nach oben

Journal of Scheduling

Erschienen in:

27.03.2023

Competitive two-agent scheduling with release dates and preemption on a single machine

verfasst von: Shi-Sheng Li, Ren-Xia Chen

Erschienen in: Journal of Scheduling | Ausgabe 3/2023

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

We study several competitive two-agent scheduling problems with release dates and preemption on a single machine, where the scheduling criterion of the first agent is regular and of the sum-form and the scheduling criterion of the second criterion is regular and of the max-form or the weighted number of tardy jobs. Two variants of the problems are investigated. One is the restricted version, in which the goal is to find a feasible schedule so that the objective value of the first agent is minimized subject to the restriction that the objective value of the second agent does not exceed a given threshold value. The other one is the Pareto version, in which the goal is to find all the Pareto-optimal points and their corresponding Pareto-optimal schedules. We design polynomial-time and pseudo-polynomial-time algorithms for each of the considered problems.

Nächster Artikel Optimization of scheduling problems with deterioration effects and an optional maintenance activity

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

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

Agnetis, A., Chen, B., Nicosia, G., & Pacifici, A. (2019). Price of fairness in two-agent single-machine scheduling problems. European Journal of Operational Research, 276, 79–87.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

Baker, K. R., Lawler, E. L., Lenstra, J. K., & Rinnooy Kan, A. H. G. (1983). Preemptive scheduling of a single machine to minimize maximum cost subject to release dates and precedence constraints. Operations Research, 31, 381–386.CrossRef

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

Baptiste, P. (1999). Polynomial time algorithms for minimizing the weighted number of late jobs on a single machine with equal processing times. Journal of Scheduling, 2, 245–252.CrossRef

Baptiste, P. (2000). Scheduling equal-length jobs on identical parallel machines. Discrete Applied Mathematics, 103, 21–32.CrossRef

Baptiste, P., Chrobak, M., Durr, C., Jawor, W., & Vakhania, N. (2004). Preemptive scheduling of equal-length jobs to maximize weighted throughput. Operations Research Letters, 32, 258–264.CrossRef

Brucker, P. (2007). Scheduling algorithms (5th ed.). Berlin: Springer.

Buttazzo, G. C. (2011). Hard real-time computing systems: Predictable scheduling algorithms and applications (3rd ed.). New York: Springer.CrossRef

Carlier, J. (1982). The one-machine sequencing problem. European Journal of Operational Research, 11, 42–47.CrossRef

Chen, R. B., Geng, Z. C., Lu, L. F., Yuan, J. J., & Zhang, Y. (2022). Pareto-scheduling of two competing agents with their own equal processing times. European Journal of Operational Research, 301, 414–431.CrossRef

Chen, R. B., Yuan, J. J., & Gao, Y. (2019). 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

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

Cheng, T. C. E., Ng, C. T., & Yuan, J. J. (2008). Multi-agent scheduling on a single machine with max-form criteria. European Journal of Operational Research, 188, 603–609.CrossRef

Ding, G., & Sun, S. (2010). Single-machine scheduling problems with two agents competing for makespan. Lecture Notes in Computer Science, 6328, 244–255.CrossRef

Dover, O., & Shabtay, D. (2016). Single machine scheduling with two competing agents, arbitrary release dates and unit processing times. Annals of Operations Research, 238, 145–178.CrossRef

Du, J., & Leung, J. Y. T. (1990). Minimizing total tardiness on one machine is \({{\cal{N} }}{{\cal{P} }}\)-hard. Mathematics of Operations Research, 15, 483–495.CrossRef

Elvikis, D., Hamacher, H. W., & T’kindt, V. (2011). Scheduling two agents on uniform parallel machines with makespan and cost functions. Journal of Scheduling, 14, 471–481.CrossRef

Elvikis, D., & T’kindt, V. (2014). Two-agent scheduling on uniform machines with min-max criteria. Annals of Operations Research, 213, 79–94.CrossRef

Gao, Y., Yuan, J. J., Ng, C. T., & Cheng, T. C. E. (2021). A note on competing-agent Pareto-scheduling. Optimization Letters, 15, 249–262.CrossRef

Geng, Z. C., & Yuan, J. J. (2015). Pareto optimization scheduling of family jobs on a p-batch machine to minimize makespan and maximum lateness. Theoretical Computer Science, 570, 22–29.CrossRef

Gupta, B. D., & Palis, M. A. (2001). Online real-time preemptive scheduling of jobs with deadlines on multiple machines. Journal of Scheduling, 4, 297–312.CrossRef

Han, J. W., Zuo, M., Zhu, W. Y., Zuo, J. H., Lü, E. L., & Yang, X. T. (2021). A comprehensive review of cold chain logistics for fresh agricultural products: Current status, challenges, and future trends. Trends in Food Science & Technology, 109, 536–551.CrossRef

He, R. Y., Yuan, J. J., Ng, C. T., & Cheng, T. C. E. (2021). Two-agent preemptive Pareto-scheduling to minimize the number of tardy jobs and total late work. Journal of Combinatorial Optimization, 41, 504–525.CrossRef

Hermelin, D., Kubitza, J. M., Shabtay, D., Talmon, N., & Woeginger, G. J. (2019). Scheduling two agents on a single machine: A parameterized analysis of NP-hard problems. Omega, 83, 275–286.CrossRef

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

Horn, W. A. (1974). Some simple scheduling algorithms. Naval Research Logistics Quarterly, 21, 177–185.CrossRef

Huynh-Tuong, N., Soukhal, A., & Billaut, J. C. (2012). Single-machine multi-agent scheduling problems with a global objective function. Journal of Scheduling, 15, 311–321.CrossRef

Karp, R. M. (1972). Reducibility among combinatorial problems. In R. E. Miller & J. W. Thatcher (Eds.), Complexity of computer computations. New York: Plenum Press.

Kellerer, H., & Strusevich, V. A. (2010). Fully polynomial approximation schemes for a symmetric quadratic knapsack problem and its scheduling applications. Algorithmica, 57, 769–795.CrossRef

Kovalyov, M. Y., & S̆es̆ok, D. (2019). Two-agent scheduling with deteriorating jobs on a single parallel-batching machine: Refining computational complexity. Journal of Scheduling, 22, 603–606.CrossRef

Kravchenko, S. A., & Werner, F. (2011). Parallel machine problems with equal processing times: A survey. Journal of Scheduling, 14, 435–444.CrossRef

Labetoulle, J., Lawler, E. L., Lenstra, J. K., & Rinnooy Kan, A. H. G. (1984). Preemptive scheduling of uniform machines subject to release dates. Progress in combinatorial optimization (pp. 245–261). Toronto: Academic Press.

Lawler, E. L. (1990). A dynamic programming algorithm for preemptive scheduling of a single machine to minimize the number of late jobs. Annals of Operations Research, 26, 125–133.CrossRef

Lawler, E. L. (1994). Knapsack-like scheduling problems, the Moore-Hodgson algorithm and the ‘tower of set’ property. Mathematical and Computer Modelling, 20, 91–106.CrossRef

Lawler, E. L., & Moore, J. M. (1969). A functional equation and its application to resource allocation and sequencing problems. Management Science, 16, 77–84.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., & Wan, G. (2010). Competitive two-agent scheduling and its applications. Operations Research, 58, 458–469.CrossRef

Li, S. S., Cheng, T. C. E., Ng, C. T., & Yuan, J. J. (2017). Two-agent scheduling on a single sequential and compatible batching machine. Naval Research Logistics, 64, 628–641.CrossRef

Li, S. S., & Yuan, J. J. (2020). Single-machine scheduling with multi-agents to minimize total weighted late work. Journal of Scheduling, 23, 497–512.CrossRef

Moore, J. M. (1968). An \(n\) Job, one machine sequencing algorithm for minimizing the number of late jobs. Management Science, 14, 102–109.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

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

Simons, B. (1978). A fast algorithm for single processor scheduling. In Proc. IEEE 19th annual symposium on foundations of computer science (FOCS’78) (pp. 246–252).

Sourd, F. (2001). Preemptive scheduling with two minimax criteria. Annals of Operations Research, 107, 303–319.CrossRef

Tian, Z., Ng, C. T., & Cheng, T. C. E. (2006). An \(O(n^2)\) algorithm for scheduling equal-length preemptive jobs on a single machine to minimize total tardiness. Journal of Scheduling, 9, 343–364.CrossRef

Wan, L., Mei, J. J., & Du, J. Z. (2021). Two-agent scheduling of unit processing time to minimize total weighted completion time and total weighted number of tardy jobs. European Journal of Operational Research, 290, 26–35.CrossRef

Wan, L., Yuan, J. J., & Geng, Z. C. (2015). A note on the preemptive scheduling to minimize total completion time with release time and deadline constraints. Journal of Scheduling, 18, 315–323.CrossRef

Wan, L., Yuan, J. J., & Wei, L. (2016). Pareto optimization scheduling with two competing agents to minimize the number of tardy jobs and the maximum cost. Applied Mathematics and Computation, 273, 912–923.CrossRef

Yin, Y., Chen, Y., Qin, K., & Wan, D. (2019). Two-agent scheduling on unrelated parallel machines with total completion time and weighted number of tardy jobs criteria. Journal of Scheduling, 22, 315–333.CrossRef

Yin, Y., Cheng, S. R., Cheng, T. C. E., Wu, W. H., & Wu, C. C. (2013). Two-agent single-machine scheduling with release times and deadlines. International Journal of Shipping and Transport Logistics, 5, 75–94.CrossRef

Yin, Y., Wang, D., & Cheng, T. C. E. (2020). Due date-related scheduling with two agents: Models and algorithms. Singapore: Springer.CrossRef

Yuan, J. J., Ng, C. T., & Cheng, T. C. E. (2015). Two-agent single-machine scheduling with release dates and preemption to minimize the maximum lateness. Journal of Scheduling, 18, 147–153.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, 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.

Zhao, Q. L., & Yuan, J. J. (2020). Bicriteria scheduling of equal length jobs on uniform parallel machines. Journal of Combinatorial Optimization, 39, 637–661.CrossRef

Zhao, W., Ramamritham, K., & Stankovic, J. A. (1987). Preemptive scheduling under time and resource constraints. IEEE Transactions on Computers, 36, 949–960.CrossRef

Titel: Competitive two-agent scheduling with release dates and preemption on a single machine
verfasst von: Shi-Sheng Li
Ren-Xia Chen
Publikationsdatum: 27.03.2023
Verlag: Springer US
Erschienen in: Journal of Scheduling / Ausgabe 3/2023
Print ISSN: 1094-6136
Elektronische ISSN: 1099-1425
DOI: https://doi.org/10.1007/s10951-023-00779-5

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 3/2023

Automatically evolving preference-based dispatching rules for multi-objective job shop scheduling

A note on a single-shift days-off scheduling problem with sequence-dependent labor costs

Optimization of scheduling problems with deterioration effects and an optional maintenance activity

On the complexity of open shop scheduling with time lags

Algorithms for rescheduling jobs with a LIFO buffer to minimize the weighted number of late jobs

Premium Partner