Optimal Scheduling for Vector or Scalar Criterion on Parallel Machines with Arbitrary Due Dates of Tasks View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2019

AUTHORS

Michael Z. Zgurovsky , Alexander A. Pavlov

ABSTRACT

We examine the problem of constructing a feasible schedule for parallel machines of equal or various productivities with various due dates of tasks and arbitrary start times of machines. We consider two optimality criteria: maximizing the earliest start time of machines (scalar criterion) or obtaining optimal start times of machines subject to a direct lexicographical order of their assignment (vector criterion). In fact, in this chapter we examine four intractable combinatorial optimization problems (for each one there are no efficient polynomial algorithms for its solving). Each of four presented PSC-algorithms contains separate sufficient signs of optimality of a feasible solution, the first polynomial component that checks the sufficient signs of optimality, and an approximation algorithm. Since the formulated problems are quite complex, each component of the PSC-algorithms contain many subalgorithms, each of which implements a separate original heuristic. We give examples of the problems solving. More... »

PAGES

39-105

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_3

DOI

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

DIMENSIONS

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


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"
      }
    ], 
    "datePublished": "2019", 
    "datePublishedReg": "2019-01-01", 
    "description": "We examine the problem of constructing a feasible schedule for parallel machines of equal or various productivities with various due dates of tasks and arbitrary start times of machines. We consider two optimality criteria: maximizing the earliest start time of machines (scalar criterion) or obtaining optimal start times of machines subject to a direct lexicographical order of their assignment (vector criterion). In fact, in this chapter we examine four intractable combinatorial optimization problems (for each one there are no efficient polynomial algorithms for its solving). Each of four presented PSC-algorithms contains separate sufficient signs of optimality of a feasible solution, the first polynomial component that checks the sufficient signs of optimality, and an approximation algorithm. Since the formulated problems are quite complex, each component of the PSC-algorithms contain many subalgorithms, each of which implements a separate original heuristic. We give examples of the problems solving.", 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-319-98977-8_3", 
    "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": "Optimal Scheduling for Vector or Scalar Criterion on Parallel Machines with Arbitrary Due Dates of Tasks", 
    "pagination": "39-105", 
    "productId": [
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-319-98977-8_3"
        ]
      }, 
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "f96343895070736904ff0fbe4eb6477c9fbf8acf45fffb9fb0146abe1885ffe9"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1107220005"
        ]
      }
    ], 
    "publisher": {
      "location": "Cham", 
      "name": "Springer International Publishing", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-319-98977-8_3", 
      "https://app.dimensions.ai/details/publication/pub.1107220005"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2019-04-15T11:05", 
    "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_8659_00000539.jsonl", 
    "type": "Chapter", 
    "url": "http://link.springer.com/10.1007/978-3-319-98977-8_3"
  }
]
 

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

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

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

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


 

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

64 TRIPLES      21 PREDICATES      26 URIs      19 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-319-98977-8_3 schema:about anzsrc-for:01
2 anzsrc-for:0103
3 schema:author Nfd18e322d78842fbb5ffaf85d8a6ff8e
4 schema:datePublished 2019
5 schema:datePublishedReg 2019-01-01
6 schema:description We examine the problem of constructing a feasible schedule for parallel machines of equal or various productivities with various due dates of tasks and arbitrary start times of machines. We consider two optimality criteria: maximizing the earliest start time of machines (scalar criterion) or obtaining optimal start times of machines subject to a direct lexicographical order of their assignment (vector criterion). In fact, in this chapter we examine four intractable combinatorial optimization problems (for each one there are no efficient polynomial algorithms for its solving). Each of four presented PSC-algorithms contains separate sufficient signs of optimality of a feasible solution, the first polynomial component that checks the sufficient signs of optimality, and an approximation algorithm. Since the formulated problems are quite complex, each component of the PSC-algorithms contain many subalgorithms, each of which implements a separate original heuristic. We give examples of the problems solving.
7 schema:genre chapter
8 schema:inLanguage en
9 schema:isAccessibleForFree false
10 schema:isPartOf N4e455b39e73d4469ac2d46c7b283c8a0
11 schema:name Optimal Scheduling for Vector or Scalar Criterion on Parallel Machines with Arbitrary Due Dates of Tasks
12 schema:pagination 39-105
13 schema:productId N03808d4bd148403aac76300a8e438ca8
14 N638900802ff546fb90cf75fb73407413
15 N8ebe608fd0e340379aa90c40cd7bb6fe
16 schema:publisher Nea54a522b711437190f1a0f52ba422e4
17 schema:sameAs https://app.dimensions.ai/details/publication/pub.1107220005
18 https://doi.org/10.1007/978-3-319-98977-8_3
19 schema:sdDatePublished 2019-04-15T11:05
20 schema:sdLicense https://scigraph.springernature.com/explorer/license/
21 schema:sdPublisher N4a906da5aaaf4567b908c2b84ebbfd97
22 schema:url http://link.springer.com/10.1007/978-3-319-98977-8_3
23 sgo:license sg:explorer/license/
24 sgo:sdDataset chapters
25 rdf:type schema:Chapter
26 N03808d4bd148403aac76300a8e438ca8 schema:name dimensions_id
27 schema:value pub.1107220005
28 rdf:type schema:PropertyValue
29 N0553260b52ee4d49bec4c8e1b68335d4 rdf:first N2de96a236274475494ad7fc541ce8f9b
30 rdf:rest rdf:nil
31 N1255c5a43f784018bf7b1deac5208b42 schema:affiliation https://www.grid.ac/institutes/grid.440544.5
32 schema:familyName Zgurovsky
33 schema:givenName Michael Z.
34 rdf:type schema:Person
35 N2de96a236274475494ad7fc541ce8f9b schema:affiliation https://www.grid.ac/institutes/grid.440544.5
36 schema:familyName Pavlov
37 schema:givenName Alexander A.
38 rdf:type schema:Person
39 N4a906da5aaaf4567b908c2b84ebbfd97 schema:name Springer Nature - SN SciGraph project
40 rdf:type schema:Organization
41 N4e455b39e73d4469ac2d46c7b283c8a0 schema:isbn 978-3-319-98976-1
42 978-3-319-98977-8
43 schema:name Combinatorial Optimization Problems in Planning and Decision Making
44 rdf:type schema:Book
45 N638900802ff546fb90cf75fb73407413 schema:name doi
46 schema:value 10.1007/978-3-319-98977-8_3
47 rdf:type schema:PropertyValue
48 N8ebe608fd0e340379aa90c40cd7bb6fe schema:name readcube_id
49 schema:value f96343895070736904ff0fbe4eb6477c9fbf8acf45fffb9fb0146abe1885ffe9
50 rdf:type schema:PropertyValue
51 Nea54a522b711437190f1a0f52ba422e4 schema:location Cham
52 schema:name Springer International Publishing
53 rdf:type schema:Organisation
54 Nfd18e322d78842fbb5ffaf85d8a6ff8e rdf:first N1255c5a43f784018bf7b1deac5208b42
55 rdf:rest N0553260b52ee4d49bec4c8e1b68335d4
56 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
57 schema:name Mathematical Sciences
58 rdf:type schema:DefinedTerm
59 anzsrc-for:0103 schema:inDefinedTermSet anzsrc-for:
60 schema:name Numerical and Computational Mathematics
61 rdf:type schema:DefinedTerm
62 https://www.grid.ac/institutes/grid.440544.5 schema:alternateName National Technical University of Ukraine Kiev Polytechnic Institute
63 schema:name National Technical University of Ukraine
64 rdf:type schema:Organization
 




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


...