Single-Machine Preemptive Scheduling with Release Dates Involving the Total Weighted Late Work Criterion

doi:10.1007/s40305-022-00403-x

Abstract

Abstract: This paper investigates the preemptive scheduling with release dates on a single machine to minimize the total weighted late work. We firstly present an $ O(n\log n) $-time algorithm for the single-agent problem with disagreeable weights and due dates. And then, we extendedly study the two-agent Pareto-scheduling problem with jobs having a common due date to minimize each agent's total weighted late work, and give a polynomial-time algorithm that is based on the parameters analysis to generate the Pareto frontier.

Key words: Preemptive scheduling, Total weighted late work, Two agent, Pareto frontier

CLC Number:

90B35
90C29

Zhi-Chao Geng, Yuan Zhang. Single-Machine Preemptive Scheduling with Release Dates Involving the Total Weighted Late Work Criterion[J]. Journal of the Operations Research Society of China, 2023, 11(3): 693-706.

TrendMD

Add to citation manager EndNote|Reference Manager|ProCite|BibTeX|RefWorks

URL: https://www.jorsc.shu.edu.cn/EN/10.1007/s40305-022-00403-x

https://www.jorsc.shu.edu.cn/EN/Y2023/V11/I3/693

[1] Blazewicz, J., Pesch, E., Sterna, M., Werner, F.: Open shop scheduling problems with late work criteria. Discrete. Appl. Math. 134, 1–24(2004)
[2] Sterna, M.: A survey of scheduling problems with late work criteria. Omega 39, 120C129(2011)
[3] Liu, S.C., Duan, J., Lin, W.C., Wu, W.H., Kung, J.K., Chen, H.: A branch-and-bound algorithm for two-agent scheduling with learning effect and late work criterion. Asia. J. Oper. Res. 35, 1850037(2018)
[4] Agnetis, A., Billaut, J.C., Gawiejnowicz, S., Pacciarelli, D., Soukhal, A.: Multiagent Scheduling-Models and Algorithms. Springer, Berlin (2014)
[5] Graham, R.L., Lawler, E.L., Lenstra, J.K., Rinnooy Kan, A.H.G.: Optimization and approximation in deterministic sequencing and scheduling: a survey. Ann. Discrete Math. 5, 287–326(1979)
[6] Chen, X., Sterna, M., Han, X., Blazewicz, J.: Scheduling on parallel identical machines with late work criterion: offline and online cases. J. Scheduling. 19, 729–736(2016)
[7] Yin, Y.Q., Xu, J.Y., Cheng, T.C.E., Wu, C.C., Wang, D.J.: Approximation schemes for single-machine scheduling with a fixed maintenance activity to minimize the total amount of late work. Nav. Res. Log. 63, 172–183(2016)
[8] Chen, X., Chau, V., Xie, P., Sterna, M., Blazewicz, J.: Complexity of late work minimization in flow shop systems and a particle swarm optimization algorithm for learning effect. Comput. Ind. Eng. 111, 176–182(2017)
[9] Piroozfard, H., Wong, K.Y., Wong, W.P.: Minimizing total carbon footprint and total late work criterion in flexible job shop scheduling by using an improved multi-objective genetic algorithm. Resour. Conserv. Recy. 128, 267C283(2018)
[10] Chen, R.B., Yuan, J.J., Ng, C.T., Cheng, T.C.E.: Single-machine scheduling with deadlines to minimize the total weighted late work. Nav. Res. Log. 66, 582–595(2019)
[11] Baker, K.R., Smith, J.C.: A multiple-criterion model for machine scheduling. J. Scheduling. 6, 7–16(2003)
[12] Agnetis, A., Mirchandani, P.B., Pacciarelli, D., Pacifici, A.: Scheduling problems with two competing agents. Oper. Res. 52, 229–242(2004)
[13] Perez-Gonzalez, P., Framinan, J.M.: A common frame work and taxonomy for multicriteria scheduling problems with interfering and competing jobs: multi-agent scheduling problems. Eur. J. Oper. Res. 235, 1C16(2014)
[14] Blazewicz, J.: Scheduling preemptible tasks on parallel processors with information loss. Technol. Sci. Inform. 3, 415–420(1984)
[15] Blazewicz, J., Finke, G.: Minimizing mean weighted execution time loss on identical and uniform processors. Inform. Process. Lett. 24, 259–263(1987)
[16] Leung, J.Y.T.: Minimizing total weighted error for imprecise computation tasks and related problems. In J.Y.T. Leung (Ed.), Handbook of scheduling: Algorithms, models, and performance analysis, pp. 34.1–34.16, Boca Raton, CRC Press (2004)
[17] Leung, J.Y.T., Yu, V.K.M., Wei, W.D.: Minimizing the weighted number of tardy task units. Discrete. Appl. Math. 51, 307–316(1994)
[18] Lin, B.M., Hsu, S.W.: Minimizing total late work on a single machine with release and due dates. In: SIAM Conference on Computational Science and Engineering, Orlando. https://doi.org/10.1016/j.talanta.2004.06.034
[19] Wang, D.J., Kang, C.C., Shiau, Y.R., Wu, C.C., Hsu, P.H.: A two-agent single-machine scheduling problem with late work criteria. Soft. Comput. 21, 2015–2033(2017)
[20] Zhang, X., Wang, Y.: Two-agent scheduling problems on a single-machine to minimize the total weighted late work. J. Comb. Optim. 33, 945–955(2017)
[21] Zhang, Y., Yuan, J.J.: A note on a two-agent scheduling problem related to the total weighted late work. J. Comb. Optim. 37, 989–999(2019)
[22] Li, S.S., Yuan, J.J.: Single-machine scheduling with multi-agents to minimize total weighted late work. J. Scheduling. https://doi.org/10.1007/s10951-020-00646-7
[23] Hoogeveen, J.A.: Single-machine scheduling to minimize a function of two or three maximum cost criteria. J. Algorithm. 21, 415–433(1996)
[24] Hoogeveen, J.A., Van de Velde, S.L.: Minimizing total completion time and maximum cost simultaneously is solvable in polynomial time. Oper. Res. Lett. 17, 205–208(1995)
[25] Geng, Z., Yuan, J.J.: Pareto optimization scheduling of family jobs on a p-batch machine to minimize makespan and maximum lateness. Theor. Comput. 570, 22–29(2015)
[26] Yuan, J.J., Ng, C.T., Cheng, T.C.E.: Two-agent single-machine scheduling with release dates and preemption to minimize the maximum lateness. J. Scheduling. 18, 147–153(2015)
[27] Hochbaum, D.S., Shamir, R.: Minimizing the number of tardy job unit under release time constraints. Discrete. Appl. Math. 28, 45–57(1990)
[28] Tkindt, V., Billaut, J.C.: Multicriteria Scheduling: Theory, Models and Algorithms, 2nd edn. Springer, Berlin (2006)

Single-Machine Preemptive Scheduling with Release Dates Involving the Total Weighted Late Work Criterion

PDF

Knowledge

Abstract

Cite this article

share this article

Related Articles 15

Recommended Articles

Metrics

Comments

[1]	Yan-Jun Qu, Ji Tian, Ru-Yan Fu, Kai-Jie Ge. A Best Possible Online Algorithm for Single-Machine Scheduling with Non-delayed Processing Constraint and Bounded Delivery Times [J]. Journal of the Operations Research Society of China, 2026, 14(2): 489-501.
[2]	Cheng He, Jing Wu, Hao Lin, Yuan Zhang, Yan Zhao. The Unbounded Parallel-Batching Bicriteria Scheduling with Two-Component Jobs [J]. Journal of the Operations Research Society of China, 2026, 14(2): 547-564.
[3]	Lan-Meng Meng, Ran Ma, Yu-Zhong Zhang. Single-Machine Online Scheduling with Non-delayed Processing Constraint and Deterioration Effect in the Steel Rolling Process [J]. Journal of the Operations Research Society of China, 2026, 14(2): 653-670.
[4]	Xin-Gong Zhang, Xiao-Min Tang. The Two Single-Machine Scheduling Problems with Slack Due Date to Minimize Total Early Work and Late Work [J]. Journal of the Operations Research Society of China, 2026, 14(1): 129-148.
[5]	Zhu-Yi-Nan Wang, Chen Zhang, Zhi-Yi Tan. Scheduling Games with Potential Penalties on the Move of Jobs [J]. Journal of the Operations Research Society of China, 2025, 13(4): 1157-1180.
[6]	Ru-Yan He, Jin-Jiang Yuan, Yuan Zhang. The Single-Machine Preemptive or Resumable Scheduling with Maintenance Intervals [J]. Journal of the Operations Research Society of China, 2025, 13(2): 590-602.
[7]	Li-Yun Miao, Ji Tian, Ru-Yan Fu. A Best Possible Online Algorithm For Parallel-Batch Scheduling with Kind Release Times and Job Compatibilities [J]. Journal of the Operations Research Society of China, 2025, 13(2): 603-615.
[8]	Fan-Yu Kong, Cui-Xia Miao, Yu-Jia Huo, Jia-Xin Song, Yu-Zhong Zhang. Single-Machine Scheduling with Step-Deteriorating Jobs and Rejection [J]. Journal of the Operations Research Society of China, 2024, 12(4): 1088-1102.
[9]	Man Xiao, Yu-Fei Du, Wei-Dong Li, Jin-Hua Yang. Semi-online Machine Covering Problem on Three Hierarchical Machines with Bounded Processing Times [J]. Journal of the Operations Research Society of China, 2024, 12(4): 1126-1138.
[10]	Dan-Yang Lv, Jing Xue, Ji-Bo Wang. Minmax Common Due-Window Assignment Scheduling with Deteriorating Jobs [J]. Journal of the Operations Research Society of China, 2024, 12(3): 681-693.
[11]	Wei-Dong Li. Improved Approximation Schemes for Early Work Scheduling on Identical Parallel Machines with a Common Due Date [J]. Journal of the Operations Research Society of China, 2024, 12(2): 341-350.
[12]	Hai-Ling Liu, Xi-Wen Lu. Online Scheduling on a Parallel Batch Machine with Delivery Times and Limited Restarts [J]. Journal of the Operations Research Society of China, 2022, 10(1): 113-131.
[13]	Cheng He, Hao Lin, Li Li. Unbounded Serial-Batching Scheduling on Hierarchical Optimization [J]. Journal of the Operations Research Society of China, 2021, 9(4): 909-914.
[14]	Guo-Jun Zhang, Jin-Chuan Cui. A Novel MILP Model for N-vehicle Exploration Problem [J]. Journal of the Operations Research Society of China, 2021, 9(2): 359-373.
[15]	Yu-Zhong Zhang, Shu-Guang Li. Scheduling Jobs with Release and Delivery Times Subject to Nested Eligibility Constraints [J]. Journal of the Operations Research Society of China, 2021, 9(1): 63-77.