The Total Weighted Tardiness of Tasks Minimization on a Single Machine View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2019

AUTHORS

Michael Z. Zgurovsky , Alexander A. Pavlov

ABSTRACT

We solve the problem of constructing a schedule for a single machine with various due dates and a fixed start time of the machine that minimizes the sum of weighted tardiness of tasks in relation to their due dates. The problem is NP-hard in the strong sense and is one of the most known intractable combinatorial optimization problems. Unlike other PSC-algorithms in this monograph, in this chapter we present an efficient PSC-algorithm which, in addition to the first and second polynomial components (the first one contains twelve sufficient signs of optimality of a feasible schedule) includes exact subalgorithm for its solving. We have obtained the sufficient conditions that are constructively verified in the process of its execution. If the conditions are true, the exact subalgorithm becomes polynomial. We give statistical studies of the developed algorithm and show the solving of well-known examples of the problem. We present an approximation algorithm (the second polynomial component) based on the exact algorithm. Average statistical estimate of deviation of an approximate solution from the optimum does not exceed 5% of it. More... »

PAGES

107-217

References to SciGraph publications

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_4

DOI

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

DIMENSIONS

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


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.1016/0166-218x(90)90103-j", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1008240693"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0167-6377(82)90035-9", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1009890908"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0167-6377(82)90035-9", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1009890908"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/s10951-008-0093-5", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1016736892", 
          "https://doi.org/10.1007/s10951-008-0093-5"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/s0305-0548(97)00073-7", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1023787614"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/s0925-5273(02)00265-7", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1028037167"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/s0925-5273(02)00265-7", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1028037167"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/s0377-2217(00)00319-2", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1031822820"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf01580393", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1033447882", 
          "https://doi.org/10.1007/bf01580393"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf01580393", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1033447882", 
          "https://doi.org/10.1007/bf01580393"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/s0377-2217(87)80008-5", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1035319998"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/s0167-5060(08)70742-8", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1036482707"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf01585935", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1037877198", 
          "https://doi.org/10.1007/bf01585935"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/2344422.2344430", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1038653483"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/s0167-6377(03)00064-6", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1038985703"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/s0167-6377(03)00064-6", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1038985703"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1287/mnsc.39.5.626", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1064721073"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1287/opre.17.4.701", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1064727375"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1287/opre.23.5.908", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1064728652"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1287/opre.33.2.363", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1064729609"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1287/opre.35.3.450", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1064729831"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1287/opre.39.4.639", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1064730249"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1002/9780470451793", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1098662151"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-319-91008-6_43", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1103945644", 
          "https://doi.org/10.1007/978-3-319-91008-6_43"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2019", 
    "datePublishedReg": "2019-01-01", 
    "description": "We solve the problem of constructing a schedule for a single machine with various due dates and a fixed start time of the machine that minimizes the sum of weighted tardiness of tasks in relation to their due dates. The problem is NP-hard in the strong sense and is one of the most known intractable combinatorial optimization problems. Unlike other PSC-algorithms in this monograph, in this chapter we present an efficient PSC-algorithm which, in addition to the first and second polynomial components (the first one contains twelve sufficient signs of optimality of a feasible schedule) includes exact subalgorithm for its solving. We have obtained the sufficient conditions that are constructively verified in the process of its execution. If the conditions are true, the exact subalgorithm becomes polynomial. We give statistical studies of the developed algorithm and show the solving of well-known examples of the problem. We present an approximation algorithm (the second polynomial component) based on the exact algorithm. Average statistical estimate of deviation of an approximate solution from the optimum does not exceed 5% of it.", 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-319-98977-8_4", 
    "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 Tardiness of Tasks Minimization on a Single Machine", 
    "pagination": "107-217", 
    "productId": [
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-319-98977-8_4"
        ]
      }, 
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "29b53c57c803b6573a52f959e17520d7a9ece2f9f07888d0872a6241bf073242"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1107207437"
        ]
      }
    ], 
    "publisher": {
      "location": "Cham", 
      "name": "Springer International Publishing", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-319-98977-8_4", 
      "https://app.dimensions.ai/details/publication/pub.1107207437"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2019-04-16T01:28", 
    "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_8700_00000605.jsonl", 
    "type": "Chapter", 
    "url": "http://link.springer.com/10.1007/978-3-319-98977-8_4"
  }
]
 

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_4'

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_4'

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_4'

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_4'


 

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

128 TRIPLES      22 PREDICATES      46 URIs      19 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-319-98977-8_4 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author Ned9506f9e0ae499fbebcf6a12e743d15
4 schema:citation sg:pub.10.1007/978-3-319-91008-6_43
5 sg:pub.10.1007/bf01580393
6 sg:pub.10.1007/bf01585935
7 sg:pub.10.1007/s10951-008-0093-5
8 https://doi.org/10.1002/9780470451793
9 https://doi.org/10.1016/0166-218x(90)90103-j
10 https://doi.org/10.1016/0167-6377(82)90035-9
11 https://doi.org/10.1016/s0167-5060(08)70742-8
12 https://doi.org/10.1016/s0167-6377(03)00064-6
13 https://doi.org/10.1016/s0305-0548(97)00073-7
14 https://doi.org/10.1016/s0377-2217(00)00319-2
15 https://doi.org/10.1016/s0377-2217(87)80008-5
16 https://doi.org/10.1016/s0925-5273(02)00265-7
17 https://doi.org/10.1145/2344422.2344430
18 https://doi.org/10.1287/mnsc.39.5.626
19 https://doi.org/10.1287/opre.17.4.701
20 https://doi.org/10.1287/opre.23.5.908
21 https://doi.org/10.1287/opre.33.2.363
22 https://doi.org/10.1287/opre.35.3.450
23 https://doi.org/10.1287/opre.39.4.639
24 schema:datePublished 2019
25 schema:datePublishedReg 2019-01-01
26 schema:description We solve the problem of constructing a schedule for a single machine with various due dates and a fixed start time of the machine that minimizes the sum of weighted tardiness of tasks in relation to their due dates. The problem is NP-hard in the strong sense and is one of the most known intractable combinatorial optimization problems. Unlike other PSC-algorithms in this monograph, in this chapter we present an efficient PSC-algorithm which, in addition to the first and second polynomial components (the first one contains twelve sufficient signs of optimality of a feasible schedule) includes exact subalgorithm for its solving. We have obtained the sufficient conditions that are constructively verified in the process of its execution. If the conditions are true, the exact subalgorithm becomes polynomial. We give statistical studies of the developed algorithm and show the solving of well-known examples of the problem. We present an approximation algorithm (the second polynomial component) based on the exact algorithm. Average statistical estimate of deviation of an approximate solution from the optimum does not exceed 5% of it.
27 schema:genre chapter
28 schema:inLanguage en
29 schema:isAccessibleForFree false
30 schema:isPartOf Nc809f13092c54781bd05aad423445aed
31 schema:name The Total Weighted Tardiness of Tasks Minimization on a Single Machine
32 schema:pagination 107-217
33 schema:productId N033a983ffc6a452c9874c1d1ea0e7ab3
34 N8fed3af0bbad4d32a04d90b45671c78c
35 Ne31950ec263047f49c1c59595a3d1a52
36 schema:publisher Nf81f065c115a4959b7d3c9f51631a4fc
37 schema:sameAs https://app.dimensions.ai/details/publication/pub.1107207437
38 https://doi.org/10.1007/978-3-319-98977-8_4
39 schema:sdDatePublished 2019-04-16T01:28
40 schema:sdLicense https://scigraph.springernature.com/explorer/license/
41 schema:sdPublisher Nd681bbeaa76d423ea81e7472923f3cf3
42 schema:url http://link.springer.com/10.1007/978-3-319-98977-8_4
43 sgo:license sg:explorer/license/
44 sgo:sdDataset chapters
45 rdf:type schema:Chapter
46 N033a983ffc6a452c9874c1d1ea0e7ab3 schema:name readcube_id
47 schema:value 29b53c57c803b6573a52f959e17520d7a9ece2f9f07888d0872a6241bf073242
48 rdf:type schema:PropertyValue
49 N1c97ae5a7fa14fc190f8c43465d193dd rdf:first N5a2304c9f13249fdb10e852ec504bd7b
50 rdf:rest rdf:nil
51 N5a2304c9f13249fdb10e852ec504bd7b schema:affiliation https://www.grid.ac/institutes/grid.440544.5
52 schema:familyName Pavlov
53 schema:givenName Alexander A.
54 rdf:type schema:Person
55 N8fed3af0bbad4d32a04d90b45671c78c schema:name dimensions_id
56 schema:value pub.1107207437
57 rdf:type schema:PropertyValue
58 N9222ca17be224cd4bbc17c8ce5f08a0d schema:affiliation https://www.grid.ac/institutes/grid.440544.5
59 schema:familyName Zgurovsky
60 schema:givenName Michael Z.
61 rdf:type schema:Person
62 Nc809f13092c54781bd05aad423445aed schema:isbn 978-3-319-98976-1
63 978-3-319-98977-8
64 schema:name Combinatorial Optimization Problems in Planning and Decision Making
65 rdf:type schema:Book
66 Nd681bbeaa76d423ea81e7472923f3cf3 schema:name Springer Nature - SN SciGraph project
67 rdf:type schema:Organization
68 Ne31950ec263047f49c1c59595a3d1a52 schema:name doi
69 schema:value 10.1007/978-3-319-98977-8_4
70 rdf:type schema:PropertyValue
71 Ned9506f9e0ae499fbebcf6a12e743d15 rdf:first N9222ca17be224cd4bbc17c8ce5f08a0d
72 rdf:rest N1c97ae5a7fa14fc190f8c43465d193dd
73 Nf81f065c115a4959b7d3c9f51631a4fc schema:location Cham
74 schema:name Springer International Publishing
75 rdf:type schema:Organisation
76 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
77 schema:name Information and Computing Sciences
78 rdf:type schema:DefinedTerm
79 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
80 schema:name Computation Theory and Mathematics
81 rdf:type schema:DefinedTerm
82 sg:pub.10.1007/978-3-319-91008-6_43 schema:sameAs https://app.dimensions.ai/details/publication/pub.1103945644
83 https://doi.org/10.1007/978-3-319-91008-6_43
84 rdf:type schema:CreativeWork
85 sg:pub.10.1007/bf01580393 schema:sameAs https://app.dimensions.ai/details/publication/pub.1033447882
86 https://doi.org/10.1007/bf01580393
87 rdf:type schema:CreativeWork
88 sg:pub.10.1007/bf01585935 schema:sameAs https://app.dimensions.ai/details/publication/pub.1037877198
89 https://doi.org/10.1007/bf01585935
90 rdf:type schema:CreativeWork
91 sg:pub.10.1007/s10951-008-0093-5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1016736892
92 https://doi.org/10.1007/s10951-008-0093-5
93 rdf:type schema:CreativeWork
94 https://doi.org/10.1002/9780470451793 schema:sameAs https://app.dimensions.ai/details/publication/pub.1098662151
95 rdf:type schema:CreativeWork
96 https://doi.org/10.1016/0166-218x(90)90103-j schema:sameAs https://app.dimensions.ai/details/publication/pub.1008240693
97 rdf:type schema:CreativeWork
98 https://doi.org/10.1016/0167-6377(82)90035-9 schema:sameAs https://app.dimensions.ai/details/publication/pub.1009890908
99 rdf:type schema:CreativeWork
100 https://doi.org/10.1016/s0167-5060(08)70742-8 schema:sameAs https://app.dimensions.ai/details/publication/pub.1036482707
101 rdf:type schema:CreativeWork
102 https://doi.org/10.1016/s0167-6377(03)00064-6 schema:sameAs https://app.dimensions.ai/details/publication/pub.1038985703
103 rdf:type schema:CreativeWork
104 https://doi.org/10.1016/s0305-0548(97)00073-7 schema:sameAs https://app.dimensions.ai/details/publication/pub.1023787614
105 rdf:type schema:CreativeWork
106 https://doi.org/10.1016/s0377-2217(00)00319-2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1031822820
107 rdf:type schema:CreativeWork
108 https://doi.org/10.1016/s0377-2217(87)80008-5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1035319998
109 rdf:type schema:CreativeWork
110 https://doi.org/10.1016/s0925-5273(02)00265-7 schema:sameAs https://app.dimensions.ai/details/publication/pub.1028037167
111 rdf:type schema:CreativeWork
112 https://doi.org/10.1145/2344422.2344430 schema:sameAs https://app.dimensions.ai/details/publication/pub.1038653483
113 rdf:type schema:CreativeWork
114 https://doi.org/10.1287/mnsc.39.5.626 schema:sameAs https://app.dimensions.ai/details/publication/pub.1064721073
115 rdf:type schema:CreativeWork
116 https://doi.org/10.1287/opre.17.4.701 schema:sameAs https://app.dimensions.ai/details/publication/pub.1064727375
117 rdf:type schema:CreativeWork
118 https://doi.org/10.1287/opre.23.5.908 schema:sameAs https://app.dimensions.ai/details/publication/pub.1064728652
119 rdf:type schema:CreativeWork
120 https://doi.org/10.1287/opre.33.2.363 schema:sameAs https://app.dimensions.ai/details/publication/pub.1064729609
121 rdf:type schema:CreativeWork
122 https://doi.org/10.1287/opre.35.3.450 schema:sameAs https://app.dimensions.ai/details/publication/pub.1064729831
123 rdf:type schema:CreativeWork
124 https://doi.org/10.1287/opre.39.4.639 schema:sameAs https://app.dimensions.ai/details/publication/pub.1064730249
125 rdf:type schema:CreativeWork
126 https://www.grid.ac/institutes/grid.440544.5 schema:alternateName National Technical University of Ukraine Kiev Polytechnic Institute
127 schema:name National Technical University of Ukraine
128 rdf:type schema:Organization
 




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


...