The Total Tardiness of Tasks Minimization on Identical Parallel Machines with Arbitrary Fixed Times of Their Start and a Common ... View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2019

AUTHORS

Michael Z. Zgurovsky , Alexander A. Pavlov

ABSTRACT

We solve a NP-hard problem of constructing a schedule for identical parallel machines that minimizes the total tardiness of tasks in relation to a common due date in case when the start times of machines are fixed at arbitrary time points less than the due date. We present an efficient PSC-algorithm of its solving which is a generalization of our previously developed results: for the problem with equal start times of machines we have derived two sufficient signs of optimality of a feasible solution and constructed two PSC-algorithms. Each of the algorithms checks one of these signs. In this chapter we propose a generalized PSC-algorithm for equal start times of machines that combines the best properties of both PSC-algorithms. We have obtained a modification of the generalized PSC-algorithm for the case of arbitrary start times of machines, its complexity is determined by O(n2m) function. The first polynomial component of the PSC-algorithm coincides with its second polynomial component. We obtain an efficient estimate of the deviation from an optimal solution for an approximation algorithm of the problem solving. We also present the statistical studies of the PSC-algorithm that showed its high efficiency (efficient exact solutions have been obtained for problems with tens of thousands of variables which is unique for NP-hard combinatorial optimization problems). More... »

PAGES

265-290

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_6

DOI

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

DIMENSIONS

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


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/0103", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Numerical and Computational Mathematics", 
        "type": "DefinedTerm"
      }, 
      {
        "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"
      }
    ], 
    "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.1137/1024022", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062861702"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2019", 
    "datePublishedReg": "2019-01-01", 
    "description": "We solve a NP-hard problem of constructing a schedule for identical parallel machines that minimizes the total tardiness of tasks in relation to a common due date in case when the start times of machines are fixed at arbitrary time points less than the due date. We present an efficient PSC-algorithm of its solving which is a generalization of our previously developed results: for the problem with equal start times of machines we have derived two sufficient signs of optimality of a feasible solution and constructed two PSC-algorithms. Each of the algorithms checks one of these signs. In this chapter we propose a generalized PSC-algorithm for equal start times of machines that combines the best properties of both PSC-algorithms. We have obtained a modification of the generalized PSC-algorithm for the case of arbitrary start times of machines, its complexity is determined by O(n2m) function. The first polynomial component of the PSC-algorithm coincides with its second polynomial component. We obtain an efficient estimate of the deviation from an optimal solution for an approximation algorithm of the problem solving. We also present the statistical studies of the PSC-algorithm that showed its high efficiency (efficient exact solutions have been obtained for problems with tens of thousands of variables which is unique for NP-hard combinatorial optimization problems).", 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-319-98977-8_6", 
    "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 Tardiness of Tasks Minimization on Identical Parallel Machines with Arbitrary Fixed Times of Their Start and a Common Due Date", 
    "pagination": "265-290", 
    "productId": [
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-319-98977-8_6"
        ]
      }, 
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "5c197d3c64e9fe84cea6380a21eca14d1c9061038f735dd3625e5ab884e00b57"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1107210571"
        ]
      }
    ], 
    "publisher": {
      "location": "Cham", 
      "name": "Springer International Publishing", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-319-98977-8_6", 
      "https://app.dimensions.ai/details/publication/pub.1107210571"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2019-04-16T00:32", 
    "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_8697_00000605.jsonl", 
    "type": "Chapter", 
    "url": "http://link.springer.com/10.1007/978-3-319-98977-8_6"
  }
]
 

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

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

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

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


 

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_6 schema:about anzsrc-for:01
2 anzsrc-for:0103
3 schema:author N1d008fa0b7ba4beaa32985157a5f885e
4 schema:citation https://doi.org/10.1137/1024022
5 schema:datePublished 2019
6 schema:datePublishedReg 2019-01-01
7 schema:description We solve a NP-hard problem of constructing a schedule for identical parallel machines that minimizes the total tardiness of tasks in relation to a common due date in case when the start times of machines are fixed at arbitrary time points less than the due date. We present an efficient PSC-algorithm of its solving which is a generalization of our previously developed results: for the problem with equal start times of machines we have derived two sufficient signs of optimality of a feasible solution and constructed two PSC-algorithms. Each of the algorithms checks one of these signs. In this chapter we propose a generalized PSC-algorithm for equal start times of machines that combines the best properties of both PSC-algorithms. We have obtained a modification of the generalized PSC-algorithm for the case of arbitrary start times of machines, its complexity is determined by O(n2m) function. The first polynomial component of the PSC-algorithm coincides with its second polynomial component. We obtain an efficient estimate of the deviation from an optimal solution for an approximation algorithm of the problem solving. We also present the statistical studies of the PSC-algorithm that showed its high efficiency (efficient exact solutions have been obtained for problems with tens of thousands of variables which is unique for NP-hard combinatorial optimization problems).
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf N23785357e6334a65b7895e8bf457003d
12 schema:name The Total Tardiness of Tasks Minimization on Identical Parallel Machines with Arbitrary Fixed Times of Their Start and a Common Due Date
13 schema:pagination 265-290
14 schema:productId N9f4b9485119245658bb30e2a57b37e2c
15 Nc2ac5fb79e8c4d0c80b1eb10ee475dc3
16 Nca9ea9a02bc84ed3b4b237bf06604cee
17 schema:publisher Nacbacddefe2641ba9a585f61e90518d3
18 schema:sameAs https://app.dimensions.ai/details/publication/pub.1107210571
19 https://doi.org/10.1007/978-3-319-98977-8_6
20 schema:sdDatePublished 2019-04-16T00:32
21 schema:sdLicense https://scigraph.springernature.com/explorer/license/
22 schema:sdPublisher Nb47ad7143c534aaf9184fbe82c8a260f
23 schema:url http://link.springer.com/10.1007/978-3-319-98977-8_6
24 sgo:license sg:explorer/license/
25 sgo:sdDataset chapters
26 rdf:type schema:Chapter
27 N1d008fa0b7ba4beaa32985157a5f885e rdf:first Ne2c4ac643c7f4b16a94eb30edd5d3464
28 rdf:rest N907a9badf9194c3a8803fc97992e6e58
29 N23785357e6334a65b7895e8bf457003d schema:isbn 978-3-319-98976-1
30 978-3-319-98977-8
31 schema:name Combinatorial Optimization Problems in Planning and Decision Making
32 rdf:type schema:Book
33 N907a9badf9194c3a8803fc97992e6e58 rdf:first Nf4d9a99964ab42d88ab45bf99559c9ef
34 rdf:rest rdf:nil
35 N9f4b9485119245658bb30e2a57b37e2c schema:name dimensions_id
36 schema:value pub.1107210571
37 rdf:type schema:PropertyValue
38 Nacbacddefe2641ba9a585f61e90518d3 schema:location Cham
39 schema:name Springer International Publishing
40 rdf:type schema:Organisation
41 Nb47ad7143c534aaf9184fbe82c8a260f schema:name Springer Nature - SN SciGraph project
42 rdf:type schema:Organization
43 Nc2ac5fb79e8c4d0c80b1eb10ee475dc3 schema:name doi
44 schema:value 10.1007/978-3-319-98977-8_6
45 rdf:type schema:PropertyValue
46 Nca9ea9a02bc84ed3b4b237bf06604cee schema:name readcube_id
47 schema:value 5c197d3c64e9fe84cea6380a21eca14d1c9061038f735dd3625e5ab884e00b57
48 rdf:type schema:PropertyValue
49 Ne2c4ac643c7f4b16a94eb30edd5d3464 schema:affiliation https://www.grid.ac/institutes/grid.440544.5
50 schema:familyName Zgurovsky
51 schema:givenName Michael Z.
52 rdf:type schema:Person
53 Nf4d9a99964ab42d88ab45bf99559c9ef schema:affiliation https://www.grid.ac/institutes/grid.440544.5
54 schema:familyName Pavlov
55 schema:givenName Alexander A.
56 rdf:type schema:Person
57 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
58 schema:name Mathematical Sciences
59 rdf:type schema:DefinedTerm
60 anzsrc-for:0103 schema:inDefinedTermSet anzsrc-for:
61 schema:name Numerical and Computational Mathematics
62 rdf:type schema:DefinedTerm
63 https://doi.org/10.1137/1024022 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062861702
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)


...