nach oben

Journal of Scheduling

Erschienen in:

01.02.2016

A polynomial-time algorithm for the preemptive mixed-shop problem with two unit operations per job

verfasst von: Aldar Dugarzhapov, Alexander Kononov

Erschienen in: Journal of Scheduling | Ausgabe 1/2016

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

In a so-called mixed-shop scheduling problem, the operations of some jobs have to be processed in a fixed order (as in the job-shop problem); the other ones can be processed in an arbitrary order (as in the open-shop problem). In this paper we present a new exact polynomial-time algorithm for the mixed-shop problems with preemptions and at most two unit operations per job.

Vorheriger Artikel A genetic algorithm for the robust resource leveling problem

Nächster Artikel A graph coloring approach to the deployment scheduling and unit assignment problem

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

Baptiste, P., & Timkovsky, V. G. (2001). On preemption redundancy in scheduling unit processing time jobs on two parallel machines. Operations Research Letters, 28, 205–212.CrossRef

Brucker, P., Heitmann, S., & Hurink, J. (2003). How useful are preemptive schedules? Operations Research Letters, 31(2), 129–136.CrossRef

Cole, R., Ost, K., & Schirra, K. (2001). Edge-coloring bipartite multigraphs in \(O(E \log D)\) time. Combinatorica, 21, 5–12.CrossRef

Conway, R. W. W., Maxwell, L., & Miller, L. W. (1967). Theory of scheduling. Reading: Addison-Wesley.

Gabow, H., & Kariv, O. (1982). Algorithms for edge coloring bipartite graphs and multigraphs. SIAM Journal of Computing, 11, 117–129.CrossRef

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

Kononov, A., Sevastyanov, S., & Sviridenko, M. (2012). Complete complexity classification of short shop scheduling. Journal of Scheduling, 15, 427–446.CrossRef

König, D. (1916). Graphok és alkalmazásuk a determinánsok és a halmazok elméletére, [Hungarian] Mathematikai és Természettudományi Értesitö 34, (1916), 104–119. [German translation: Über Graphen und ihre Anwendung auf Determinantentheorie und Mengenlehre. Mathematische Annalen, 77, 453–465.

Lenstra, J. K., & Rinnooy Kan, A. H. G. (1979). Computational complexity of discrete optimization problems. Annals of Discrete Mathematics, 4, 121–140.

Leung, J. Y. T. (Ed.). (2004). Handbook of scheduling: Algorithms, models, and performance analysis. Boca Raton: Chapman & Hall/CRC Computer and Information Science Series.

Masuda, T., Ishii, H., & Nishida, T. (1985). The mixed shop scheduling problem. Discrete Applied Mathematics, 11(2), 175–186.CrossRef

Melnikov, L., & Vizing, V. (1999). The edge chromatic number of a directed/mixed multigraph. Journal Graph Theory, 31(4), 267–273.CrossRef

Pyatkin, A. (1999). Incidentor colorings and their applications. Ph. D. Thesis, in Russian.

Shakhlevich, N. V., & Sotskov, Y. N. (1994). Scheduling two jobs with fixed and non-fixed routines. Computing, 52, 17–30.CrossRef

Shakhlevich, N. V., Sotskov, Yu N, & Werner, F. (1999). Shop-scheduling problems with fixed and non-fixed orders of the jobs. Annals of Operations Research, 92, 281–304.CrossRef

Shakhlevich, N. V., Sotskov, Yu N, & Werner, F. (2000). Complexity of mixed shop scheduling problems: A survey. European Journal of Operational Research, 120, 387–397.CrossRef

Strusevich, V. A. (1989). On nonhomogeneous two-stage deterministic processing systems. Kibernetica, 3, 88–94. (in Russian).

Strusevich, V. A. (1991). Two machine super-shop scheduling problem. Journal of the Operational Research Society, 42(6), 479–492.CrossRef

Timkovsky, V. G. (2004). Reducibility among scheduling classes, Chapter 8. In J. Y.-T. Leung (Ed.), Handbook of scheduling: Algorithms, models, and performance analysis. Boca Raton: Chapman & Hall/CRC Computer and Information Science Series.

Vizing, V. (2002). A bipartite interpretation of a direct multigraph in problems of the coloring of incidentors Ser. 1. Diskretn. Anal. Issled. Oper., 9(1), 27–41.

Williamson, D., Hall, L., Hoogeveen, J., Hurkens, C., Lenstra, J. K., Sevastianov, S., & Shmoys, D. (1997). Short shop schedules. Operations Research, 45(2), 288–294.

Titel: A polynomial-time algorithm for the preemptive mixed-shop problem with two unit operations per job
verfasst von: Aldar Dugarzhapov
Alexander Kononov
Publikationsdatum: 01.02.2016
Verlag: Springer US
Erschienen in: Journal of Scheduling / Ausgabe 1/2016
Print ISSN: 1094-6136
Elektronische ISSN: 1099-1425
DOI: https://doi.org/10.1007/s10951-015-0454-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 1/2016

A graph coloring approach to the deployment scheduling and unit assignment problem

A mixed integer programming approach to multi-skilled workforce scheduling

Journal of Scheduling (2016)

A new approximation algorithm for multi-agent scheduling to minimize makespan on two machines

A survey of offline algorithms for energy minimization under deadline constraints

A genetic algorithm for the robust resource leveling problem

Premium Partner