nach oben

Journal of Scheduling

Erschienen in:

11.12.2017

Parallel machine makespan minimization subject to machine availability and total completion time constraints

verfasst von: Yumei Huo

Erschienen in: Journal of Scheduling | Ausgabe 4/2019

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

In this paper, we study the parallel machine scheduling subject to machine availability constraint. The jobs can be resumed after being preempted by another job or interrupted by the unavailable intervals. The goal is to minimize the makespan subject to the constraint that the total completion time is minimized. We study two different machine unavailability models. In the first model, each machine has a single unavailable interval which starts from time 0. In the second model, each machine can have multiple unavailable intervals, but at any time, there is at most one machine unavailable. For each model, we show that there is an optimal polynomial time algorithm.

Vorheriger Artikel Preemptive parallel-machine scheduling problem of maximizing the number of on-time jobs

Nächster Artikel Unbounded parallel-batch scheduling with drop-line tasks

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

Aslam, J., Rasala, A., Stein, C. & Young, N. (1999). Improved bicriteria existence theorems for scheduling, In Proceedings of the tenth annual ACM-SIAM symposium on discrete algorithms, pp. 846–847.

Chen, C. L., & Bulfin, R. L. (1993). Complexity of single machine, multicriteria scheduling problems. European Journal of Operational Research, 70, 115–125.CrossRef

Dileepan, P., & Sen, T. (1988). Bicriteria static scheduling research for a single machine. OMEGA, 16, 53–59.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.CrossRef

Gupta, J. N. D., Ho, J. C., & Webster, S. (2000). Bicriteria optimisation of the makespan and mean flowtime on two identical parallel machines. Journal of Operational Research Society, 51(11), 1330–1339.CrossRef

Hoogeveen, J. A. (2005). Multicriteria scheduling. European Journal of Operational Research, 167(3), 592–623.CrossRef

Huo, Y. (2014). Makespan minimization on multiple machines subject to machine unavailability and total completion time constraints. In The tenth international conference on algorithmic aspects of information and management (AAIM 2014). Lecture notes in computer science (Vol. 8546, pp. 56–65).

Huo, Y., & Zhao, H. (2011). Bicriteria scheduling concerned with makespan and total completion time subject to machine availability constraints. Theoretical Computer Science, 412, 1081–1091.CrossRef

Huo, Y., & Zhao, H. (2015). Total completion time minimization on multiple machines subject to machine availability and makespan constraints. European Journal of Operational Research, 243(2), 547–554.CrossRef

Lee, C.-Y., & Liman, S. D. (1993). Capacitated two-parallel machine scheduling to minimize sum of job completion times. Discrete Applied Mathematics, 41, 211–222.CrossRef

Lenstra, J. K., Rinnooy Kan, A. H. G., & Brucker, P. (1977). Complexity of machine scheduling problems. Annals of Discrete Mathematics, 1, 343–362.CrossRef

Leung, J. Y.-T., & Pinedo, M. L. (2003). Minimizing total completion time on parallel machines with deadline constraints. SIAM Journal on Computing, 32, 1370–1388.CrossRef

Leung, J. Y.-T., & Pinedo, M. L. (2004). A note on the scheduling of parallel machines subject to breakdown and repair. Naval Research Logistics, 51, 60–72.CrossRef

Leung, J. Y.-T., & Young, G. H. (1989). Minimizing schedule length subject to minimum flow time. SIAM Journal on Computing, 18(2), 314–326.CrossRef

Liu, Z., & Sanlaville, E. (1995). Preemptive scheduling with variable profile, precedence constraints and due dates. Discrete Applied Mathematics, 58, 253–280.CrossRef

Ma, Y., Chu, C., & Zuo, C. (2010). A survey of scheduling with deterministic machine availability constraints. Computers & Industrial Engineering, 58(2), 199–211.CrossRef

McNaughton, R. (1959). Scheduling with deadlines and loss functions. Management Science, 6(1), 1–12.CrossRef

Panwalkar, S. S., Dudek, R. K., & Smith, M. L. (1973). Sequencing research and the industrial scheduling problem. In S. E. Elmaghraby (Ed.), Proceedings of the symposium on the theory of scheduling and its application (pp. 29–38). New York: Springer.

Pinedo, M. (2012). Scheduling: Theory, models and algorithms (4th ed.). New York: Springer.CrossRef

Saidy, H., & Taghvi-Fard, M. (2008). Study of scheduling problems with machine availability constraint. Journal of Industrial and Systems Engineering, 1(4), 360–383.

Sanlaville, E., & Schmidt, G. (1998). Machine scheduling with availability constraints. Acta Informatica, 35, 795–811.CrossRef

Schmidt, G. (2000). Scheduling with limited machine availability. European Journal of Operational Research, 121(1), 1–15.CrossRef

Stein, C., & Wein, J. (1997). On the existence of schedules that are near-optimal for both makespan and total weighted completion time. Operations Research Letters, 21(3), 115–122.CrossRef

T’kindt, V., & Billaut, J. C. (2002). Multicriteria scheduling: Theory, models and algorithms. Heidelberg: Springer.CrossRef

Titel: Parallel machine makespan minimization subject to machine availability and total completion time constraints
verfasst von: Yumei Huo
Publikationsdatum: 11.12.2017
Verlag: Springer US
Erschienen in: Journal of Scheduling / Ausgabe 4/2019
Print ISSN: 1094-6136
Elektronische ISSN: 1099-1425
DOI: https://doi.org/10.1007/s10951-017-0551-z

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 4/2019

Unbounded parallel-batch scheduling with drop-line tasks

Quality of strong equilibria for selfish bin packing with uniform cost sharing

The single-processor scheduling problem with time restrictions: complexity and related problems

Lower bounds for online bin covering-type problems

Malleable scheduling for flows of jobs and applications to MapReduce

Preemptive parallel-machine scheduling problem of maximizing the number of on-time jobs

Premium Partner