nach oben

Journal of Scheduling

Erschienen in:

27.10.2020

Three-machine open shop with a bottleneck machine revisited

verfasst von: Inna G. Drobouchevitch

Erschienen in: Journal of Scheduling | Ausgabe 2/2021

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

The paper considers the three-machine open shop scheduling problem to minimize the makespan. In the model, each job consists of two operations, one of which is to be processed on the bottleneck machine, which is the same for all jobs. A new linear-time algorithm to find an optimal non-preemptive schedule is developed. The suggested algorithm considerably simplifies the only previously known method as it straightforwardly exploits the structure of the problem and its key components to yield an optimal solution.

Vorheriger Artikel Multiple dispatching rules allocation in real time using data mining, genetic algorithms, and simulation

Nächster Artikel Scheduling coupled tasks with exact delays for minimum total job completion time

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Aksjonov, V. A. (1988). A polynomial-time algorithm of approximate solution of a scheduling problem. Upravlyaemye Sistemy, 28, 8–11. (in Russian).

Bárány, I., & Fiala, T. (1982). Nearly optimum solution of multimachine scheduling problems. Szigma, 15, 177–191. (in Hungarian).

Chen, B., & Strusevich, V. A. (1993). Approximation algorithms for three machine open shop scheduling. ORSA Journal on Computing, 5, 321–328.CrossRef

Chen, B., & Yu, W. (2001). How good is a dense shop schedule? Acta Mathematics Application Sinica, 17(1), 121–128.CrossRef

Chen, R., Huang, W., Men, Z., & Tang, G. (2012). Open-shop dense schedules: Properties and worst-case performance ratio. Journal of Scheduling, 15(1), 3–11.CrossRef

de Werra, D. (1989). Graph-theoretical models for preemptive scheduling. In R. Slowinski & J. Weglarz (Eds.), Advances in project scheduling (pp. 171–185). Amsterdam: Elsevier.CrossRef

Drobouchevitch, I. G., & Strusevich, V. A. (1999). A polynomial algorithm for the three-machine open shop with a bottleneck machine. Annals of Operations Research, 92, 185–214.CrossRef

Gonzalez, T., & Sahni, S. (1976). Open shop scheduling to minimize finish time. Journal of the Association for Computing Machinery, 23, 665–679.CrossRef

Lawler, E. L., Lenstra, J. K., Rinnooy Kan, A. H. G., & Shmoys, D. B. (1993). Sequencing and scheduling: Algorithms and complexity. In S. C. Graves, et al. (Eds.), Handbook in operations research and management science (Vol. 4, pp. 445–522)., Logistics of production and inventory Amsterdam: North-Holland.

Pinedo, M., & Schrage, L. (1982). Stochastic shop scheduling: A survey. In M. A. H. Dempster, et al. (Eds.), Deterministic and stochastic scheduling (pp. 181–196). Dordrecht: Riedel.CrossRef

Sevastianov, S. V., & Woeginger, G. J. (1998). Makespan minimization in open shops: A polynomial time approximation scheme. Mathematical Programming, 82, 191–198.

Soper, A. J. (2015). A cyclical search for the two machine flow shop and open shop to minimise finishing time. Journal of Scheduling, 18(3), 311–314.CrossRef

Williamson, D. P., Hall, L. A., Hoogeveen, J. A., Hurkens, C. A. J., Lenstra, J. K., Sevast’janov, S. V., et al. (1997). Short shop schedules. Operations Research, 45, 288–294.CrossRef

Titel: Three-machine open shop with a bottleneck machine revisited
verfasst von: Inna G. Drobouchevitch
Publikationsdatum: 27.10.2020
Verlag: Springer US
Erschienen in: Journal of Scheduling / Ausgabe 2/2021
Print ISSN: 1094-6136
Elektronische ISSN: 1099-1425
DOI: https://doi.org/10.1007/s10951-020-00652-9

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Weitere Artikel der Ausgabe 2/2021

Multiple dispatching rules allocation in real time using data mining, genetic algorithms, and simulation

Coupled task scheduling with time-dependent processing times

Approximate and robust bounded job start scheduling for Royal Mail delivery offices

Stochastic programming approach for unidirectional quay crane scheduling problem with uncertainty

Scheduling coupled tasks with exact delays for minimum total job completion time

Cyclic lot-sizing problems with sequencing costs