nach oben

Journal of Scheduling

Erschienen in:

21.02.2020

Single-machine scheduling with multi-agents to minimize total weighted late work

verfasst von: Shi-Sheng Li, Jin-Jiang Yuan

Erschienen in: Journal of Scheduling | Ausgabe 4/2020

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

We consider the competitive multi-agent scheduling problem on a single machine, where each agent’s cost function is to minimize its total weighted late work. The aim is to find the Pareto-optimal frontier, i.e., the set of all Pareto-optimal points. When the number of agents is arbitrary, the decision problem is shown to be unary \(\mathcal {NP}\)-complete even if all jobs have the unit weights. When the number of agents is two, the decision problems are shown to be binary \(\mathcal {NP}\)-complete for the case in which all jobs have the common due date and the case in which all jobs have the unit processing times. When the number of agents is a fixed constant, a pseudo-polynomial dynamic programming algorithm and a \((1+\epsilon )\)-approximate Pareto-optimal frontier are designed to solve it.

Vorheriger Artikel Mixed batch scheduling on identical machines

Nächster Artikel Benders decomposition for the mixed no-idle permutation flowshop scheduling 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

Nur mit Berechtigung zugänglich

Agnetis, A., Billaut, J. C., Gawiejnowicz, S., Pacciarelli, D., & Souhal, A. (2014). Multiagent scheduling: Models and algorithms. Berlin: Springer.CrossRef

Agnetis, A., Mirchandani, P. B., Pacciarelli, D., & Pacifici, A. (2004). Scheduling problems with two competing agents. Operations Research, 52, 229–242.CrossRef

Agnetis, A., Pacciarelli, D., & Pacifici, A. (2007). Multi-agent single machine scheduling. Annals of Operations Research, 150, 3–15.CrossRef

Arbib, C., Smriglio, S., & Servilio, M. (2004). A competitive scheduling problem and its relevance to UMTS channel assignment. Networks, 44, 132–141.CrossRef

Baker, K. R., & Smith, J. C. (2003). A multiple-criterion model for machine scheduling. Journal of Scheduling, 6, 7–16.CrossRef

Blazewicz, J. (1984). Scheduling preemptible tasks on parallel processors with information loss. Technique et Science Informatiques, 3, 415–420.

Blazewicz, J., Pesch, E., Sterna, M., & Werner, F. (2004). Open shop scheduling problems with late work criteria. Discrete Applied Mathematics, 134, 1–24.CrossRef

Blazewicz, J., Pesch, E., Sterna, M., & Werner, F. (2005). The two-machine flow-shop problem with weighted late work criterion and common due date. European Journal of Operational Research, 165, 408–415.CrossRef

Blazewicz, J., Pesch, E., Sterna, M., & Werner, F. (2007). A note on two-machine job shop with weighted late work criterion. Journal of Scheduling, 10, 87–95.CrossRef

Chen, R. B., Yuan, J. J., & Gao, Y. (2019a). The complexity of CO-agent scheduling to minimize the total completion time and total number of tardy jobs. Journal of Scheduling, 22, 581–593.CrossRef

Chen, R. B., Yuan, J. J., Ng, C. T., & Cheng, T. C. E. (2019b). Single-machine scheduling with deadlines to minimize the total weighted late work. Naval Research Logistics, 66, 582–595.CrossRef

Chen, X., Chau, V., Xie, P., Sterna, M., & Blazewicz, J. (2017). Complexity of late work minimization in flow shop systems and a particle swarm optimization algorithm for learning effect. Computers and Industrial Engineering, 111, 176–182.CrossRef

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

Cheng, T. C. E., Ng, C. T., & Yuan, J. J. (2006). Multi-agent scheduling on a single machine to minimize total weighted number of tardy jobs. Theoretical Computer Science, 362, 273–281.CrossRef

Garey, M. R., & Johnson, D. S. (1979). Computers and intractability: A guide to the theory of \(\cal{NP}\)-completeness. San Francisco: Freeman.

Gerstl, E., Mor, B., & Mosheiov, G. (2019). Scheduling on a proportionate flowshop to minimize total late work. International Journal of Production Research, 57, 531–543.CrossRef

Hariri, A. M. A., Potts, C. N., & Van Wassenhove, L. N. (1995). Single machine scheduling to minimize total late work. ORSA Journal on Computing, 7, 232–242.CrossRef

Kovalyov, M. Y., Oulamara, A., & Soukhal, A. (2015). Two-agent scheduling with agent specific batches on an unbounded serial batching machine. Journal of Scheduling, 18, 423–434.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, 86–93.CrossRef

Lee, K., Choi, B. C., Leung, J. Y. T., & Pinedo, M. (2009). Approximation algorithms for multi-agent scheduling to minimize total weighted completion time. Information Processing Letters, 109, 913–917.CrossRef

Leung, J. Y. T. (2004). Minimizing total weighted error for imprecise computation tasks and related problems. In J. Y. Leung (Ed.), Handbook of scheduling: Algorithms, models, and performance analysis. Boca Raton: Chapman and Hall/CRC.

Leung, J. Y. T., Pinedo, M., & Wan, G. (2010). Competitive two-agent scheduling and its applications. Operations Research, 58, 458–469.CrossRef

Li, S. S., Chen, R. X., & Li, W. J. (2018). Proportionate flow shop scheduling with multi-agents to maximize total gains of JIT jobs. Arabian Journal for Science and Engineering, 43, 969–978.CrossRef

Liu, S. C., Duan, J., Lin, W. C., Wu, W. H., Kung, J. K., Chen, H., et al. (2018). A branch-and-bound algorithm for two-agent scheduling with learning effect and late work criterion. Asia-Pacific Journal of Operational Research, 35, 1850037.CrossRef

Ng, C. T., Cheng, T. C. E., & Yuan, J. J. (2006). A note on the complexity of the problem of two-agent scheduling on a single machine. Journal of Combinatorial Optimization, 12, 387–394.CrossRef

Oron, D., Shabtay, D., & Steiner, G. (2015). Single machine scheduling with two competing agents and equal job processing times. European Journal of Operational Research, 244, 86–99.CrossRef

Papadimitriou C, Yannakakis M (2000) On the approximability of trade-offs and optimal access of web sources. In Proceedings of the 41st annual IEEE symposium on the foundations of computer science (pp 86–92).

Perez-Gonzalez, P., & Framinan, J. M. (2014). A common framework and taxonomy for multicriteria scheduling problems with interfering and competing jobs: Multi-agent scheduling problems. European Journal of Operational Research, 235, 1–16.CrossRef

Piroozfard, H., Wong, K. Y., & Wong, W. P. (2018). Minimizing total carbon footprint and total late work criterion in flexible job shop scheduling by using an improved multi-objective genetic algorithm. Resources, Conservation and Recycling, 128, 267–283.CrossRef

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

Potts, C. N., & Van Wassenhove, L. N. (1992). Approximation algorithms for scheduling a single machine to minimize total late work. Operations Research Letters, 11, 261–266.CrossRef

Shioura, A., Shakhlevich, N. V., & Strusevich, V. A. (2018). Preemptive models of scheduling with controllable processing times and of scheduling with imprecise computation: A review of solution approaches. European Journal of Operational Research, 266, 795–818.CrossRef

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

Sterna, M., & Czerniachowska, K. (2017). Polynomial time approximation scheme for two parallel machines scheduling with a common due date to maximize early work. Journal of Optimization Theory and Applications, 174, 927–944.CrossRef

Wang, D. J., Kang, C. C., Shiau, Y. R., Wu, C. C., & Hsu, P. H. (2017). A two-agent single-machine scheduling problem with late work criteria. Soft Computing, 21, 2015–2033.CrossRef

Yin, Y., Wang, W., Wang, D., & Cheng, T. C. E. (2017). Multi-agent single-machine scheduling and unrestricted due date assignment with a fixed machine unavailability interval. Computers & Industrial Engineering, 111, 202–215.CrossRef

Yin, Y., Xu, J., Cheng, T. C. E., Wu, C. C., & Wang, D. J. (2016). Approximation schemes for single-machine scheduling with a fixed maintenance activity to minimize the total amount of late work. Naval Research Logistics, 63, 172–183.CrossRef

Yuan, J. J. (2016). Complexities of some problems on multi-agent scheduling on a single machine. Journal of the Operations Research Society of China, 4, 379–384.CrossRef

Yuan, J. J. (2017). Multi-agent scheduling on a single machine with a fixed number of competing agents to minimize the weighted sum of number of tardy jobs and makespans. Journal of Combinatorial Optimization, 34, 433–440.CrossRef

Yuan, J. J., Ng, C. T., & Cheng, T. C. E. (2020). Scheduling with release dates and preemption to minimize multiple max-form objective functions. European Journal of Operational Research, 280, 860–875.CrossRef

Zhang, X., & Wang, Y. (2017). Two-agent scheduling problems on a single-machine to minimize the total weighted late work. Journal of Combinatorial Optimization, 33, 945–955.CrossRef

Zhang, Y., & Yuan, J. J. (2019). A note on a two-agent scheduling problem related to the total weighted late work. Journal of Combinatorial Optimization, 37, 989–999.CrossRef

Titel: Single-machine scheduling with multi-agents to minimize total weighted late work
verfasst von: Shi-Sheng Li
Jin-Jiang Yuan
Publikationsdatum: 21.02.2020
Verlag: Springer US
Erschienen in: Journal of Scheduling / Ausgabe 4/2020
Print ISSN: 1094-6136
Elektronische ISSN: 1099-1425
DOI: https://doi.org/10.1007/s10951-020-00646-7

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

Benders decomposition for the mixed no-idle permutation flowshop scheduling problem

Interruptible algorithms for multiproblem solving

On the exact solution of a large class of parallel machine scheduling problems

An Efficient Filtering Algorithm for the Unary Resource Constraint with Transition Times and Optional Activities

Interference aware scheduling of triple-crossover-cranes

Mixed batch scheduling on identical machines

Premium Partner