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

References

[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)