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 N2e82e8700d694feaba05086977cbacf5
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 N6ce09d56ff28480da4aa3ea50e8aebea
24 N7111d21fe16449c28ba38907f7adcb14
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 N066c26cb86604a95b60e4a00c544a7e1
29 N228c8419505b440d9428f73b7f2238b9
30 Nd82b1c5573ad43b6a926e51e6e3701d6
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 Nf236044644d04f5eb2c4adaa0fdac531
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 N02965b210e16442ebf5430ce77710e3a rdf:first sg:person.016512702752.88
41 rdf:rest N1ac128fff1f544fa88efb1b208f892ff
42 N066c26cb86604a95b60e4a00c544a7e1 schema:name doi
43 schema:value 10.1023/a:1018948621875
44 rdf:type schema:PropertyValue
45 N1ac128fff1f544fa88efb1b208f892ff rdf:first sg:person.014360176042.73
46 rdf:rest Nf3a4c6ca4c47451fa5546fc4221d883f
47 N1bed6733f3d74cf68ecd06bc9454efb0 rdf:first sg:person.07777333042.20
48 rdf:rest N02965b210e16442ebf5430ce77710e3a
49 N1de8397597f545faa72d91f59d536dd1 rdf:first sg:person.011440407242.05
50 rdf:rest N74b51414614b496a9d45b8feea13bd6d
51 N228c8419505b440d9428f73b7f2238b9 schema:name readcube_id
52 schema:value 32c6b8cf6d7b5c4b8f562cac88249c272ac18c90af230db0fef65dfb0ee58981
53 rdf:type schema:PropertyValue
54 N2e82e8700d694feaba05086977cbacf5 rdf:first sg:person.01362072570.41
55 rdf:rest N1bed6733f3d74cf68ecd06bc9454efb0
56 N6ce09d56ff28480da4aa3ea50e8aebea schema:issueNumber 0
57 rdf:type schema:PublicationIssue
58 N7111d21fe16449c28ba38907f7adcb14 schema:volumeNumber 76
59 rdf:type schema:PublicationVolume
60 N74b51414614b496a9d45b8feea13bd6d rdf:first sg:person.013630730642.10
61 rdf:rest N8cc9760abd844d27bcc0890ceb9344a7
62 N8cc9760abd844d27bcc0890ceb9344a7 rdf:first sg:person.010002506045.85
63 rdf:rest Ncc1c36bdf26144bd92abac1705fe1bfe
64 Ncc1c36bdf26144bd92abac1705fe1bfe rdf:first sg:person.010711142042.60
65 rdf:rest rdf:nil
66 Nd82b1c5573ad43b6a926e51e6e3701d6 schema:name dimensions_id
67 schema:value pub.1010657916
68 rdf:type schema:PropertyValue
69 Nf236044644d04f5eb2c4adaa0fdac531 schema:name Springer Nature - SN SciGraph project
70 rdf:type schema:Organization
71 Nf3a4c6ca4c47451fa5546fc4221d883f rdf:first sg:person.016550517442.70
72 rdf:rest N1de8397597f545faa72d91f59d536dd1
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)


...