Job shop scheduling with group-dependent setups, finite buffers, and long time horizon View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

1998-01

AUTHORS

Peter B. Luh, Ling Gou, Yuanhui Zhang, Takaaki Nagahora, Makoto Tsuji, Kiyoshi Yoneda, Tetsuo Hasegawa, Yuji Kyoya, Toshiyuki Kano

ABSTRACT

Scheduling is a key factor for manufacturing productivity. Effective scheduling can improve on-time delivery of products, reduce inventory, cut lead times, and improve the utilization of bottleneck resources. This study was motivated by the design and implementation of a scheduling system for the manufacturing of Toshiba's gas insulated switchgears. The manufacturing is characterized by significant machine setup times, strict local buffer capacities, the option of choosing a few alternative processing routes, and long horizon as compared to the time resolution required. This problem has been recognized to be extremely difficult because of the combinatorial nature of integer optimization and the large size of the real problem. Our goal is thus to obtain near-optimal schedules with quantifiable quality in a computationally efficient manner. To achieve this goal, a novel integer optimization formulation with a separable structure is developed, and a solution methodology based on a combined Lagrangian relaxation, dynamic programming, and heuristics is developed. The method has been implemented using the object-oriented programming language C++, and numerical testing shows that the method generates high-quality schedules in a timely fashion to achieve on-time delivery of products and low inventory. Through explicit consideration of setups, tanks with the same processing requirements tend to be processed together to avoid excessive setups. The integrated treatment of machines and buffers facilitates the smooth flow of parts through the system. The embedded routing selection mechanism also balances the load among candidate routes. Finally, the newly developed "time step reduction technique" implicitly establishes two time scales to reduce computational requirements without much loss of modeling accuracy and scheduling performance, thereby enabling the resolution of long horizon problems with controllable computational requirements. More... »

PAGES

233-259

Identifiers

URI

http://scigraph.springernature.com/pub.10.1023/a:1018948621875

DOI

http://dx.doi.org/10.1023/a:1018948621875

DIMENSIONS

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


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": [
      {
        "familyName": "Luh", 
        "givenName": "Peter B.", 
        "id": "sg:person.01362072570.41", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01362072570.41"
        ], 
        "type": "Person"
      }, 
      {
        "familyName": "Gou", 
        "givenName": "Ling", 
        "id": "sg:person.07777333042.20", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07777333042.20"
        ], 
        "type": "Person"
      }, 
      {
        "familyName": "Zhang", 
        "givenName": "Yuanhui", 
        "id": "sg:person.016512702752.88", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016512702752.88"
        ], 
        "type": "Person"
      }, 
      {
        "familyName": "Nagahora", 
        "givenName": "Takaaki", 
        "id": "sg:person.014360176042.73", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014360176042.73"
        ], 
        "type": "Person"
      }, 
      {
        "familyName": "Tsuji", 
        "givenName": "Makoto", 
        "id": "sg:person.016550517442.70", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016550517442.70"
        ], 
        "type": "Person"
      }, 
      {
        "familyName": "Yoneda", 
        "givenName": "Kiyoshi", 
        "id": "sg:person.011440407242.05", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011440407242.05"
        ], 
        "type": "Person"
      }, 
      {
        "familyName": "Hasegawa", 
        "givenName": "Tetsuo", 
        "id": "sg:person.013630730642.10", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013630730642.10"
        ], 
        "type": "Person"
      }, 
      {
        "familyName": "Kyoya", 
        "givenName": "Yuji", 
        "id": "sg:person.010002506045.85", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010002506045.85"
        ], 
        "type": "Person"
      }, 
      {
        "familyName": "Kano", 
        "givenName": "Toshiyuki", 
        "id": "sg:person.010711142042.60", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010711142042.60"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "https://doi.org/10.1080/05695558308974639", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1010918114"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0895-7177(96)00073-8", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1011522709"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0305-0548(93)e0021-k", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1013627176"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1080/00207549408957019", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1018367459"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1080/00207548208947793", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1022878288"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1080/05695557708975171", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1028924693"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0736-5845(89)90031-8", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1033102873"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0736-5845(89)90031-8", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1033102873"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1080/00207549508904867", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1039149035"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1080/00207547708943117", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1049127114"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/9.231461", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1061243376"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1287/mnsc.33.1.39", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1064720238"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1287/opre.23.1.118", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1064728570"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1541/ieejeiss1987.112.9_568", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1084872873"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "1998-01", 
    "datePublishedReg": "1998-01-01", 
    "description": "Scheduling is a key factor for manufacturing productivity. Effective scheduling can improve on-time delivery of products, reduce inventory, cut lead times, and improve the utilization of bottleneck resources. This study was motivated by the design and implementation of a scheduling system for the manufacturing of Toshiba's gas insulated switchgears. The manufacturing is characterized by significant machine setup times, strict local buffer capacities, the option of choosing a few alternative processing routes, and long horizon as compared to the time resolution required. This problem has been recognized to be extremely difficult because of the combinatorial nature of integer optimization and the large size of the real problem. Our goal is thus to obtain near-optimal schedules with quantifiable quality in a computationally efficient manner. To achieve this goal, a novel integer optimization formulation with a separable structure is developed, and a solution methodology based on a combined Lagrangian relaxation, dynamic programming, and heuristics is developed. The method has been implemented using the object-oriented programming language C++, and numerical testing shows that the method generates high-quality schedules in a timely fashion to achieve on-time delivery of products and low inventory. Through explicit consideration of setups, tanks with the same processing requirements tend to be processed together to avoid excessive setups. The integrated treatment of machines and buffers facilitates the smooth flow of parts through the system. The embedded routing selection mechanism also balances the load among candidate routes. Finally, the newly developed \"time step reduction technique\" implicitly establishes two time scales to reduce computational requirements without much loss of modeling accuracy and scheduling performance, thereby enabling the resolution of long horizon problems with controllable computational requirements.", 
    "genre": "research_article", 
    "id": "sg:pub.10.1023/a:1018948621875", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": false, 
    "isPartOf": [
      {
        "id": "sg:journal.1048429", 
        "issn": [
          "0254-5330", 
          "1572-9338"
        ], 
        "name": "Annals of Operations Research", 
        "type": "Periodical"
      }, 
      {
        "issueNumber": "0", 
        "type": "PublicationIssue"
      }, 
      {
        "type": "PublicationVolume", 
        "volumeNumber": "76"
      }
    ], 
    "name": "Job shop scheduling with group-dependent setups, finite buffers, and long time horizon", 
    "pagination": "233-259", 
    "productId": [
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "32c6b8cf6d7b5c4b8f562cac88249c272ac18c90af230db0fef65dfb0ee58981"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1023/a:1018948621875"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1010657916"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1023/a:1018948621875", 
      "https://app.dimensions.ai/details/publication/pub.1010657916"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2019-04-10T16: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_8669_00000503.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "http://link.springer.com/10.1023%2FA%3A1018948621875"
  }
]
 

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.1023/a:1018948621875'

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.1023/a:1018948621875'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1023/a:1018948621875'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1023/a:1018948621875'


 

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

144 TRIPLES      21 PREDICATES      40 URIs      19 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1023/a:1018948621875 schema:about anzsrc-for:01
2 anzsrc-for:0103
3 schema:author N52572f349c604809bbab8ad14be02262
4 schema:citation https://doi.org/10.1016/0305-0548(93)e0021-k
5 https://doi.org/10.1016/0736-5845(89)90031-8
6 https://doi.org/10.1016/0895-7177(96)00073-8
7 https://doi.org/10.1080/00207547708943117
8 https://doi.org/10.1080/00207548208947793
9 https://doi.org/10.1080/00207549408957019
10 https://doi.org/10.1080/00207549508904867
11 https://doi.org/10.1080/05695557708975171
12 https://doi.org/10.1080/05695558308974639
13 https://doi.org/10.1109/9.231461
14 https://doi.org/10.1287/mnsc.33.1.39
15 https://doi.org/10.1287/opre.23.1.118
16 https://doi.org/10.1541/ieejeiss1987.112.9_568
17 schema:datePublished 1998-01
18 schema:datePublishedReg 1998-01-01
19 schema:description Scheduling is a key factor for manufacturing productivity. Effective scheduling can improve on-time delivery of products, reduce inventory, cut lead times, and improve the utilization of bottleneck resources. This study was motivated by the design and implementation of a scheduling system for the manufacturing of Toshiba's gas insulated switchgears. The manufacturing is characterized by significant machine setup times, strict local buffer capacities, the option of choosing a few alternative processing routes, and long horizon as compared to the time resolution required. This problem has been recognized to be extremely difficult because of the combinatorial nature of integer optimization and the large size of the real problem. Our goal is thus to obtain near-optimal schedules with quantifiable quality in a computationally efficient manner. To achieve this goal, a novel integer optimization formulation with a separable structure is developed, and a solution methodology based on a combined Lagrangian relaxation, dynamic programming, and heuristics is developed. The method has been implemented using the object-oriented programming language C++, and numerical testing shows that the method generates high-quality schedules in a timely fashion to achieve on-time delivery of products and low inventory. Through explicit consideration of setups, tanks with the same processing requirements tend to be processed together to avoid excessive setups. The integrated treatment of machines and buffers facilitates the smooth flow of parts through the system. The embedded routing selection mechanism also balances the load among candidate routes. Finally, the newly developed "time step reduction technique" implicitly establishes two time scales to reduce computational requirements without much loss of modeling accuracy and scheduling performance, thereby enabling the resolution of long horizon problems with controllable computational requirements.
20 schema:genre research_article
21 schema:inLanguage en
22 schema:isAccessibleForFree false
23 schema:isPartOf N451ff1a3d534485ebbfeae0d8dc7c48e
24 N64d725664b394315b951da82c8f5ca42
25 sg:journal.1048429
26 schema:name Job shop scheduling with group-dependent setups, finite buffers, and long time horizon
27 schema:pagination 233-259
28 schema:productId N253b2b95c85f4cb38d4b0d8882a236f4
29 N4a4bf8be6254407994e68d2d48c401ea
30 Nfc93fd1b0f5041f3a475326290d6e78c
31 schema:sameAs https://app.dimensions.ai/details/publication/pub.1010657916
32 https://doi.org/10.1023/a:1018948621875
33 schema:sdDatePublished 2019-04-10T16:40
34 schema:sdLicense https://scigraph.springernature.com/explorer/license/
35 schema:sdPublisher Nf03697c3ca314096abcb57a86d28681a
36 schema:url http://link.springer.com/10.1023%2FA%3A1018948621875
37 sgo:license sg:explorer/license/
38 sgo:sdDataset articles
39 rdf:type schema:ScholarlyArticle
40 N253b2b95c85f4cb38d4b0d8882a236f4 schema:name doi
41 schema:value 10.1023/a:1018948621875
42 rdf:type schema:PropertyValue
43 N3f331c38ebf944d0bb4ecbd84592c593 rdf:first sg:person.011440407242.05
44 rdf:rest N8a694cc9be1146dcbe6302817e91f6db
45 N411e9ef1a9e0428faa86dcdbf2094898 rdf:first sg:person.016512702752.88
46 rdf:rest Na60900f2b00f4c2fb1f7547043fb6f83
47 N451ff1a3d534485ebbfeae0d8dc7c48e schema:issueNumber 0
48 rdf:type schema:PublicationIssue
49 N4a4bf8be6254407994e68d2d48c401ea schema:name dimensions_id
50 schema:value pub.1010657916
51 rdf:type schema:PropertyValue
52 N4f6f8fa2f8e34045ab3f7a3de8939ceb rdf:first sg:person.010002506045.85
53 rdf:rest N8b7ee77b19844ecea7029167ce2ba6fd
54 N51637f3fbfcf4e16b5d08d0387de4f26 rdf:first sg:person.07777333042.20
55 rdf:rest N411e9ef1a9e0428faa86dcdbf2094898
56 N52572f349c604809bbab8ad14be02262 rdf:first sg:person.01362072570.41
57 rdf:rest N51637f3fbfcf4e16b5d08d0387de4f26
58 N64d725664b394315b951da82c8f5ca42 schema:volumeNumber 76
59 rdf:type schema:PublicationVolume
60 N8a694cc9be1146dcbe6302817e91f6db rdf:first sg:person.013630730642.10
61 rdf:rest N4f6f8fa2f8e34045ab3f7a3de8939ceb
62 N8b7ee77b19844ecea7029167ce2ba6fd rdf:first sg:person.010711142042.60
63 rdf:rest rdf:nil
64 N8e458de3e93a49b3ab5b2696e227858d rdf:first sg:person.016550517442.70
65 rdf:rest N3f331c38ebf944d0bb4ecbd84592c593
66 Na60900f2b00f4c2fb1f7547043fb6f83 rdf:first sg:person.014360176042.73
67 rdf:rest N8e458de3e93a49b3ab5b2696e227858d
68 Nf03697c3ca314096abcb57a86d28681a schema:name Springer Nature - SN SciGraph project
69 rdf:type schema:Organization
70 Nfc93fd1b0f5041f3a475326290d6e78c schema:name readcube_id
71 schema:value 32c6b8cf6d7b5c4b8f562cac88249c272ac18c90af230db0fef65dfb0ee58981
72 rdf:type schema:PropertyValue
73 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
74 schema:name Mathematical Sciences
75 rdf:type schema:DefinedTerm
76 anzsrc-for:0103 schema:inDefinedTermSet anzsrc-for:
77 schema:name Numerical and Computational Mathematics
78 rdf:type schema:DefinedTerm
79 sg:journal.1048429 schema:issn 0254-5330
80 1572-9338
81 schema:name Annals of Operations Research
82 rdf:type schema:Periodical
83 sg:person.010002506045.85 schema:familyName Kyoya
84 schema:givenName Yuji
85 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010002506045.85
86 rdf:type schema:Person
87 sg:person.010711142042.60 schema:familyName Kano
88 schema:givenName Toshiyuki
89 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010711142042.60
90 rdf:type schema:Person
91 sg:person.011440407242.05 schema:familyName Yoneda
92 schema:givenName Kiyoshi
93 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011440407242.05
94 rdf:type schema:Person
95 sg:person.01362072570.41 schema:familyName Luh
96 schema:givenName Peter B.
97 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01362072570.41
98 rdf:type schema:Person
99 sg:person.013630730642.10 schema:familyName Hasegawa
100 schema:givenName Tetsuo
101 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013630730642.10
102 rdf:type schema:Person
103 sg:person.014360176042.73 schema:familyName Nagahora
104 schema:givenName Takaaki
105 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014360176042.73
106 rdf:type schema:Person
107 sg:person.016512702752.88 schema:familyName Zhang
108 schema:givenName Yuanhui
109 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016512702752.88
110 rdf:type schema:Person
111 sg:person.016550517442.70 schema:familyName Tsuji
112 schema:givenName Makoto
113 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016550517442.70
114 rdf:type schema:Person
115 sg:person.07777333042.20 schema:familyName Gou
116 schema:givenName Ling
117 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07777333042.20
118 rdf:type schema:Person
119 https://doi.org/10.1016/0305-0548(93)e0021-k schema:sameAs https://app.dimensions.ai/details/publication/pub.1013627176
120 rdf:type schema:CreativeWork
121 https://doi.org/10.1016/0736-5845(89)90031-8 schema:sameAs https://app.dimensions.ai/details/publication/pub.1033102873
122 rdf:type schema:CreativeWork
123 https://doi.org/10.1016/0895-7177(96)00073-8 schema:sameAs https://app.dimensions.ai/details/publication/pub.1011522709
124 rdf:type schema:CreativeWork
125 https://doi.org/10.1080/00207547708943117 schema:sameAs https://app.dimensions.ai/details/publication/pub.1049127114
126 rdf:type schema:CreativeWork
127 https://doi.org/10.1080/00207548208947793 schema:sameAs https://app.dimensions.ai/details/publication/pub.1022878288
128 rdf:type schema:CreativeWork
129 https://doi.org/10.1080/00207549408957019 schema:sameAs https://app.dimensions.ai/details/publication/pub.1018367459
130 rdf:type schema:CreativeWork
131 https://doi.org/10.1080/00207549508904867 schema:sameAs https://app.dimensions.ai/details/publication/pub.1039149035
132 rdf:type schema:CreativeWork
133 https://doi.org/10.1080/05695557708975171 schema:sameAs https://app.dimensions.ai/details/publication/pub.1028924693
134 rdf:type schema:CreativeWork
135 https://doi.org/10.1080/05695558308974639 schema:sameAs https://app.dimensions.ai/details/publication/pub.1010918114
136 rdf:type schema:CreativeWork
137 https://doi.org/10.1109/9.231461 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061243376
138 rdf:type schema:CreativeWork
139 https://doi.org/10.1287/mnsc.33.1.39 schema:sameAs https://app.dimensions.ai/details/publication/pub.1064720238
140 rdf:type schema:CreativeWork
141 https://doi.org/10.1287/opre.23.1.118 schema:sameAs https://app.dimensions.ai/details/publication/pub.1064728570
142 rdf:type schema:CreativeWork
143 https://doi.org/10.1541/ieejeiss1987.112.9_568 schema:sameAs https://app.dimensions.ai/details/publication/pub.1084872873
144 rdf:type schema:CreativeWork
 




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


...