The Total Weighted Completion Time of Tasks Minimization with Precedence Relations on a Single Machine View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2019

AUTHORS

Michael Z. Zgurovsky , Alexander A. Pavlov

ABSTRACT

We consider the problem of constructing a schedule for a single machine that minimizes the total weighted completion time of tasks when the restrictions on their processing order are given by an arbitrary oriented acyclic graph. The problem is NP-hard in the strong sense. Efficient polynomial algorithms for its solving are known only for cases when the oriented acyclic graph is a tree or a series-parallel graph. We give a new efficient PSC-algorithm of its solving. It is based on our earlier theoretical and practical results and solves the problem with precedence relations specified by an oriented acyclic graph of the general form. The first polynomial component of the PSC-algorithm contains sixteen sufficient signs of optimality. One of them will be statistically significantly satisfied at each iteration of the algorithm when solving randomly generated problem instances. In case when the sufficient signs of optimality fail, the PSC-algorithm is an efficient approximation algorithm. If the sufficient signs of optimality are satisfied at each iteration then the algorithm becomes exact. We present the empirical properties of the PSC-algorithm on the basis of statistical studies. More... »

PAGES

291-344

Book

TITLE

Combinatorial Optimization Problems in Planning and Decision Making

ISBN

978-3-319-98976-1
978-3-319-98977-8

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-319-98977-8_7

DOI

http://dx.doi.org/10.1007/978-3-319-98977-8_7

DIMENSIONS

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


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/0802", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Computation Theory and Mathematics", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/08", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Information and Computing Sciences", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "National Technical University of Ukraine Kiev Polytechnic Institute", 
          "id": "https://www.grid.ac/institutes/grid.440544.5", 
          "name": [
            "National Technical University of Ukraine"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Zgurovsky", 
        "givenName": "Michael Z.", 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "National Technical University of Ukraine Kiev Polytechnic Institute", 
          "id": "https://www.grid.ac/institutes/grid.440544.5", 
          "name": [
            "National Technical University of Ukraine"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Pavlov", 
        "givenName": "Alexander A.", 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "https://doi.org/10.1287/opre.23.2.283", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1064728592"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2019", 
    "datePublishedReg": "2019-01-01", 
    "description": "We consider the problem of constructing a schedule for a single machine that minimizes the total weighted completion time of tasks when the restrictions on their processing order are given by an arbitrary oriented acyclic graph. The problem is NP-hard in the strong sense. Efficient polynomial algorithms for its solving are known only for cases when the oriented acyclic graph is a tree or a series-parallel graph. We give a new efficient PSC-algorithm of its solving. It is based on our earlier theoretical and practical results and solves the problem with precedence relations specified by an oriented acyclic graph of the general form. The first polynomial component of the PSC-algorithm contains sixteen sufficient signs of optimality. One of them will be statistically significantly satisfied at each iteration of the algorithm when solving randomly generated problem instances. In case when the sufficient signs of optimality fail, the PSC-algorithm is an efficient approximation algorithm. If the sufficient signs of optimality are satisfied at each iteration then the algorithm becomes exact. We present the empirical properties of the PSC-algorithm on the basis of statistical studies.", 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-319-98977-8_7", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-319-98976-1", 
        "978-3-319-98977-8"
      ], 
      "name": "Combinatorial Optimization Problems in Planning and Decision Making", 
      "type": "Book"
    }, 
    "name": "The Total Weighted Completion Time of Tasks Minimization with Precedence Relations on a Single Machine", 
    "pagination": "291-344", 
    "productId": [
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-319-98977-8_7"
        ]
      }, 
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "fb0c0f4e6aadc512a3c10e720f77e11aef41b9780bac316a3bd66ffec4e146b3"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1107220123"
        ]
      }
    ], 
    "publisher": {
      "location": "Cham", 
      "name": "Springer International Publishing", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-319-98977-8_7", 
      "https://app.dimensions.ai/details/publication/pub.1107220123"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2019-04-15T19:40", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-uberresearch-data-dimensions-target-20181106-alternative/cleanup/v134/2549eaecd7973599484d7c17b260dba0a4ecb94b/merge/v9/a6c9fde33151104705d4d7ff012ea9563521a3ce/jats-lookup/v90/0000000001_0000000264/records_8684_00000539.jsonl", 
    "type": "Chapter", 
    "url": "http://link.springer.com/10.1007/978-3-319-98977-8_7"
  }
]
 

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/978-3-319-98977-8_7'

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/978-3-319-98977-8_7'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-319-98977-8_7'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/978-3-319-98977-8_7'


 

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

67 TRIPLES      22 PREDICATES      27 URIs      19 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-319-98977-8_7 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author N8b53d63bd8484a3f97ee2a7739760d7f
4 schema:citation https://doi.org/10.1287/opre.23.2.283
5 schema:datePublished 2019
6 schema:datePublishedReg 2019-01-01
7 schema:description We consider the problem of constructing a schedule for a single machine that minimizes the total weighted completion time of tasks when the restrictions on their processing order are given by an arbitrary oriented acyclic graph. The problem is NP-hard in the strong sense. Efficient polynomial algorithms for its solving are known only for cases when the oriented acyclic graph is a tree or a series-parallel graph. We give a new efficient PSC-algorithm of its solving. It is based on our earlier theoretical and practical results and solves the problem with precedence relations specified by an oriented acyclic graph of the general form. The first polynomial component of the PSC-algorithm contains sixteen sufficient signs of optimality. One of them will be statistically significantly satisfied at each iteration of the algorithm when solving randomly generated problem instances. In case when the sufficient signs of optimality fail, the PSC-algorithm is an efficient approximation algorithm. If the sufficient signs of optimality are satisfied at each iteration then the algorithm becomes exact. We present the empirical properties of the PSC-algorithm on the basis of statistical studies.
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf N9e9e5ab9ac4546e0bd96409cb1ffde8f
12 schema:name The Total Weighted Completion Time of Tasks Minimization with Precedence Relations on a Single Machine
13 schema:pagination 291-344
14 schema:productId N6d2b0e6436114d98a1890b15f62adf71
15 N8842281b63a0467ba9c12dce608073d1
16 N8fd9017facde47cf9c25ee42f027b4b7
17 schema:publisher N54634ef9f98d4a30b0cf2ad1e6d1fa0a
18 schema:sameAs https://app.dimensions.ai/details/publication/pub.1107220123
19 https://doi.org/10.1007/978-3-319-98977-8_7
20 schema:sdDatePublished 2019-04-15T19:40
21 schema:sdLicense https://scigraph.springernature.com/explorer/license/
22 schema:sdPublisher N178986c9584e4e768232d457c12b30fa
23 schema:url http://link.springer.com/10.1007/978-3-319-98977-8_7
24 sgo:license sg:explorer/license/
25 sgo:sdDataset chapters
26 rdf:type schema:Chapter
27 N178986c9584e4e768232d457c12b30fa schema:name Springer Nature - SN SciGraph project
28 rdf:type schema:Organization
29 N206c21fd6fc748ed8aff590c5aedead4 schema:affiliation https://www.grid.ac/institutes/grid.440544.5
30 schema:familyName Pavlov
31 schema:givenName Alexander A.
32 rdf:type schema:Person
33 N54634ef9f98d4a30b0cf2ad1e6d1fa0a schema:location Cham
34 schema:name Springer International Publishing
35 rdf:type schema:Organisation
36 N6d2b0e6436114d98a1890b15f62adf71 schema:name doi
37 schema:value 10.1007/978-3-319-98977-8_7
38 rdf:type schema:PropertyValue
39 N8842281b63a0467ba9c12dce608073d1 schema:name readcube_id
40 schema:value fb0c0f4e6aadc512a3c10e720f77e11aef41b9780bac316a3bd66ffec4e146b3
41 rdf:type schema:PropertyValue
42 N8b53d63bd8484a3f97ee2a7739760d7f rdf:first Nb195048f51f344e7ab5bc44364d86089
43 rdf:rest Nebde5b4067f14e1390a31aca8d4119c1
44 N8fd9017facde47cf9c25ee42f027b4b7 schema:name dimensions_id
45 schema:value pub.1107220123
46 rdf:type schema:PropertyValue
47 N9e9e5ab9ac4546e0bd96409cb1ffde8f schema:isbn 978-3-319-98976-1
48 978-3-319-98977-8
49 schema:name Combinatorial Optimization Problems in Planning and Decision Making
50 rdf:type schema:Book
51 Nb195048f51f344e7ab5bc44364d86089 schema:affiliation https://www.grid.ac/institutes/grid.440544.5
52 schema:familyName Zgurovsky
53 schema:givenName Michael Z.
54 rdf:type schema:Person
55 Nebde5b4067f14e1390a31aca8d4119c1 rdf:first N206c21fd6fc748ed8aff590c5aedead4
56 rdf:rest rdf:nil
57 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
58 schema:name Information and Computing Sciences
59 rdf:type schema:DefinedTerm
60 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
61 schema:name Computation Theory and Mathematics
62 rdf:type schema:DefinedTerm
63 https://doi.org/10.1287/opre.23.2.283 schema:sameAs https://app.dimensions.ai/details/publication/pub.1064728592
64 rdf:type schema:CreativeWork
65 https://www.grid.ac/institutes/grid.440544.5 schema:alternateName National Technical University of Ukraine Kiev Polytechnic Institute
66 schema:name National Technical University of Ukraine
67 rdf:type schema:Organization
 




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


...