Single-machine Pareto-scheduling with multiple weighting vectors for minimizing the total weighted late works

Shuen Guo; Zhichao Geng; Jinjiang Yuan

doi:10.3934/jimo.2021192

Article Contents

2023, Volume 19, Issue 1: 456-471. Doi: 10.3934/jimo.2021192

This issue Previous Article Diagonally scaled memoryless quasi–Newton methods with application to compressed sensing Next Article Zinc ore supplier evaluation and recommendation method based on nonlinear adaptive online transfer learning

Single-machine Pareto-scheduling with multiple weighting vectors for minimizing the total weighted late works

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

^*Corresponding author: Jinjiang Yuan
^*Corresponding author: Jinjiang Yuan

Received: March 2021

Revised: August 2021

Early access: November 2021

Published: January 2023

Abstract / Introduction Full Text(HTML) Related Papers Cited by

Abstract

In this paper, we study the single-machine Pareto-scheduling of jobs with multiple weighting vectors for minimizing the total weighted late works. Each weighting vector has its corresponding weighted late work. The goal of the problem is to find the Pareto-frontier for the weighted late works of the multiple weighting vectors. When the number of weighting vectors is arbitrary, it is implied in the literature that the problem is unary NP-hard. Then we concentrate on our research under the assumption that the number of weighting vectors is a constant. For this problem, we present a dynamic programming algorithm running in pseudo-polynomial time and a fully polynomial-time approximation scheme (FPTAS).

Keywords:

Scheduling,
multiple weights,
weighted late work,
Pareto-frontier,
fully polynomial-time approximation scheme.

Mathematics Subject Classification: Primary: 90B35; Secondary: 68M20.

Citation:

Full Text(HTML)

Related Papers

Cited by

References

[1]	J. Blazewicz, Scheduling preemptible tasks on parallel processors with information loss, Technique et Science Informatiques, 3 (1984), 415-420.
[2]	J. Blazewicz and G. Finke, Minimizing mean weighted execution time loss on identical and uniform processors, Inform. Process. Lett., 24 (1987), 259-263. doi: 10.1016/0020-0190(87)90145-1.
[3]	J. Blazewicz, E. Pesch, M. Sterna and F. Werner, The two-machine flow-shop problem with weighted late work criterion and common due date, European J. Oper. Res., 165 (2005), 408-415. doi: 10.1016/j.ejor.2004.04.011.
[4]	R. B. Chen and J. J. Yuan, Single-machine scheduling to minimize total weighted late work with positional due-indices, Operations Research Transactions, 24 (2020), 131-144.
[5]	R. B. Chen, J. J. Yuan, C. T. Ng and T. C. E. Cheng, Single machine scheduling with deadlines to minimize the total weighted late work, Naval Res. Logist., 66 (2019), 582-595. doi: 10.1002/nav.21869.
[6]	R. B. Chen, J. J. Yuan, C. T. Ng and T. C. E. Cheng, Bicriteria scheduling to minimize total late work and maximum tardiness with preemption, Computers & Industrial Engineering, 159 (2021), 107525. doi: 10.1016/j.cie.2021.107525.
[7]	X. Chen, M. Sterna, X. Han and J. Blazewicz, Scheduling on parallel identical machines with late work criterion: Offline and online cases, J. Sched., 19 (2016), 729-736. doi: 10.1007/s10951-015-0464-7.
[8]	D. Freud and G. Mosheiov, Scheduling with competing agents, total late work and job rejection, Comput. Oper. Res., 133 (2021), 105329. doi: 10.1016/j.cor.2021.105329.
[9]	A. M. A. Hariri, C. N. Potts and L. N. Van Wassenhove, Single machine scheduling to minimize total weighted late work, ORSA Journal on Computing, 7 (1995), 232-242.
[10]	R. Y. He and J. J. Yuan, Two-agent preemptive pareto-scheduling to minimize late work and other criteria, Mathematics, 8 (2020), 1517. doi: 10.3390/math8091517.
[11]	R. Y. He, J. J. Yuan, C. T. Ng and T. C. E. Cheng, Two-agent preemptive Pareto-scheduling to minimize the number of tardy jobs and total late work, J. Comb. Optim., 41 (2021), 504-525. doi: 10.1007/s10878-021-00697-2.
[12]	D. S. Hochbaum and R. Shamir, Minimizing the number of tardy job units under release time constraints, Discrete Applied Mathematics, 28 (1990), 45-57. doi: 10.1016/0166-218X(90)90093-R.
[13]	R. B. Kethley and B. Alidaee, Single machine scheduling to minimize total weighted late work: A comparison of scheduling rules and search algorithms, Computers & Industrial Engineering, 43 (2002), 509-528. doi: 10.1016/S0360-8352(02)00123-7.
[14]	M. Y. Kovalyov, C. N. Potts and L. N. Van Wassenhove, A fully polynomial approximation scheme for scheduling a single machine to minimize total weighted late work, Math. Oper. Res., 19 (1994), 86-93. doi: 10.1287/moor.19.1.86.
[15]	H. T. Kung, F. Luccio and F. P. Preparata, On finding the maxima of a set of vectors, J. Assoc. Comput. Mach., 22 (1975), 469-476. doi: 10.1145/321906.321910.
[16]	J. Y. T. Leung, Minimizing total weighted error for imprecise computation tasks and related problems, Handbook of Scheduling, 34 (2004), 1-16.
[17]	J. Y. T. Leung, K. M. Vincent and W. D. Wei, Minimizing the weighted number of tardy task units, Discrete Appl. Math., 51 (1994), 307-316. doi: 10.1016/0166-218X(92)00037-M.
[18]	S. S. Li and J. J. Yuan, Single-machine scheduling with multi-agents to minimize total weighted late work, J. Sched., 23 (2020), 497-512. doi: 10.1007/s10951-020-00646-7.
[19]	B. M. Lin and S. W. Hsu, Minimizing total late work on a single machine with release and due dates, In SIAM Conference on Computational Science and Engineering, Orlando, 2005.
[20]	G. Mosheiov, D. Oron and D. Shabtay, Minimizing total late work on a single machine with generalized due-dates, European J. Oper. Res., 293 (2021), 837-846. doi: 10.1016/j.ejor.2020.12.061.
[21]	C. N. Potts and L. N. Van Wassenhove, Single machine scheduling to minimize total late work, Oper. Res., 40 (1992), 586-595. doi: 10.1287/opre.40.3.586.
[22]	C. N. Potts and L. N. Van Wassenhove, Approximation algorithms for scheduling a single machine to minimize total late work, Oper. Res. Lett., 11 (1992), 261-266. doi: 10.1016/0167-6377(92)90001-J.
[23]	J. F. Ren, D. L. Du and D. C. Xu, The complexity of two supply chain scheduling problems, Inform. Process. Lett., 113 (2013), 609-612. doi: 10.1016/j.ipl.2013.05.005.
[24]	J. F. Ren, Y. Z. Zhang and G. Sun, The NP-hardness of minimizing the total late work on an unbounded batch machine, Asia-Pac. J. Oper. Res., 26 (2009), 351-363. doi: 10.1142/S0217595909002249.
[25]	M. Sterna, A survey of scheduling problems with late work criteria, Omega, 39 (2011), 120-129. doi: 10.1016/j.omega.2010.06.006.
[26]	M. Sterna, Late and early work scheduling: A survey, Omega, 104 (2021), 102453. doi: 10.1016/j.omega.2021.102453.
[27]	D. J. Wang, C. C. Kang, Y. R. Shiau, C. C. Wu and P. H. Hsu, A two-agent single-machine scheduling problem with late work criteria, Soft Computing, 21 (2017), 2015-2033.
[28]	G. J. Woeginger, When does a dynamic programming formulation guarantee the existence of a fully polynomial time approximation scheme (FPTAS)?, INFORMS J. Comput., 12 (2000), 57-74. doi: 10.1287/ijoc.12.1.57.11901.
[29]	C. C. Wu, Y. Q. Yin, W. H. Wu, H. M. Chen and S. R. Cheng, Using a branch-and-bound and a genetic algorithm for a single-machine total late work scheduling problem, Soft Computing, 20 (2016), 1329-1339. doi: 10.1007/s00500-015-1590-z.
[30]	Z. Z. Xu, Y. X. Zou and X. J. Kong, Meta-heuristic algorithms for parallel identical machines scheduling problem with weighted late work criterion and common due date, Springer Plus, 4 (2015), 782. doi: 10.1186/s40064-015-1559-5.
[31]	K. M. Yu, Approximation Algorithms for Minimizing the Number of Tardy Units in Real-time System, Ph.D thesis, Dallas: The University of Texas at Dallas, 1991.
[32]	X. Zhang and Y. Wang, Two-agent scheduling problems on a single-machine to minimize the total weighted late work, J. Comb. Optim., 33 (2017), 945-955. doi: 10.1007/s10878-016-0017-9.
[33]	X. G. Zhang, Two competitive agents to minimize the weighted total late work and the total completion time, Appl. Math. Comput., 406 (2021), 126286. doi: 10.1016/j.amc.2021.126286.
[34]	Y. Zhang, Z. C. Geng and J. J. Yuan, Two-agent Pareto-scheduling of minimizing total weighted completion time and total weighted late work, Mathematics, 8 (2020), 2070.
[35]	Y. Zhang and J. J. Yuan, A note on a two-agent scheduling problem related to the total weighted late work, J. Comb. Optim., 37 (2019), 989-999. doi: 10.1007/s10878-018-0337-z.
[36]	Y. Zhang, J. J. Yuan, C. T. Ng and T. C. E. Cheng, Pareto-optimization of three-agent scheduling to minimize the total weighted completion time, weighted number of tardy jobs, and total weighted late work, Naval Res. Logist., 68 (2021), 378-393. doi: 10.1002/nav.21961.
[37]	J. Zou and J. J. Yuan, Single-machine scheduling with maintenance activities and rejection, Discrete Optim., 38 (2020), 100609. doi: 10.1016/j.disopt.2020.100609.