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

Expand
  • School of Mathematics and Statistics, Zhengzhou University, Zhengzhou, Henan, 450001, China

Received date: 2021-01-05

  Revised date: 2022-02-15

  Online published: 2023-09-07

Supported by

This research was supported in part by the National Natural Science Foundation of China (Nos.12071442, 11771406, and 11971443).

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.

Cite this article

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 . DOI: 10.1007/s40305-022-00403-x

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)
Options
Outlines

/