An Online Algorithm for a Problem in Scheduling with Set-ups and Release Times View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

2009-07-07

AUTHORS

Srikrishnan Divakaran, Michael Saks

ABSTRACT

We address the problem of sequential single machine scheduling of jobs with release times, where jobs are classified into types, and the machine must be properly configured to handle jobs of a given type. The objective is to minimize the maximum flow time (time from release until completion) of any job. We consider this problem under the assumptions of sequence independent set-up times and item availability with the objective of minimizing the maximum flow time. We present an online algorithm that is O(1)-competitive, that is, always gets within a constant factor of optimal. We also show that exact offline optimization of maximum flow time is NP-hard. More... »

PAGES

301-315

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/s00453-009-9337-9

DOI

http://dx.doi.org/10.1007/s00453-009-9337-9

DIMENSIONS

https://app.dimensions.ai/details/publication/pub.1032248027


Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
Incoming Citations Browse incoming citations for this publication using opencitations.net

JSON-LD is the canonical representation for SciGraph data.

TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT

[
  {
    "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
    "about": [
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/01", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Mathematical Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0103", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Numerical and Computational Mathematics", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Dhirubhai Ambani Institute of Information and Communication Technology, 4212, Faculty Block 4, Gujarat, India", 
          "id": "http://www.grid.ac/institutes/grid.444424.6", 
          "name": [
            "Dhirubhai Ambani Institute of Information and Communication Technology, 4212, Faculty Block 4, Gujarat, India"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Divakaran", 
        "givenName": "Srikrishnan", 
        "id": "sg:person.014157175455.29", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014157175455.29"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Mathematics, Rutgers, The State University of New Jersey, 430, Hill Center, 08855, Piscataway, NJ, USA", 
          "id": "http://www.grid.ac/institutes/grid.430387.b", 
          "name": [
            "Department of Mathematics, Rutgers, The State University of New Jersey, 430, Hill Center, 08855, Piscataway, NJ, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Saks", 
        "givenName": "Michael", 
        "id": "sg:person.011520224512.05", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011520224512.05"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "sg:pub.10.1023/a:1018903027868", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1040111894", 
          "https://doi.org/10.1023/a:1018903027868"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1023/a:1018978322417", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1051456798", 
          "https://doi.org/10.1023/a:1018978322417"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1023/a:1018920416308", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1017572792", 
          "https://doi.org/10.1023/a:1018920416308"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2009-07-07", 
    "datePublishedReg": "2009-07-07", 
    "description": "We address the problem of sequential single machine scheduling of jobs with release times, where jobs are classified into types, and the machine must be properly configured to handle jobs of a given type. The objective is to minimize the maximum flow time (time from release until completion) of any job. We consider this problem under the assumptions of sequence independent set-up times and item availability with the objective of minimizing the maximum flow time. We present an online algorithm that is O(1)-competitive, that is, always gets within a constant factor of optimal. We also show that exact offline optimization of maximum flow time is NP-hard.", 
    "genre": "article", 
    "id": "sg:pub.10.1007/s00453-009-9337-9", 
    "isAccessibleForFree": false, 
    "isPartOf": [
      {
        "id": "sg:journal.1047644", 
        "issn": [
          "0178-4617", 
          "1432-0541"
        ], 
        "name": "Algorithmica", 
        "publisher": "Springer Nature", 
        "type": "Periodical"
      }, 
      {
        "issueNumber": "2", 
        "type": "PublicationIssue"
      }, 
      {
        "type": "PublicationVolume", 
        "volumeNumber": "60"
      }
    ], 
    "keywords": [
      "maximum flow time", 
      "sequence-independent set", 
      "flow time", 
      "single-machine scheduling", 
      "online algorithm", 
      "machine scheduling", 
      "offline optimization", 
      "constant factor", 
      "independent set", 
      "release time", 
      "scheduling", 
      "problem", 
      "algorithm", 
      "optimization", 
      "assumption", 
      "set", 
      "NPs", 
      "time", 
      "item availability", 
      "machine", 
      "types", 
      "jobs", 
      "objective", 
      "availability", 
      "factors"
    ], 
    "name": "An Online Algorithm for a Problem in Scheduling with Set-ups and Release Times", 
    "pagination": "301-315", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1032248027"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/s00453-009-9337-9"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1007/s00453-009-9337-9", 
      "https://app.dimensions.ai/details/publication/pub.1032248027"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2022-11-24T20:54", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20221124/entities/gbq_results/article/article_477.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "https://doi.org/10.1007/s00453-009-9337-9"
  }
]
 

Download the RDF metadata as:  json-ld nt turtle xml License info

HOW TO GET THIS DATA PROGRAMMATICALLY:

JSON-LD is a popular format for linked data which is fully compatible with JSON.

curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/s00453-009-9337-9'

N-Triples is a line-based linked data format ideal for batch operations.

curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/s00453-009-9337-9'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s00453-009-9337-9'

RDF/XML is a standard XML format for linked data.

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s00453-009-9337-9'


 

This table displays all metadata directly associated to this object as RDF triples.

104 TRIPLES      21 PREDICATES      52 URIs      41 LITERALS      6 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/s00453-009-9337-9 schema:about anzsrc-for:01
2 anzsrc-for:0103
3 schema:author N78d43fc2d26b4544a2744f552e1a8f2d
4 schema:citation sg:pub.10.1023/a:1018903027868
5 sg:pub.10.1023/a:1018920416308
6 sg:pub.10.1023/a:1018978322417
7 schema:datePublished 2009-07-07
8 schema:datePublishedReg 2009-07-07
9 schema:description We address the problem of sequential single machine scheduling of jobs with release times, where jobs are classified into types, and the machine must be properly configured to handle jobs of a given type. The objective is to minimize the maximum flow time (time from release until completion) of any job. We consider this problem under the assumptions of sequence independent set-up times and item availability with the objective of minimizing the maximum flow time. We present an online algorithm that is O(1)-competitive, that is, always gets within a constant factor of optimal. We also show that exact offline optimization of maximum flow time is NP-hard.
10 schema:genre article
11 schema:isAccessibleForFree false
12 schema:isPartOf N1ec50906edcf44b59750858b01f58696
13 N29e3c62648814fbeb5757dd8a46a1f4e
14 sg:journal.1047644
15 schema:keywords NPs
16 algorithm
17 assumption
18 availability
19 constant factor
20 factors
21 flow time
22 independent set
23 item availability
24 jobs
25 machine
26 machine scheduling
27 maximum flow time
28 objective
29 offline optimization
30 online algorithm
31 optimization
32 problem
33 release time
34 scheduling
35 sequence-independent set
36 set
37 single-machine scheduling
38 time
39 types
40 schema:name An Online Algorithm for a Problem in Scheduling with Set-ups and Release Times
41 schema:pagination 301-315
42 schema:productId N050f099d4092495cb6ea37b63edbe98c
43 N8d98e0bb75a34767a4a35956d56299ac
44 schema:sameAs https://app.dimensions.ai/details/publication/pub.1032248027
45 https://doi.org/10.1007/s00453-009-9337-9
46 schema:sdDatePublished 2022-11-24T20:54
47 schema:sdLicense https://scigraph.springernature.com/explorer/license/
48 schema:sdPublisher N828c14c8bccb4b9a996684615c8dd545
49 schema:url https://doi.org/10.1007/s00453-009-9337-9
50 sgo:license sg:explorer/license/
51 sgo:sdDataset articles
52 rdf:type schema:ScholarlyArticle
53 N050f099d4092495cb6ea37b63edbe98c schema:name doi
54 schema:value 10.1007/s00453-009-9337-9
55 rdf:type schema:PropertyValue
56 N1ec50906edcf44b59750858b01f58696 schema:volumeNumber 60
57 rdf:type schema:PublicationVolume
58 N29e3c62648814fbeb5757dd8a46a1f4e schema:issueNumber 2
59 rdf:type schema:PublicationIssue
60 N63ee395a699c42bd9e33a0bf79923d31 rdf:first sg:person.011520224512.05
61 rdf:rest rdf:nil
62 N78d43fc2d26b4544a2744f552e1a8f2d rdf:first sg:person.014157175455.29
63 rdf:rest N63ee395a699c42bd9e33a0bf79923d31
64 N828c14c8bccb4b9a996684615c8dd545 schema:name Springer Nature - SN SciGraph project
65 rdf:type schema:Organization
66 N8d98e0bb75a34767a4a35956d56299ac schema:name dimensions_id
67 schema:value pub.1032248027
68 rdf:type schema:PropertyValue
69 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
70 schema:name Mathematical Sciences
71 rdf:type schema:DefinedTerm
72 anzsrc-for:0103 schema:inDefinedTermSet anzsrc-for:
73 schema:name Numerical and Computational Mathematics
74 rdf:type schema:DefinedTerm
75 sg:journal.1047644 schema:issn 0178-4617
76 1432-0541
77 schema:name Algorithmica
78 schema:publisher Springer Nature
79 rdf:type schema:Periodical
80 sg:person.011520224512.05 schema:affiliation grid-institutes:grid.430387.b
81 schema:familyName Saks
82 schema:givenName Michael
83 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011520224512.05
84 rdf:type schema:Person
85 sg:person.014157175455.29 schema:affiliation grid-institutes:grid.444424.6
86 schema:familyName Divakaran
87 schema:givenName Srikrishnan
88 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014157175455.29
89 rdf:type schema:Person
90 sg:pub.10.1023/a:1018903027868 schema:sameAs https://app.dimensions.ai/details/publication/pub.1040111894
91 https://doi.org/10.1023/a:1018903027868
92 rdf:type schema:CreativeWork
93 sg:pub.10.1023/a:1018920416308 schema:sameAs https://app.dimensions.ai/details/publication/pub.1017572792
94 https://doi.org/10.1023/a:1018920416308
95 rdf:type schema:CreativeWork
96 sg:pub.10.1023/a:1018978322417 schema:sameAs https://app.dimensions.ai/details/publication/pub.1051456798
97 https://doi.org/10.1023/a:1018978322417
98 rdf:type schema:CreativeWork
99 grid-institutes:grid.430387.b schema:alternateName Department of Mathematics, Rutgers, The State University of New Jersey, 430, Hill Center, 08855, Piscataway, NJ, USA
100 schema:name Department of Mathematics, Rutgers, The State University of New Jersey, 430, Hill Center, 08855, Piscataway, NJ, USA
101 rdf:type schema:Organization
102 grid-institutes:grid.444424.6 schema:alternateName Dhirubhai Ambani Institute of Information and Communication Technology, 4212, Faculty Block 4, Gujarat, India
103 schema:name Dhirubhai Ambani Institute of Information and Communication Technology, 4212, Faculty Block 4, Gujarat, India
104 rdf:type schema:Organization
 




Preview window. Press ESC to close (or click here)


...