doi: 10.3934/jimo.2021192
Online First

Online First articles are published articles within a journal that have not yet been assigned to a formal issue. This means they do not yet have a volume number, issue number, or page numbers assigned to them, however, they can still be found and cited using their DOI (Digital Object Identifier). Online First publication benefits the research community by making new scientific discoveries known as quickly as possible.

Readers can access Online First articles via the “Online First” tab for the selected journal.

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

Received  March 2021 Revised  August 2021 Early access November 2021

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

Citation: Shuen Guo, Zhichao Geng, Jinjiang Yuan. Single-machine Pareto-scheduling with multiple weighting vectors for minimizing the total weighted late works. Journal of Industrial & Management Optimization, doi: 10.3934/jimo.2021192
References:
[1]

J. Blazewicz, Scheduling preemptible tasks on parallel processors with information loss, Technique et Science Informatiques, 3 (1984), 415-420.   Google Scholar

[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.  Google Scholar

[3]

J. BlazewiczE. PeschM. 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.  Google Scholar

[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.   Google Scholar

[5]

R. B. ChenJ. J. YuanC. 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.  Google Scholar

[6]

R. B. ChenJ. J. YuanC. 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.  Google Scholar

[7]

X. ChenM. SternaX. 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.  Google Scholar

[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.  Google Scholar

[9]

A. M. A. HaririC. N. Potts and L. N. Van Wassenhove, Single machine scheduling to minimize total weighted late work, ORSA Journal on Computing, 7 (1995), 232-242.   Google Scholar

[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.  Google Scholar

[11]

R. Y. HeJ. J. YuanC. 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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[14]

M. Y. KovalyovC. 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.  Google Scholar

[15]

H. T. KungF. 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.  Google Scholar

[16]

J. Y. T. Leung, Minimizing total weighted error for imprecise computation tasks and related problems, Handbook of Scheduling, 34 (2004), 1-16.   Google Scholar

[17]

J. Y. T. LeungK. 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.  Google Scholar

[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.  Google Scholar

[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. Google Scholar

[20]

G. MosheiovD. 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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[23]

J. F. RenD. 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.  Google Scholar

[24]

J. F. RenY. 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.  Google Scholar

[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.  Google Scholar

[26]

M. Sterna, Late and early work scheduling: A survey, Omega, 104 (2021), 102453.  doi: 10.1016/j.omega.2021.102453.  Google Scholar

[27]

D. J. WangC. C. KangY. R. ShiauC. C. Wu and P. H. Hsu, A two-agent single-machine scheduling problem with late work criteria, Soft Computing, 21 (2017), 2015-2033.   Google Scholar

[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.  Google Scholar

[29]

C. C. WuY. Q. YinW. H. WuH. 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.  Google Scholar

[30]

Z. Z. XuY. 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.  Google Scholar

[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. Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[34]

Y. ZhangZ. 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.   Google Scholar

[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.  Google Scholar

[36]

Y. ZhangJ. J. YuanC. 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.  Google Scholar

[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.  Google Scholar

show all references

References:
[1]

J. Blazewicz, Scheduling preemptible tasks on parallel processors with information loss, Technique et Science Informatiques, 3 (1984), 415-420.   Google Scholar

[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.  Google Scholar

[3]

J. BlazewiczE. PeschM. 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.  Google Scholar

[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.   Google Scholar

[5]

R. B. ChenJ. J. YuanC. 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.  Google Scholar

[6]

R. B. ChenJ. J. YuanC. 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.  Google Scholar

[7]

X. ChenM. SternaX. 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.  Google Scholar

[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.  Google Scholar

[9]

A. M. A. HaririC. N. Potts and L. N. Van Wassenhove, Single machine scheduling to minimize total weighted late work, ORSA Journal on Computing, 7 (1995), 232-242.   Google Scholar

[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.  Google Scholar

[11]

R. Y. HeJ. J. YuanC. 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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[14]

M. Y. KovalyovC. 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.  Google Scholar

[15]

H. T. KungF. 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.  Google Scholar

[16]

J. Y. T. Leung, Minimizing total weighted error for imprecise computation tasks and related problems, Handbook of Scheduling, 34 (2004), 1-16.   Google Scholar

[17]

J. Y. T. LeungK. 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.  Google Scholar

[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.  Google Scholar

[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. Google Scholar

[20]

G. MosheiovD. 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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[23]

J. F. RenD. 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.  Google Scholar

[24]

J. F. RenY. 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.  Google Scholar

[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.  Google Scholar

[26]

M. Sterna, Late and early work scheduling: A survey, Omega, 104 (2021), 102453.  doi: 10.1016/j.omega.2021.102453.  Google Scholar

[27]

D. J. WangC. C. KangY. R. ShiauC. C. Wu and P. H. Hsu, A two-agent single-machine scheduling problem with late work criteria, Soft Computing, 21 (2017), 2015-2033.   Google Scholar

[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.  Google Scholar

[29]

C. C. WuY. Q. YinW. H. WuH. 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.  Google Scholar

[30]

Z. Z. XuY. 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.  Google Scholar

[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. Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[34]

Y. ZhangZ. 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.   Google Scholar

[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.  Google Scholar

[36]

Y. ZhangJ. J. YuanC. 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.  Google Scholar

[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.  Google Scholar

[1]

Igor E. Pritsker and Richard S. Varga. Weighted polynomial approximation in the complex plane. Electronic Research Announcements, 1997, 3: 38-44.

[2]

Terry Shue Chien Lau, Chik How Tan. Polynomial-time plaintext recovery attacks on the IKKR code-based cryptosystems. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2020132

[3]

Yanqin Bai, Pengfei Ma, Jing Zhang. A polynomial-time interior-point method for circular cone programming based on kernel functions. Journal of Industrial & Management Optimization, 2016, 12 (2) : 739-756. doi: 10.3934/jimo.2016.12.739

[4]

Imed Kacem, Eugene Levner. An improved approximation scheme for scheduling a maintenance and proportional deteriorating jobs. Journal of Industrial & Management Optimization, 2016, 12 (3) : 811-817. doi: 10.3934/jimo.2016.12.811

[5]

P. Robert Kotiuga. On the topological characterization of near force-free magnetic fields, and the work of late-onset visually-impaired topologists. Discrete & Continuous Dynamical Systems - S, 2016, 9 (1) : 215-234. doi: 10.3934/dcdss.2016.9.215

[6]

Ran Ma, Jiping Tao. An improved 2.11-competitive algorithm for online scheduling on parallel machines to minimize total weighted completion time. Journal of Industrial & Management Optimization, 2018, 14 (2) : 497-510. doi: 10.3934/jimo.2017057

[7]

Jinjiang Yuan, Weiping Shang. A PTAS for the p-batch scheduling with pj = p to minimize total weighted completion time. Journal of Industrial & Management Optimization, 2005, 1 (3) : 353-358. doi: 10.3934/jimo.2005.1.353

[8]

Wen-Hung Wu, Yunqiang Yin, Wen-Hsiang Wu, Chin-Chia Wu, Peng-Hsiang Hsu. A time-dependent scheduling problem to minimize the sum of the total weighted tardiness among two agents. Journal of Industrial & Management Optimization, 2014, 10 (2) : 591-611. doi: 10.3934/jimo.2014.10.591

[9]

Horst Osberger. Long-time behavior of a fully discrete Lagrangian scheme for a family of fourth order equations. Discrete & Continuous Dynamical Systems, 2017, 37 (1) : 405-434. doi: 10.3934/dcds.2017017

[10]

Guoliang Xue, Weiyi Zhang, Tie Wang, Krishnaiyan Thulasiraman. On the partial path protection scheme for WDM optical networks and polynomial time computability of primary and secondary paths. Journal of Industrial & Management Optimization, 2007, 3 (4) : 625-643. doi: 10.3934/jimo.2007.3.625

[11]

Maurizio Grasselli, Nicolas Lecoq, Morgan Pierre. A long-time stable fully discrete approximation of the Cahn-Hilliard equation with inertial term. Conference Publications, 2011, 2011 (Special) : 543-552. doi: 10.3934/proc.2011.2011.543

[12]

Zhonghua Qiao, Xuguang Yang. A multiple-relaxation-time lattice Boltzmann method with Beam-Warming scheme for a coupled chemotaxis-fluid model. Electronic Research Archive, 2020, 28 (3) : 1207-1225. doi: 10.3934/era.2020066

[13]

Dmitry Dolgopyat. The work of Sébastien Gouëzel on limit theorems and on weighted Banach spaces. Journal of Modern Dynamics, 2020, 16: 351-371. doi: 10.3934/jmd.2020014

[14]

Wenchang Luo, Lin Chen. Approximation schemes for scheduling a maintenance and linear deteriorating jobs. Journal of Industrial & Management Optimization, 2012, 8 (2) : 271-283. doi: 10.3934/jimo.2012.8.271

[15]

Antonio Garijo, Xavier Jarque. The secant map applied to a real polynomial with multiple roots. Discrete & Continuous Dynamical Systems, 2020, 40 (12) : 6783-6794. doi: 10.3934/dcds.2020133

[16]

Muminu O. Adamu, Aderemi O. Adewumi. A survey of single machine scheduling to minimize weighted number of tardy jobs. Journal of Industrial & Management Optimization, 2014, 10 (1) : 219-241. doi: 10.3934/jimo.2014.10.219

[17]

Kohei Ueno. Weighted Green functions of nondegenerate polynomial skew products on $\mathbb{C}^2$. Discrete & Continuous Dynamical Systems, 2011, 31 (3) : 985-996. doi: 10.3934/dcds.2011.31.985

[18]

Kohei Ueno. Weighted Green functions of polynomial skew products on $\mathbb{C}^2$. Discrete & Continuous Dynamical Systems, 2014, 34 (5) : 2283-2305. doi: 10.3934/dcds.2014.34.2283

[19]

Pierre Gervais. A spectral study of the linearized Boltzmann operator in $ L^2 $-spaces with polynomial and Gaussian weights. Kinetic & Related Models, 2021, 14 (4) : 725-747. doi: 10.3934/krm.2021022

[20]

Z.G. Feng, K.L. Teo, Y. Zhao. Branch and bound method for sensor scheduling in discrete time. Journal of Industrial & Management Optimization, 2005, 1 (4) : 499-512. doi: 10.3934/jimo.2005.1.499

2020 Impact Factor: 1.801

Article outline

[Back to Top]