nach oben

Journal of Scheduling

Erschienen in:

30.01.2020

Mirror scheduling problems with early work and late work criteria

verfasst von: Xin Chen, Sergey Kovalev, Małgorzata Sterna, Jacek Błażewicz

Erschienen in: Journal of Scheduling | Ausgabe 5/2021

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

We give a definition of a class of mirror scheduling problems, review existing representatives of this class and demonstrate that an identical parallel machine scheduling problem with precedence constraints and an upper bound on the makespan to minimize (maximize) the total weighted early work and the same problem with modified due dates, reversed precedence constraints and the objective function of minimizing (maximizing) the total weighted late work are mirror problems.

Vorheriger Artikel Scheduling periodic I/O access with bi-colored chains: models and algorithms

Nächster Artikel An approach to reduce energy consumption and performance losses on heterogeneous servers using power capping

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

Abasian, F., Ranjbar, M., Salari, M., Davari, M., & Khatami, S. M. (2014). Minimizing the total weighted late work in scheduling of identical parallel processors with communication delays. Applied Mathematical Modelling, 38(15–16), 3975–3986.CrossRef

Aloulou, M. A., Kovalyov, M. Y., & Portmann, M.-C. (2004). Maximization problems in single machine scheduling. Annals of Operations Research, 129(1–4), 21–32.CrossRef

Ben-Yehoshua, Y., & Mosheiov, G. (2016). A single machine scheduling problem to minimize total early work. Computers and Operations Research, 73, 115–118.CrossRef

Błażewicz, J. (1984). Scheduling preemptible tasks on parallel processors with information loss. Technique et Science Informatiques, 3(6), 415–420.

Chen, X., Sterna, M., Han, X., & Błażewicz, J. (2016). Scheduling on parallel identical machines with late work criterion: Offline and online cases. Journal of Scheduling, 19(6), 729–736.CrossRef

Cheng, T. C. E., & Ding, Q. (1998). The complexity of scheduling starting time dependent tasks with release times. Information Processing Letters, 65(2), 75–79.CrossRef

Cheng, T. C. E., Ding, Q., & Lin, B. M. T. (2004). A concise survey of scheduling with time-dependent processing times. European Journal of Operational Research, 152(1), 1–13.CrossRef

Du, J., & Leung, J. Y.-T. (1990). Minimizing total tardiness on one machine is NP-hard. Mathematics of Operations Research, 15(3), 483–495.CrossRef

Gafarov, E. R., Lazarev, A. A., & Werner, F. (2012). Transforming a pseudo-polynomial algorithm for the single machine total tardiness maximization problem into a polynomial one. Annals of Operations Research, 196(1), 247–261.CrossRef

Hardy, G. H., Littlewood, J. E., & Pólya, G. (1934). Inequalities. Cambridge: Cambridge University Press.

Janiak, A., Kovalyov, M. Y., & Marek, M. (2007). Soft due window assignment and scheduling on parallel machines. IEEE Transactions on Systems, Man and Cybernetics-Part A: Systems and Humans, 37(5), 614–620.CrossRef

Koulamas, C. (2015). A note on scheduling problems with competing agents and earliness minimization objectives. European Journal of Operational Research, 245(3), 875–876.CrossRef

Kovalyov, M. Y., Potts, C. N., & Van Wassenhove, L. N. (1994). A fully polynomial approximation scheme for scheduling a single machine to minimize total weighted late work. Mathematics of Operations Research, 19(1), 86–93.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, A. H. G. RinnooyKan, & P. H. Zipkin (Eds.), Logistics of production and inventory. Handbook in operations research and management science (Vol. 4, pp. 445–452). Amsterdam: Elsevier.CrossRef

Martello, S., & Toth, P. (1990). Knapsack problems: Algorithms and computer implementation. New York, NY: Wiley.

Potts, C. N., & Van Wassenhove, L. N. (1992). Single machine scheduling to minimize total late work. Operations Research, 40(3), 586–595.CrossRef

Ranjbar, M., Hosseinabadi, S., & Abasian, F. (2013). Minimizing total weighted late work in the resource-constrained project scheduling problem. Applied Mathematical Modelling, 37(23), 9776–9785.CrossRef

Sterna, M. (2011). A survey of scheduling problems with late work criteria. Omega, 39(2), 120–129.CrossRef

Tadei, R., Gupta, J. N. D., Della Croce, F., & Cortesi, M. (1998). Minimizing makespan in the two-machine flow-shop with release times. Journal of the Operational Research Society, 49(5–6), 77–85.CrossRef

Xu, Z., Zou, Y., & Kong, X. (2015). Metaheuristic algorithms for parallel identical machines scheduling problem with weighted late work criterion and common due date. SpringerPlus, 24(782), 1–13.

Titel: Mirror scheduling problems with early work and late work criteria
verfasst von: Xin Chen
Sergey Kovalev
Małgorzata Sterna
Jacek Błażewicz
Publikationsdatum: 30.01.2020
Verlag: Springer US
Erschienen in: Journal of Scheduling / Ausgabe 5/2021
Print ISSN: 1094-6136
Elektronische ISSN: 1099-1425
DOI: https://doi.org/10.1007/s10951-020-00636-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 5/2021

Scheduling periodic I/O access with bi-colored chains: models and algorithms

Scheduling divisible loads with time and cost constraints

Calibrations scheduling with arbitrary lengths and activation length

Stand-alone renewable power system scheduling for a green data center using integer linear programming

A new LP rounding algorithm for the active time problem

New Perspectives in Scheduling Theory