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-09-02T15:54", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220902/entities/gbq_results/article/article_487.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 N07d25f5868db4c4095fb94d394b9e0d0
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 N7ec830c209c94a57b5c7728044cc97fc
13 N816c583f48ce4360860240e1c40cef2f
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 N44df1c643744489681fee4ef96d2b37a
43 N74546fb9e3be4d24a15b85fbe2474e9e
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-09-02T15:54
47 schema:sdLicense https://scigraph.springernature.com/explorer/license/
48 schema:sdPublisher N6fcfa28d0aa74bf8a204f7dd9c1a00c0
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 N07d25f5868db4c4095fb94d394b9e0d0 rdf:first sg:person.014157175455.29
54 rdf:rest Na63255468f804c65a12238650c24e7ad
55 N44df1c643744489681fee4ef96d2b37a schema:name dimensions_id
56 schema:value pub.1032248027
57 rdf:type schema:PropertyValue
58 N6fcfa28d0aa74bf8a204f7dd9c1a00c0 schema:name Springer Nature - SN SciGraph project
59 rdf:type schema:Organization
60 N74546fb9e3be4d24a15b85fbe2474e9e schema:name doi
61 schema:value 10.1007/s00453-009-9337-9
62 rdf:type schema:PropertyValue
63 N7ec830c209c94a57b5c7728044cc97fc schema:volumeNumber 60
64 rdf:type schema:PublicationVolume
65 N816c583f48ce4360860240e1c40cef2f schema:issueNumber 2
66 rdf:type schema:PublicationIssue
67 Na63255468f804c65a12238650c24e7ad rdf:first sg:person.011520224512.05
68 rdf:rest rdf:nil
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)


...