nach oben

Journal of Scheduling

Erschienen in:

22.04.2016

Improved approaches to the exact solution of the machine covering problem

verfasst von: Rico Walter, Martin Wirth, Alexander Lawrinenko

Erschienen in: Journal of Scheduling | Ausgabe 2/2017

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

For the basic problem of scheduling a set of n independent jobs on a set of m identical parallel machines with the objective of maximizing the minimum machine completion time—also referred to as machine covering—we propose a new exact branch-and-bound algorithm. Its most distinctive components are a different symmetry-breaking solution representation, enhanced lower and upper bounds, and effective novel dominance criteria derived from structural patterns of optimal schedules. Results of a comprehensive computational study conducted on benchmark instances attest to the effectiveness of our approach, particularly for small ratios of n to m.

Vorheriger Artikel Scheduling of multi-class multi-server queueing systems with abandonments

Nächster Artikel A hybrid multi-objective immune algorithm for predictive and reactive scheduling

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

Nur mit Berechtigung zugänglich

Ahuja, R. K., & Orlin, J. B. (2001). Inverse optimization. Operations Research, 49, 771–783.CrossRef

Alvim, A. C. F., Ribeiro, C. C., Glover, F., & Aloise, D. J. (2004). A hybrid improvement heuristic for the one-dimensional bin packing problem. Journal of Heuristics, 10, 205–229.CrossRef

Azar, Y., & Epstein, L. (1998). On-line machine covering. Journal of Scheduling, 1, 67–77.CrossRef

Brucker, P., & Shakhlevich, N. V. (2009). Inverse scheduling with maximum lateness objective. Journal of Scheduling, 12, 475–488.CrossRef

Brucker, P., & Shakhlevich, N. V. (2011). Inverse scheduling: Two-machine flow-shop problem. Journal of Scheduling, 14, 239–256.CrossRef

Cai, S.-Y. (2007). Semi-online machine covering. Asia-Pacific Journal of Operational Research, 24, 373–382.CrossRef

Csirik, J., Kellerer, H., & Woeginger, G. (1992). The exact LPT-bound for maximizing the minimum completion time. Operations Research Letters, 11, 281–287.CrossRef

Dell’Amico, M., & Martello, S. (1995). Optimal scheduling of tasks on identical parallel processors. ORSA Journal on Computing, 7, 191–200.CrossRef

Deuermeyer, B. L., Friesen, D. K., & Langston, M. A. (1982). Scheduling to maximize the minimum processor finish time in a multiprocessor system. SIAM Journal on Algebraic and Discrete Methods, 3, 190–196.CrossRef

Ebenlendr, T., Noga, J., Sgall, J., & Woeginger, G. (2006). A note on semi-online machine covering. In T. Erlebach & G. Persiano (Eds.), Approximation and online algorithms. Lecture Notes in Computer Science (Vol. 3879, pp. 110–118). Berlin: Springer.CrossRef

Epstein, L., Levin, A., & van Stee, R. (2011). Max-min online allocations with a reordering buffer. SIAM Journal on Discrete Mathematics, 25, 1230–1250.CrossRef

França, P. M., Gendreau, M., Laporte, G., & Müller, F. M. (1994). A composite heuristic for the identical parallel machine scheduling problem with minimum makespan objective. Computers & Operations Research, 21, 205–210.CrossRef

Frangioni, A., Necciari, E., & Scutellà, M. G. (2004). A multi-exchange neighborhood for minimum makespan parallel machine scheduling problems. Journal of Combinatorial Optimization, 8, 195–220.CrossRef

Friesen, D. K., & Deuermeyer, B. L. (1981). Analysis of greedy solutions for a replacement part sequencing problem. Mathematics of Operations Research, 6, 74–87.CrossRef

Graham, R. L. (1969). Bounds on multiprocessing timing anomalies. SIAM Journal on Applied Mathematics, 17, 416–429.CrossRef

Graham, R. L., Lawler, E. L., Lenstra, J. K., & Rinnooy Kan, A. H. G. (1979). Optimization and approximation in deterministic sequencing and scheduling: A survey. Annals of Discrete Mathematics, 5, 287–326.

Haouari, M., & Jemmali, M. (2008). Maximizing the minimum completion time on parallel machines. 4OR: A Quarterly Journal of Operations Research, 6, 375–392.CrossRef

He, Y., & Tan, Z. Y. (2002). Ordinal on-line scheduling for maximizing the minimum machine completion time. Journal of Combinatorial Optimization, 6, 199–206.CrossRef

Heuberger, C. (2004). Inverse combinatorial optimization: A survey on problems, methods, and results. Journal of Combinatorial Optimization, 8, 329–361.CrossRef

Koulamas, C. (2005). Inverse scheduling with controllable job parameters. International Journal of Services and Operations Management, 1, 35–43.CrossRef

Labbé, M., Laporte, G., & Martello, S. (1995). An exact algorithm for the dual bin packing problem. Operations Research Letters, 17, 9–18.CrossRef

Luo, R.-Z., & Sun, S.-J. (2005). Semi on-line scheduling problem for maximizing the minimum machine completion time on \(m\) identical machines. Journal of Shanghai University, 9, 99–102.CrossRef

Peeters, M., & Degraeve, Z. (2006). Branch-and-price algorithms for the dual bin packing and maximum cardinality bin packing problem. European Journal of Operational Research, 170, 416–439.CrossRef

Tan, Z., & Wu, Y. (2007). Optimal semi-online algorithms for machine covering. Theoretical Computer Science, 372, 69–80.CrossRef

Walter, R. (2013). Comparing the minimum completion times of two longest-first scheduling-heuristics. Central European Journal of Operations Research, 21, 125–139.CrossRef

Walter, R., & Lawrinenko, A. (2014). Effective solution space limitation for the identical parallel machine scheduling problem. Working Paper. http://s.fhg.de/WrkngPprRW.

Woeginger, G. J. (1997). A polynomial-time approximation scheme for maximizing the minimum machine completion time. Operations Research Letters, 20, 149–154.CrossRef

Titel: Improved approaches to the exact solution of the machine covering problem
verfasst von: Rico Walter
Martin Wirth
Alexander Lawrinenko
Publikationsdatum: 22.04.2016
Verlag: Springer US
Erschienen in: Journal of Scheduling / Ausgabe 2/2017
Print ISSN: 1094-6136
Elektronische ISSN: 1099-1425
DOI: https://doi.org/10.1007/s10951-016-0477-x

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/2017

Preemptive scheduling on uniformly related machines: minimizing the sum of the largest pair of job completion times

A hybrid multi-objective immune algorithm for predictive and reactive scheduling

Scheduling jobs and maintenance activities subject to job-dependent machine deteriorations

Batched bin packing revisited

Scheduling of multi-class multi-server queueing systems with abandonments

Unary NP-hardness of minimizing the number of tardy jobs with deadlines

Premium Partner