doi: 10.3934/jimo.2019005

A survey of due-date related single-machine with two-agent scheduling problem

Department of Supply Chain Management, I.H. Asper School of Business, University of Manitoba, Winnipeg, Manitoba, R3T 5V4, Canada

* Corresponding author: Yuvraj Gajpal

Received  November 2017 Revised  September 2018 Published  March 2019

In this paper, we consider due-date related single machine scheduling problems, where two agents compete for utilizing a common processing resource (i.e. a single machine). In this paper, we provide a detailed and a systemic literature review of the two-agent scheduling problem dealing with models with a given due date. We consider the following four main cases: 1) the earliness and tardiness, 2) the maximum lateness, 3) the number of tardy jobs and 4) the late work criteria. To do so, we classify due-date related, two-agent scheduling problems into two categories on the basis of the objective function setting, (i.e. the feasibility model and the minimality model). The feasibility model minimizes the objective function of one agent subject to an upper bound on the objective for the other agent. The minimality model assigns certain weights for two agents and as a result minimizes their weighted objectives. In the present paper, we list the computational complexities and proposed algorithms for the due-date related, two-agent scheduling problem, investigated in the literature since 2003.

Citation: Hongwei Li, Yuvraj Gajpal, C. R. Bector. A survey of due-date related single-machine with two-agent scheduling problem. Journal of Industrial & Management Optimization, doi: 10.3934/jimo.2019005
References:
[1]

A. AgnetisG. de Pascale and D. Pacciarelli, A Lagrangian approach to single-machine scheduling problems with two competing agents, Journal of Scheduling, 12 (2009), 401-415. doi: 10.1007/s10951-008-0098-0. Google Scholar

[2]

A. AgnetisP. B. MirchandaniD. Pacciarelli and A. Pacifici, Scheduling problems with two competing agents, Operations Research, 52 (2004), 229-242. doi: 10.1287/opre.1030.0092. Google Scholar

[3]

K. R. Baker and J. Cole Smith, A multiple-criterion model for machine scheduling, Journal of Scheduling, 6 (2003), 7-16. doi: 10.1023/A:1022231419049. Google Scholar

[4]

P. BaptisteJ. Carlier and A. Jouglet, A branch-and-bound procedure to minimize total tardiness on one machine with arbitrary release dates, European Journal of Operational Research, 158 (2004), 595-608. doi: 10.1016/S0377-2217(03)00378-3. Google Scholar

[5]

J. Blazewicz, Scheduling preemptible tasks on parallel processors with information k s., (1984).Google Scholar

[6]

J. BłazewiczM. DrozdowskiP. FormanowiczW. Kubiak and G. Schmidt, Scheduling preemptable tasks on parallel processors with limited availability, Parallel Computing, 26 (2000), 1195-1211. doi: 10.1016/S0167-8191(00)00035-1. Google Scholar

[7]

P. J. Brewer and C. R. Plott, A binary conflict ascending price (BICAP) mechanism for the decentralized allocation of the right to use railroad tracks, International Journal of Industrial Organization, 14 (1996), 857-886. doi: 10.1016/0167-7187(96)01014-4. Google Scholar

[8]

S.-R. Cheng, Some new problems on two-agent scheduling to minimize the earliness costs, International Journal of Production Economics, 156 (2014), 24-30. doi: 10.1016/j.ijpe.2014.05.004. Google Scholar

[9]

T. E. ChengY.-H. ChungS.-C. Liao and W.-C. Lee, Two-agent singe-machine scheduling with release times to minimize the total weighted completion time, Computers & Operations Research, 40 (2013), 353-361. doi: 10.1016/j.cor.2012.07.013. Google Scholar

[10]

T. E. ChengC.-Y. LiuW.-C. Lee and M. Ji, Two-agent single-machine scheduling to minimize the weighted sum of the agents' objective functions, Computers & Industrial Engineering, 78 (2014), 66-73. doi: 10.1016/j.cie.2014.09.028. Google Scholar

[11]

T. E. ChengC. Ng and J. Yuan, Multi-agent scheduling on a single machine with max-form criteria, European Journal of Operational Research, 188 (2008), 603-609. doi: 10.1016/j.ejor.2007.04.040. Google Scholar

[12]

D. ElvikisH. W. Hamacher and V. T'kindt, Scheduling two agents on uniform parallel machines with makespan and cost functions, Journal of Scheduling, 14 (2011), 471-481. doi: 10.1007/s10951-010-0201-1. Google Scholar

[13]

D. Elvikis and V. T'kindt, Two-agent scheduling on uniform parallel machines with min-max criteria, Annals of Operations Research, 213 (2014), 79-94. doi: 10.1007/s10479-012-1099-0. Google Scholar

[14]

E. Gerstl and G. Mosheiov, Scheduling problems with two competing agents to minimized weighted earliness-tardiness, Computers & Operations Research, 40 (2013), 109-116. doi: 10.1016/j.cor.2012.05.019. Google Scholar

[15]

E. Gerstl and G. Mosheiov, Single machine just-in-time scheduling problems with two competing agents, Naval Research Logistics (NRL), 61 (2014), 1-16. doi: 10.1002/nav.21562. Google Scholar

[16]

A. M. 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

[17]

W. Horn, Some simple scheduling algorithms, Naval Research Logistics (NRL), 21 (1974), 177-185. doi: 10.1002/nav.3800210113. Google Scholar

[18]

R. M. Karp, Reducibility among combinatorial problems, Complexity of Computer Computations(Proc. Sympos., IBM Thomas J. Watson Res. Center, Yorktown Heights, N. Y., 1972), , Springer, (1972), 85–103. Google Scholar

[19]

S. KirkpatrickC. D. Gelatt and M. P. Vecchi, Optimization by simulated annealing, Science, 220 (1983), 671-680. doi: 10.1126/science.220.4598.671. Google Scholar

[20]

W.-C. LeeY.-H. Chung and M.-C. Hu, Genetic algorithms for a two-agent single-machine problem with release time, Applied Soft Computing, 12 (2012), 3580-3589. doi: 10.1016/j.asoc.2012.06.015. Google Scholar

[21]

W.-C. LeeY.-H. Chung and Z.-R. Huang, A single-machine bi-criterion scheduling problem with two agents, Applied Mathematics and Computation, 219 (2013), 10831-10841. doi: 10.1016/j.amc.2013.05.025. Google Scholar

[22]

W.-C. LeeW.-J. WangY.-R. Shiau and C.-C. Wu, A single-machine scheduling problem with two-agent and deteriorating jobs, Applied Mathematical Modelling, 34 (2010), 3098-3107. doi: 10.1016/j.apm.2010.01.015. Google Scholar

[23]

J. Y.-T. LeungM. Pinedo and G. Wan, Competitive two-agent scheduling and its applications, Operations Research, 58 (2010), 458-469. doi: 10.1287/opre.1090.0744. Google Scholar

[24]

H. LiY. Gajpal and C. Bector, Single machine scheduling with two-agent for total weighted completion time objectives, Applied Soft Computing, 70 (2018), 147-156. doi: 10.1016/j.asoc.2018.05.027. Google Scholar

[25]

Y. Lun, K. Lai, C. Ng, C. Wong and T. Cheng, Editorial: Research in Shipping and Transport Logistics, International Journal of Shipping and Transport Logistics, 2011.Google Scholar

[26]

M. MezmazN. MelabY. KessaciY. C. LeeE.-G. TalbiA. Y. Zomaya and D. Tuyttens, A parallel bi-objective hybrid metaheuristic for energy-aware scheduling for cloud computing systems, Journal of Parallel and Distributed Computing, 71 (2011), 1497-1508. doi: 10.1016/j.jpdc.2011.04.007. Google Scholar

[27]

J. M. Moore, An n job, one machine sequencing algorithm for minimizing the number of late jobs, Management Science, 15 (1968), 102-109. doi: 10.1287/mnsc.15.1.102. Google Scholar

[28]

B. Mor and G. Mosheiov, Scheduling problems with two competing agents to minimize minmax and minsum earliness measures, European Journal of Operational Research, 206 (2010), 540-546. doi: 10.1016/j.ejor.2010.03.003. Google Scholar

[29]

B. Mor and G. Mosheiov, A two-agent single machine scheduling problem with due-window assignment and a common flow-allowance, Journal of Combinatorial Optimization, 33 (2017), 1454-1468. doi: 10.1007/s10878-016-0049-1. Google Scholar

[30]

C. NgT. C. Cheng and J. Yuan, A note on the complexity of the problem of two-agent scheduling on a single machine, Journal of Combinatorial Optimization, 12 (2006), 387-394. doi: 10.1007/s10878-006-9001-0. Google Scholar

[31]

S. Pandey, L. Wu, S. M. Guru and R. Buyya, A particle swarm optimization-based heuristic for scheduling workflow applications in cloud computing environments, Paper presented at the Advanced information networking and applications (AINA), 2010 24th IEEE international conference on, 2010.Google Scholar

[32]

J. M. Peha, Heterogeneous-criteria scheduling: minimizing weighted number of tardy jobs and weighted completion time, Computers & Operations Research, 22 (1995), 1089-1100. doi: 10.1016/0305-0548(94)00090-U. Google Scholar

[33]

M. Pinedo, Scheduling, Theory, algorithms, and systems. Fourth edition. Springer, New York, 2012. doi: 10.1007/978-1-4614-2361-4. Google Scholar

[34]

C. N. Potts and L. N. Van Wassenhove, Approximation algorithms for scheduling a single machine to minimize total late work, Operations Research Letters, 11 (1992), 261-266. doi: 10.1016/0167-6377(92)90001-J. Google Scholar

[35]

C. N. Potts and L. N. Van Wassenhove, Single machine scheduling to minimize total late work, Operations Research, 40 (1992), 586-595. doi: 10.1287/opre.40.3.586. Google Scholar

[36]

M. Reisi-Nafchi and G. Moslehi, A hybrid genetic and linear programming algorithm for two-agent order acceptance and scheduling problem, Applied Soft Computing, 33 (2015), 37-47. doi: 10.1016/j.asoc.2015.04.027. Google Scholar

[37]

R. SoltaniF. Jolai and M. Zandieh, Two robust meta-heuristics for scheduling multiple job classes on a single machine with multiple criteria, Expert Systems with Applications, 37 (2010), 5951-5959. doi: 10.1016/j.eswa.2010.02.009. Google Scholar

[38]

M. Soomer and G. J. Franx, Scheduling aircraft landings using airlines' preferences, European Journal of Operational Research, 190 (2008), 277-291. doi: 10.1016/j.ejor.2007.06.017. Google Scholar

[39]

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

[40]

V. Suresh and D. Chaudhuri, Bicriteria scheduling problem for unrelated parallel machines, Computers & industrial engineering, 30 (1996), 77-82. doi: 10.1016/0360-8352(95)00028-3. Google Scholar

[41]

L. N. Van Wassenhove and C. N. Potts, Single machine scheduling to minimize total late work, Oper. Res., 40 (1992), 586-595. doi: 10.1287/opre.40.3.586. Google Scholar

[42]

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. doi: 10.1007/s00500-015-1900-5. Google Scholar

[43]

D.-J. WangY. YinS.-R. ChengT. Cheng and C.-C. Wu, Due date assignment and scheduling on a single machine with two competing agents, International Journal of Production Research, 54 (2016), 1152-1169. Google Scholar

[44]

D.-J. WangY. YinJ. XuW.-H. WuS.-R. Cheng and C.-C. Wu, Some due date determination scheduling problems with two agents on a single machine, International Journal of Production Economics, 168 (2015), 81-90. doi: 10.1016/j.ijpe.2015.06.018. Google Scholar

[45]

W.-H. Wu, An exact and meta-heuristic approach for two-agent single-machine scheduling problem, Journal of Marine Science and Technology, 21 (2013), 215-221. Google Scholar

[46]

W.-H. WuY. YinW.-H. WuC.-C. Wu and P.-H. Hsu, A time-dependent scheduling problem to minimize the sum of the total weighted tardiness among two agents, Journal of Industrial & Management Optimization, 10 (2014), 591-611. doi: 10.3934/jimo.2014.10.591. Google Scholar

[47]

Z. Xingong and W. Yong, Two-agent scheduling problems on a single-machine to minimize the total weighted late work, Journal of Combinatorial Optimization, 33 (2017), 945-955. doi: 10.1007/s10878-016-0017-9. Google Scholar

[48]

M. Yazdani and F. Jolai, A Genetic Algorithm with Modified Crossover Operator for a Two-Agent Scheduling Problem, Shiraz Journal of System Management, 1 (2013), 1-13. Google Scholar

[49]

Y. YinS.-R. ChengT. ChengD.-J. Wang and C.-C. Wu, Just-in-time scheduling with two competing agents on unrelated parallel machines, Omega, 63 (2016), 41-47. doi: 10.1016/j.omega.2015.09.010. Google Scholar

[50]

Y. YinS.-R. ChengT. ChengW.-H. Wu and C.-C. Wu, Two-agent single-machine scheduling with release times and deadlines, International Journal of Shipping and Transport Logistics, 5 (2013), 75-94. doi: 10.1504/IJSTL.2013.050590. Google Scholar

[51]

Y. YinT. ChengD.-J. Wang and C.-C. Wu, Two-agent flowshop scheduling to maximize the weighted number of just-in-time jobs, Journal of scheduling, 20 (2017), 313-335. doi: 10.1007/s10951-017-0511-7. Google Scholar

[52]

Y. YinW. WangD. Wang and T. Cheng, Multi-agent single-machine scheduling and unrestricted due date assignment with a fixed machine unavailability interval, Computers & Industrial Engineering, 111 (2017), 202-215. doi: 10.1016/j.cie.2017.07.013. Google Scholar

[53]

Y. YinC.-C. WuW.-H. WuC.-J. Hsu and W.-H. Wu, A branch-and-bound procedure for a single-machine earliness scheduling problem with two agents, Applied Soft Computing, 13 (2013), 1042-1054. doi: 10.1016/j.asoc.2012.09.026. Google Scholar

[54]

Y. YinW.-H. WuS.-R. Cheng and C.-C. Wu, An investigation on a two-agent single-machine scheduling problem with unequal release dates, Computers & Operations Research, 39 (2012), 3062-3073. doi: 10.1016/j.cor.2012.03.012. Google Scholar

[55]

Y. YinW.-H. WuT. ChengC.-C. Wu and W.-H. Wu, A honey-bees optimization algorithm for a two-agent single-machine scheduling problem with ready times, Applied Mathematical Modelling, 39 (2015), 2587-2601. doi: 10.1016/j.apm.2014.10.044. Google Scholar

[56]

J. YuanC. Ng and T. E. Cheng, Two-agent single-machine scheduling with release dates and preemption to minimize the maximum lateness, Journal of Scheduling, 18 (2015), 147-153. doi: 10.1007/s10951-013-0360-y. Google Scholar

[57]

F. ZhangC. NgG. TangT. Cheng and Y. Lun, Inverse scheduling: Applications in shipping, International Journal of Shipping and Transport Logistics, 3 (2011), 312-322. doi: 10.1504/IJSTL.2011.040800. Google Scholar

show all references

References:
[1]

A. AgnetisG. de Pascale and D. Pacciarelli, A Lagrangian approach to single-machine scheduling problems with two competing agents, Journal of Scheduling, 12 (2009), 401-415. doi: 10.1007/s10951-008-0098-0. Google Scholar

[2]

A. AgnetisP. B. MirchandaniD. Pacciarelli and A. Pacifici, Scheduling problems with two competing agents, Operations Research, 52 (2004), 229-242. doi: 10.1287/opre.1030.0092. Google Scholar

[3]

K. R. Baker and J. Cole Smith, A multiple-criterion model for machine scheduling, Journal of Scheduling, 6 (2003), 7-16. doi: 10.1023/A:1022231419049. Google Scholar

[4]

P. BaptisteJ. Carlier and A. Jouglet, A branch-and-bound procedure to minimize total tardiness on one machine with arbitrary release dates, European Journal of Operational Research, 158 (2004), 595-608. doi: 10.1016/S0377-2217(03)00378-3. Google Scholar

[5]

J. Blazewicz, Scheduling preemptible tasks on parallel processors with information k s., (1984).Google Scholar

[6]

J. BłazewiczM. DrozdowskiP. FormanowiczW. Kubiak and G. Schmidt, Scheduling preemptable tasks on parallel processors with limited availability, Parallel Computing, 26 (2000), 1195-1211. doi: 10.1016/S0167-8191(00)00035-1. Google Scholar

[7]

P. J. Brewer and C. R. Plott, A binary conflict ascending price (BICAP) mechanism for the decentralized allocation of the right to use railroad tracks, International Journal of Industrial Organization, 14 (1996), 857-886. doi: 10.1016/0167-7187(96)01014-4. Google Scholar

[8]

S.-R. Cheng, Some new problems on two-agent scheduling to minimize the earliness costs, International Journal of Production Economics, 156 (2014), 24-30. doi: 10.1016/j.ijpe.2014.05.004. Google Scholar

[9]

T. E. ChengY.-H. ChungS.-C. Liao and W.-C. Lee, Two-agent singe-machine scheduling with release times to minimize the total weighted completion time, Computers & Operations Research, 40 (2013), 353-361. doi: 10.1016/j.cor.2012.07.013. Google Scholar

[10]

T. E. ChengC.-Y. LiuW.-C. Lee and M. Ji, Two-agent single-machine scheduling to minimize the weighted sum of the agents' objective functions, Computers & Industrial Engineering, 78 (2014), 66-73. doi: 10.1016/j.cie.2014.09.028. Google Scholar

[11]

T. E. ChengC. Ng and J. Yuan, Multi-agent scheduling on a single machine with max-form criteria, European Journal of Operational Research, 188 (2008), 603-609. doi: 10.1016/j.ejor.2007.04.040. Google Scholar

[12]

D. ElvikisH. W. Hamacher and V. T'kindt, Scheduling two agents on uniform parallel machines with makespan and cost functions, Journal of Scheduling, 14 (2011), 471-481. doi: 10.1007/s10951-010-0201-1. Google Scholar

[13]

D. Elvikis and V. T'kindt, Two-agent scheduling on uniform parallel machines with min-max criteria, Annals of Operations Research, 213 (2014), 79-94. doi: 10.1007/s10479-012-1099-0. Google Scholar

[14]

E. Gerstl and G. Mosheiov, Scheduling problems with two competing agents to minimized weighted earliness-tardiness, Computers & Operations Research, 40 (2013), 109-116. doi: 10.1016/j.cor.2012.05.019. Google Scholar

[15]

E. Gerstl and G. Mosheiov, Single machine just-in-time scheduling problems with two competing agents, Naval Research Logistics (NRL), 61 (2014), 1-16. doi: 10.1002/nav.21562. Google Scholar

[16]

A. M. 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

[17]

W. Horn, Some simple scheduling algorithms, Naval Research Logistics (NRL), 21 (1974), 177-185. doi: 10.1002/nav.3800210113. Google Scholar

[18]

R. M. Karp, Reducibility among combinatorial problems, Complexity of Computer Computations(Proc. Sympos., IBM Thomas J. Watson Res. Center, Yorktown Heights, N. Y., 1972), , Springer, (1972), 85–103. Google Scholar

[19]

S. KirkpatrickC. D. Gelatt and M. P. Vecchi, Optimization by simulated annealing, Science, 220 (1983), 671-680. doi: 10.1126/science.220.4598.671. Google Scholar

[20]

W.-C. LeeY.-H. Chung and M.-C. Hu, Genetic algorithms for a two-agent single-machine problem with release time, Applied Soft Computing, 12 (2012), 3580-3589. doi: 10.1016/j.asoc.2012.06.015. Google Scholar

[21]

W.-C. LeeY.-H. Chung and Z.-R. Huang, A single-machine bi-criterion scheduling problem with two agents, Applied Mathematics and Computation, 219 (2013), 10831-10841. doi: 10.1016/j.amc.2013.05.025. Google Scholar

[22]

W.-C. LeeW.-J. WangY.-R. Shiau and C.-C. Wu, A single-machine scheduling problem with two-agent and deteriorating jobs, Applied Mathematical Modelling, 34 (2010), 3098-3107. doi: 10.1016/j.apm.2010.01.015. Google Scholar

[23]

J. Y.-T. LeungM. Pinedo and G. Wan, Competitive two-agent scheduling and its applications, Operations Research, 58 (2010), 458-469. doi: 10.1287/opre.1090.0744. Google Scholar

[24]

H. LiY. Gajpal and C. Bector, Single machine scheduling with two-agent for total weighted completion time objectives, Applied Soft Computing, 70 (2018), 147-156. doi: 10.1016/j.asoc.2018.05.027. Google Scholar

[25]

Y. Lun, K. Lai, C. Ng, C. Wong and T. Cheng, Editorial: Research in Shipping and Transport Logistics, International Journal of Shipping and Transport Logistics, 2011.Google Scholar

[26]

M. MezmazN. MelabY. KessaciY. C. LeeE.-G. TalbiA. Y. Zomaya and D. Tuyttens, A parallel bi-objective hybrid metaheuristic for energy-aware scheduling for cloud computing systems, Journal of Parallel and Distributed Computing, 71 (2011), 1497-1508. doi: 10.1016/j.jpdc.2011.04.007. Google Scholar

[27]

J. M. Moore, An n job, one machine sequencing algorithm for minimizing the number of late jobs, Management Science, 15 (1968), 102-109. doi: 10.1287/mnsc.15.1.102. Google Scholar

[28]

B. Mor and G. Mosheiov, Scheduling problems with two competing agents to minimize minmax and minsum earliness measures, European Journal of Operational Research, 206 (2010), 540-546. doi: 10.1016/j.ejor.2010.03.003. Google Scholar

[29]

B. Mor and G. Mosheiov, A two-agent single machine scheduling problem with due-window assignment and a common flow-allowance, Journal of Combinatorial Optimization, 33 (2017), 1454-1468. doi: 10.1007/s10878-016-0049-1. Google Scholar

[30]

C. NgT. C. Cheng and J. Yuan, A note on the complexity of the problem of two-agent scheduling on a single machine, Journal of Combinatorial Optimization, 12 (2006), 387-394. doi: 10.1007/s10878-006-9001-0. Google Scholar

[31]

S. Pandey, L. Wu, S. M. Guru and R. Buyya, A particle swarm optimization-based heuristic for scheduling workflow applications in cloud computing environments, Paper presented at the Advanced information networking and applications (AINA), 2010 24th IEEE international conference on, 2010.Google Scholar

[32]

J. M. Peha, Heterogeneous-criteria scheduling: minimizing weighted number of tardy jobs and weighted completion time, Computers & Operations Research, 22 (1995), 1089-1100. doi: 10.1016/0305-0548(94)00090-U. Google Scholar

[33]

M. Pinedo, Scheduling, Theory, algorithms, and systems. Fourth edition. Springer, New York, 2012. doi: 10.1007/978-1-4614-2361-4. Google Scholar

[34]

C. N. Potts and L. N. Van Wassenhove, Approximation algorithms for scheduling a single machine to minimize total late work, Operations Research Letters, 11 (1992), 261-266. doi: 10.1016/0167-6377(92)90001-J. Google Scholar

[35]

C. N. Potts and L. N. Van Wassenhove, Single machine scheduling to minimize total late work, Operations Research, 40 (1992), 586-595. doi: 10.1287/opre.40.3.586. Google Scholar

[36]

M. Reisi-Nafchi and G. Moslehi, A hybrid genetic and linear programming algorithm for two-agent order acceptance and scheduling problem, Applied Soft Computing, 33 (2015), 37-47. doi: 10.1016/j.asoc.2015.04.027. Google Scholar

[37]

R. SoltaniF. Jolai and M. Zandieh, Two robust meta-heuristics for scheduling multiple job classes on a single machine with multiple criteria, Expert Systems with Applications, 37 (2010), 5951-5959. doi: 10.1016/j.eswa.2010.02.009. Google Scholar

[38]

M. Soomer and G. J. Franx, Scheduling aircraft landings using airlines' preferences, European Journal of Operational Research, 190 (2008), 277-291. doi: 10.1016/j.ejor.2007.06.017. Google Scholar

[39]

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

[40]

V. Suresh and D. Chaudhuri, Bicriteria scheduling problem for unrelated parallel machines, Computers & industrial engineering, 30 (1996), 77-82. doi: 10.1016/0360-8352(95)00028-3. Google Scholar

[41]

L. N. Van Wassenhove and C. N. Potts, Single machine scheduling to minimize total late work, Oper. Res., 40 (1992), 586-595. doi: 10.1287/opre.40.3.586. Google Scholar

[42]

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. doi: 10.1007/s00500-015-1900-5. Google Scholar

[43]

D.-J. WangY. YinS.-R. ChengT. Cheng and C.-C. Wu, Due date assignment and scheduling on a single machine with two competing agents, International Journal of Production Research, 54 (2016), 1152-1169. Google Scholar

[44]

D.-J. WangY. YinJ. XuW.-H. WuS.-R. Cheng and C.-C. Wu, Some due date determination scheduling problems with two agents on a single machine, International Journal of Production Economics, 168 (2015), 81-90. doi: 10.1016/j.ijpe.2015.06.018. Google Scholar

[45]

W.-H. Wu, An exact and meta-heuristic approach for two-agent single-machine scheduling problem, Journal of Marine Science and Technology, 21 (2013), 215-221. Google Scholar

[46]

W.-H. WuY. YinW.-H. WuC.-C. Wu and P.-H. Hsu, A time-dependent scheduling problem to minimize the sum of the total weighted tardiness among two agents, Journal of Industrial & Management Optimization, 10 (2014), 591-611. doi: 10.3934/jimo.2014.10.591. Google Scholar

[47]

Z. Xingong and W. Yong, Two-agent scheduling problems on a single-machine to minimize the total weighted late work, Journal of Combinatorial Optimization, 33 (2017), 945-955. doi: 10.1007/s10878-016-0017-9. Google Scholar

[48]

M. Yazdani and F. Jolai, A Genetic Algorithm with Modified Crossover Operator for a Two-Agent Scheduling Problem, Shiraz Journal of System Management, 1 (2013), 1-13. Google Scholar

[49]

Y. YinS.-R. ChengT. ChengD.-J. Wang and C.-C. Wu, Just-in-time scheduling with two competing agents on unrelated parallel machines, Omega, 63 (2016), 41-47. doi: 10.1016/j.omega.2015.09.010. Google Scholar

[50]

Y. YinS.-R. ChengT. ChengW.-H. Wu and C.-C. Wu, Two-agent single-machine scheduling with release times and deadlines, International Journal of Shipping and Transport Logistics, 5 (2013), 75-94. doi: 10.1504/IJSTL.2013.050590. Google Scholar

[51]

Y. YinT. ChengD.-J. Wang and C.-C. Wu, Two-agent flowshop scheduling to maximize the weighted number of just-in-time jobs, Journal of scheduling, 20 (2017), 313-335. doi: 10.1007/s10951-017-0511-7. Google Scholar

[52]

Y. YinW. WangD. Wang and T. Cheng, Multi-agent single-machine scheduling and unrestricted due date assignment with a fixed machine unavailability interval, Computers & Industrial Engineering, 111 (2017), 202-215. doi: 10.1016/j.cie.2017.07.013. Google Scholar

[53]

Y. YinC.-C. WuW.-H. WuC.-J. Hsu and W.-H. Wu, A branch-and-bound procedure for a single-machine earliness scheduling problem with two agents, Applied Soft Computing, 13 (2013), 1042-1054. doi: 10.1016/j.asoc.2012.09.026. Google Scholar

[54]

Y. YinW.-H. WuS.-R. Cheng and C.-C. Wu, An investigation on a two-agent single-machine scheduling problem with unequal release dates, Computers & Operations Research, 39 (2012), 3062-3073. doi: 10.1016/j.cor.2012.03.012. Google Scholar

[55]

Y. YinW.-H. WuT. ChengC.-C. Wu and W.-H. Wu, A honey-bees optimization algorithm for a two-agent single-machine scheduling problem with ready times, Applied Mathematical Modelling, 39 (2015), 2587-2601. doi: 10.1016/j.apm.2014.10.044. Google Scholar

[56]

J. YuanC. Ng and T. E. Cheng, Two-agent single-machine scheduling with release dates and preemption to minimize the maximum lateness, Journal of Scheduling, 18 (2015), 147-153. doi: 10.1007/s10951-013-0360-y. Google Scholar

[57]

F. ZhangC. NgG. TangT. Cheng and Y. Lun, Inverse scheduling: Applications in shipping, International Journal of Shipping and Transport Logistics, 3 (2011), 312-322. doi: 10.1504/IJSTL.2011.040800. Google Scholar

Figure 1.  Variants of Objective Function
Table 1.  Summary of reviewed maximum lateness scheduling problem
Problem Complexity Reference Approach/Result
$1.~1~\ \left| ~L_{max}^{B}\le Q \right|~\mathop{\sum }^{}w_{i}^{A}C_{i}^{A}$ strongly NP-hard T. E. Cheng et al. (2008) Alessandro Agnetis et al. (2009) Branch-and-Bound method;
In an optimal schedule, A-jobs are scheduled in WSPT order, and B-jobs are scheduled in EDD order;
B-jobs are scheduled consecutively.
$2.~1\ ~\left| ~L_{max}^{B}\le Q,~{{r}_{i/j}} \right|~\mathop{\sum }^{}C_{i}^{A}$ unary NP-hard Yin et al. (2012) A-jobs are scheduled in SPT order, and B-jobs are scheduled in EDD order;
$3.~1\ ~\left| ~L_{max}^{B}\le Q,~{{r}_{i/j}} \right|~\mathop{\sum }^{}w_{i}^{A}C_{i}^{A}$ strongly NP-hard T. E. Cheng et al. (2013)Yin et al. (2015) Branch-and-Bound method;
Simulated Annealingalgorithm;
Marriage in Honey-bees Optimization algorithm;
In an optimal schedule, (1) the job i needs to be scheduled before job j, if ri+pi≤rj for any jobs in both agents; (2) CiA≤ri+1A for the jobs of the first agent and CjB-djB≤Q for the jobs of the second agent.
$4.1\ |L_{max}^{B}\le Q,{{r}_{(i/j)}}|\sum{T_{i}^{A}}$ unary NP-hard Yin et al. (2012)Lee et al. (2012)Baptiste et al. (2004) Branch-and-Bound algorithm;
Mixed Integer Programming model;
Marriage in Honey-Bees Optimization algorithm;
In the initialization step, B-jobs are scheduled in EDD order, A-jobs are scheduled in non-decreasing order of their sums of processing time and release time.Genetic Algorithm.
$\begin{align} &5.\text{ }\!\!~\!\!\text{ }1\text{ }\!\!~\!\!\text{ }\left| \text{ }\!\!~\!\!\text{ }L_{max}^{B}\le Q\text{ }\!\!~\!\!\text{ } \right|\text{ }\!\!~\!\!\text{ }L_{max}^{A}\text{ }\!\!~\!\!\text{ }\!\!~\!\!\text{ }\left( \text{P}1 \right), \\ &1\text{ }\!\!~\!\!\text{ }\left| \text{ }\!\!~\!\!\text{ }L_{max}^{B}\le Q\text{ }\!\!~\!\!\text{ } \right|\text{ }\!\!~\!\!\text{ }\mathop{\sum }^{}T_{i}^{A}\text{ }\!\!~\!\!\text{ }\left( \text{P}2 \right), \\ &1\text{ }\!\!~\!\!\text{ }\left| \text{ }\!\!~\!\!\text{ }L_{max}^{B}\le Q\text{ }\!\!~\!\!\text{ } \right|\text{ }\!\!~\!\!\text{ }\mathop{\sum }^{}w_{i}^{A}T_{i}^{A}\left( \text{P}3 \right), \\ &1\text{ }\!\!~\!\!\text{ }\left| L_{max}^{B}\le Q \right|\mathop{\sum }^{}U_{i}^{A}\text{ }\!\!~\!\!\text{ }\left( \text{P}4 \right), \\ &1\text{ }\!\!~\!\!\text{ }\left| L_{max}^{B}\le Q \right|\mathop{\sum }^{}U_{i}^{A}\text{ }\!\!~\!\!\text{ }\left( \text{P}4 \right), \\ &1\text{ }\!\!~\!\!\text{ }|L_{max}^{B}\le Q|\mathop{\sum }^{}w_{i}^{A}U_{i}^{A}\text{ }\!\!~\!\!\text{ }\left( \text{P}5 \right) \\ \end{align}$ NP-hard Wang et al. (2015) There exists an optimal solution, A-jobs are scheduled in SPT-EDD order for P1 and P2; A-jobs are scheduled in SPT order for P3, P4 and P5; B-jobs are scheduled in SPT-EDD order for all five problems.
$6.1~|~\mathop{\sum }^{}L_{max}^{B}\le Q,~~~{{r}_{i/j}}~|~\mathop{\sum }^{}U_{i}^{A}$ strongly NP-hard Yin, Cheng, et al. (2013) Branch-and-Bound method; Simulated Annealing algorithm.
$7.~1~\left| ~L_{max}^{B}\le Q~ \right|~\mathop{\sum }^{}V_{i}^{A}$ NP-hard Wang et al. (2017) Branch-and-Bound method;
Tabu-Search Heuristic;
In an optimal schedule, (1) all A-jobs and B-jobs are processed consecutively without idle time and the first job starts at time 0; (2) all early and partially early A-jobs and all B-jobs are scheduled before all tardy A-jobs; (3) the early and partially early A-jobs are scheduled in EDD order; (4) the B-jobs are scheduled in non-decreasing order of Q-djB
$8.1|\max \{f_{j}^{B}(C_{j}^{B})\}\le Q,{{r}_{(i/j)}},pmtn|L_{max}^{A}$ O(nAnlogn) Yuan et al. (2015) Algorithm Pmtn-LS (optimal algorithm);
EDD rule.
Problem Complexity Reference Approach/Result
$1.~1~\ \left| ~L_{max}^{B}\le Q \right|~\mathop{\sum }^{}w_{i}^{A}C_{i}^{A}$ strongly NP-hard T. E. Cheng et al. (2008) Alessandro Agnetis et al. (2009) Branch-and-Bound method;
In an optimal schedule, A-jobs are scheduled in WSPT order, and B-jobs are scheduled in EDD order;
B-jobs are scheduled consecutively.
$2.~1\ ~\left| ~L_{max}^{B}\le Q,~{{r}_{i/j}} \right|~\mathop{\sum }^{}C_{i}^{A}$ unary NP-hard Yin et al. (2012) A-jobs are scheduled in SPT order, and B-jobs are scheduled in EDD order;
$3.~1\ ~\left| ~L_{max}^{B}\le Q,~{{r}_{i/j}} \right|~\mathop{\sum }^{}w_{i}^{A}C_{i}^{A}$ strongly NP-hard T. E. Cheng et al. (2013)Yin et al. (2015) Branch-and-Bound method;
Simulated Annealingalgorithm;
Marriage in Honey-bees Optimization algorithm;
In an optimal schedule, (1) the job i needs to be scheduled before job j, if ri+pi≤rj for any jobs in both agents; (2) CiA≤ri+1A for the jobs of the first agent and CjB-djB≤Q for the jobs of the second agent.
$4.1\ |L_{max}^{B}\le Q,{{r}_{(i/j)}}|\sum{T_{i}^{A}}$ unary NP-hard Yin et al. (2012)Lee et al. (2012)Baptiste et al. (2004) Branch-and-Bound algorithm;
Mixed Integer Programming model;
Marriage in Honey-Bees Optimization algorithm;
In the initialization step, B-jobs are scheduled in EDD order, A-jobs are scheduled in non-decreasing order of their sums of processing time and release time.Genetic Algorithm.
$\begin{align} &5.\text{ }\!\!~\!\!\text{ }1\text{ }\!\!~\!\!\text{ }\left| \text{ }\!\!~\!\!\text{ }L_{max}^{B}\le Q\text{ }\!\!~\!\!\text{ } \right|\text{ }\!\!~\!\!\text{ }L_{max}^{A}\text{ }\!\!~\!\!\text{ }\!\!~\!\!\text{ }\left( \text{P}1 \right), \\ &1\text{ }\!\!~\!\!\text{ }\left| \text{ }\!\!~\!\!\text{ }L_{max}^{B}\le Q\text{ }\!\!~\!\!\text{ } \right|\text{ }\!\!~\!\!\text{ }\mathop{\sum }^{}T_{i}^{A}\text{ }\!\!~\!\!\text{ }\left( \text{P}2 \right), \\ &1\text{ }\!\!~\!\!\text{ }\left| \text{ }\!\!~\!\!\text{ }L_{max}^{B}\le Q\text{ }\!\!~\!\!\text{ } \right|\text{ }\!\!~\!\!\text{ }\mathop{\sum }^{}w_{i}^{A}T_{i}^{A}\left( \text{P}3 \right), \\ &1\text{ }\!\!~\!\!\text{ }\left| L_{max}^{B}\le Q \right|\mathop{\sum }^{}U_{i}^{A}\text{ }\!\!~\!\!\text{ }\left( \text{P}4 \right), \\ &1\text{ }\!\!~\!\!\text{ }\left| L_{max}^{B}\le Q \right|\mathop{\sum }^{}U_{i}^{A}\text{ }\!\!~\!\!\text{ }\left( \text{P}4 \right), \\ &1\text{ }\!\!~\!\!\text{ }|L_{max}^{B}\le Q|\mathop{\sum }^{}w_{i}^{A}U_{i}^{A}\text{ }\!\!~\!\!\text{ }\left( \text{P}5 \right) \\ \end{align}$ NP-hard Wang et al. (2015) There exists an optimal solution, A-jobs are scheduled in SPT-EDD order for P1 and P2; A-jobs are scheduled in SPT order for P3, P4 and P5; B-jobs are scheduled in SPT-EDD order for all five problems.
$6.1~|~\mathop{\sum }^{}L_{max}^{B}\le Q,~~~{{r}_{i/j}}~|~\mathop{\sum }^{}U_{i}^{A}$ strongly NP-hard Yin, Cheng, et al. (2013) Branch-and-Bound method; Simulated Annealing algorithm.
$7.~1~\left| ~L_{max}^{B}\le Q~ \right|~\mathop{\sum }^{}V_{i}^{A}$ NP-hard Wang et al. (2017) Branch-and-Bound method;
Tabu-Search Heuristic;
In an optimal schedule, (1) all A-jobs and B-jobs are processed consecutively without idle time and the first job starts at time 0; (2) all early and partially early A-jobs and all B-jobs are scheduled before all tardy A-jobs; (3) the early and partially early A-jobs are scheduled in EDD order; (4) the B-jobs are scheduled in non-decreasing order of Q-djB
$8.1|\max \{f_{j}^{B}(C_{j}^{B})\}\le Q,{{r}_{(i/j)}},pmtn|L_{max}^{A}$ O(nAnlogn) Yuan et al. (2015) Algorithm Pmtn-LS (optimal algorithm);
EDD rule.
Table 2.  Summary of problems and their computational complexity studied by S.-R. Cheng (2014)
Problem Complexity
$1~\left| ~f_{max}^{B}\le Q~ \right|\max f_{j}^{X}\left( E_{j}^{X} \right)$ $O\left( {{\left( {{n}_{A}}+{{n}_{B}} \right)}^{2}} \right)$
$1~\left| ~f_{max}^{B}\le Q~ \right|\mathop{\sum }^{}w_{j}^{X}E_{j}^{X}$ Strongly NP-hard
$1~\left| ~f_{max}^{B}\le Q,~AD~ \right|\mathop{\sum }^{}E_{j}^{X}$ $O\left( {{n}_{A}}\log {{n}_{A}}+\left( {{n}_{A}}+{{n}_{B}} \right)\left( {{n}_{B}}+1 \right) \right)$
$1~\left| ~f_{max}^{B}\le Q,~AW~ \right|\mathop{\sum }^{}w_{j}^{X}E_{j}^{X}$ $O\left( {{n}_{A}}\log {{n}_{A}}+\left( {{n}_{A}}+{{n}_{B}} \right)\left( {{n}_{B}}+1 \right) \right)$
$1~\left| ~E_{max}^{B}\le Q~ \right|\mathop{\sum }^{}w_{j}^{X}\left( E_{j}^{X}+T_{j}^{X} \right)$ strongly NP-hard
$1~\left| ~T_{max}^{B}\le Q~ \right|\mathop{\sum }^{}w_{j}^{X}\left( E_{j}^{X}+T_{j}^{X} \right)$ strongly NP-hard
$1~\left| ~\mathop{\sum }^{}E_{j}^{B}\le Q~ \right|\mathop{\sum }^{}w_{j}^{X}\left( E_{j}^{X}+T_{j}^{X} \right)$ strongly NP-hard
$1~\left| ~\mathop{\sum }^{}T_{j}^{B}\le Q~ \right|\mathop{\sum }^{}w_{j}^{X}\left( E_{j}^{X}+T_{j}^{X} \right)$ strongly NP-hard
$1~\left| ~\mathop{\sum }^{}\left( E_{j}^{B}+T_{j}^{B} \right)\le Q~ \right|\mathop{\sum }^{}w_{j}^{X}\left( E_{j}^{X}+T_{j}^{X} \right)$ strongly NP-hard
Problem Complexity
$1~\left| ~f_{max}^{B}\le Q~ \right|\max f_{j}^{X}\left( E_{j}^{X} \right)$ $O\left( {{\left( {{n}_{A}}+{{n}_{B}} \right)}^{2}} \right)$
$1~\left| ~f_{max}^{B}\le Q~ \right|\mathop{\sum }^{}w_{j}^{X}E_{j}^{X}$ Strongly NP-hard
$1~\left| ~f_{max}^{B}\le Q,~AD~ \right|\mathop{\sum }^{}E_{j}^{X}$ $O\left( {{n}_{A}}\log {{n}_{A}}+\left( {{n}_{A}}+{{n}_{B}} \right)\left( {{n}_{B}}+1 \right) \right)$
$1~\left| ~f_{max}^{B}\le Q,~AW~ \right|\mathop{\sum }^{}w_{j}^{X}E_{j}^{X}$ $O\left( {{n}_{A}}\log {{n}_{A}}+\left( {{n}_{A}}+{{n}_{B}} \right)\left( {{n}_{B}}+1 \right) \right)$
$1~\left| ~E_{max}^{B}\le Q~ \right|\mathop{\sum }^{}w_{j}^{X}\left( E_{j}^{X}+T_{j}^{X} \right)$ strongly NP-hard
$1~\left| ~T_{max}^{B}\le Q~ \right|\mathop{\sum }^{}w_{j}^{X}\left( E_{j}^{X}+T_{j}^{X} \right)$ strongly NP-hard
$1~\left| ~\mathop{\sum }^{}E_{j}^{B}\le Q~ \right|\mathop{\sum }^{}w_{j}^{X}\left( E_{j}^{X}+T_{j}^{X} \right)$ strongly NP-hard
$1~\left| ~\mathop{\sum }^{}T_{j}^{B}\le Q~ \right|\mathop{\sum }^{}w_{j}^{X}\left( E_{j}^{X}+T_{j}^{X} \right)$ strongly NP-hard
$1~\left| ~\mathop{\sum }^{}\left( E_{j}^{B}+T_{j}^{B} \right)\le Q~ \right|\mathop{\sum }^{}w_{j}^{X}\left( E_{j}^{X}+T_{j}^{X} \right)$ strongly NP-hard
Table 3.  Summary of reviewed earliness, lateness and tardiness related two-agent scheduling problem
Problem Complexity Reference Approach/Result
$\begin{align} &1.\text{ }\!\!~\!\!\text{ }1\text{ }\!\!~\!\!\text{ }\!\!|\!\!\text{ }\max (w_{j}^{B}E_{j}^{B}+w_{j}^{B}T_{j}^{B}\text{)}\le \\ &Q,\text{ }\!\!~\!\!\text{ }p_{i}^{A}=p_{j}^{B}=p,\text{ }\!\!~\!\!\text{ }d_{i}^{A}=d_{j}^{B}= \\ &d\text{ }\!\!~\!\!\text{ }|\text{ }\!\!~\!\!\text{ }\mathop{\sum }^{}\left( w_{i}^{A}E_{i}^{A}+w_{i}^{A}T_{i}^{A} \right) \\ \end{align}$ -- Gerstl and Mosheiov (2013) Reduce the problem to a single linear assignment problem (LAP). The global optimum is determined by the minimal-cost LAP.
In an optimal solution, (1) the first scheduled job starts at time zero, or (2) at least one B-job has cost value of the upper bound, or (3) a A-job is completed exactly at the due date
$2.~1\left| E_{max}^{B}\le Q \right|~\mathop{\sum }^{}w_{i}^{A}E_{i}^{A}+\mathop{\sum }^{}w_{j}^{B}E_{j}^{B}$ strongly NP-hard Yin, Wu, et al. (2013) Mathematical Programming Formulation method;
Branch-and-Bound method;
Simulated Annealing algorithm.
$3.~1~\left| ~E_{max}^{B}\le Q~ \right|~E_{max}^{A}$ binary NP-hard Mor and Mosheiov (2010) A Heuristic
There exists an optimal solution, if (1) the first job starts at time D-(PA+PB), where D represents the common due date, PA and PB represents the total processing time of A-jobs and B-jobs, respectively, (2) B-jobs are scheduled in a non-decreasing order of djB-pjB (i.e. MST order), and (3) A-jobs are scheduled in MST order.
$4.~1~\left| ~E_{max}^{B}\le Q~ \right|~\mathop{\sum }^{}w_{i}^{A}E_{i}^{A}$ strongly NP-hard Mor and Mosheiov (2010) A WSPT and MST based Heuristic.
$5.1~\left| ~T_{max}^{B}\le Q,~~nr-a~ \right|~\mathop{\sum }^{}C_{i}^{A}$ strongly NP-hard Yazdani and Jolai (2013) Genetic Algorihtm
Problem Complexity Reference Approach/Result
$\begin{align} &1.\text{ }\!\!~\!\!\text{ }1\text{ }\!\!~\!\!\text{ }\!\!|\!\!\text{ }\max (w_{j}^{B}E_{j}^{B}+w_{j}^{B}T_{j}^{B}\text{)}\le \\ &Q,\text{ }\!\!~\!\!\text{ }p_{i}^{A}=p_{j}^{B}=p,\text{ }\!\!~\!\!\text{ }d_{i}^{A}=d_{j}^{B}= \\ &d\text{ }\!\!~\!\!\text{ }|\text{ }\!\!~\!\!\text{ }\mathop{\sum }^{}\left( w_{i}^{A}E_{i}^{A}+w_{i}^{A}T_{i}^{A} \right) \\ \end{align}$ -- Gerstl and Mosheiov (2013) Reduce the problem to a single linear assignment problem (LAP). The global optimum is determined by the minimal-cost LAP.
In an optimal solution, (1) the first scheduled job starts at time zero, or (2) at least one B-job has cost value of the upper bound, or (3) a A-job is completed exactly at the due date
$2.~1\left| E_{max}^{B}\le Q \right|~\mathop{\sum }^{}w_{i}^{A}E_{i}^{A}+\mathop{\sum }^{}w_{j}^{B}E_{j}^{B}$ strongly NP-hard Yin, Wu, et al. (2013) Mathematical Programming Formulation method;
Branch-and-Bound method;
Simulated Annealing algorithm.
$3.~1~\left| ~E_{max}^{B}\le Q~ \right|~E_{max}^{A}$ binary NP-hard Mor and Mosheiov (2010) A Heuristic
There exists an optimal solution, if (1) the first job starts at time D-(PA+PB), where D represents the common due date, PA and PB represents the total processing time of A-jobs and B-jobs, respectively, (2) B-jobs are scheduled in a non-decreasing order of djB-pjB (i.e. MST order), and (3) A-jobs are scheduled in MST order.
$4.~1~\left| ~E_{max}^{B}\le Q~ \right|~\mathop{\sum }^{}w_{i}^{A}E_{i}^{A}$ strongly NP-hard Mor and Mosheiov (2010) A WSPT and MST based Heuristic.
$5.1~\left| ~T_{max}^{B}\le Q,~~nr-a~ \right|~\mathop{\sum }^{}C_{i}^{A}$ strongly NP-hard Yazdani and Jolai (2013) Genetic Algorihtm
Table 4.  Summary of reviewed number of tardy jobs related two-agent scheduling problem
Problem Complexity Reference Approach/Result
$1.1~\left| ~\mathop{\sum }^{}U_{j}^{B}\le Q~ \right|~\mathop{\sum }^{}U_{i}^{A}$ $O\left( {{n}^{3}} \right)$ Allesandro Agnetis et al. (2004) Dynamic Programming.
In an optimal solution, (1) all early jobs are scheduled consecutively in EDD order at the beginning of the schedule; (2) all tardy jobs are scheduled consecutively at the end of the schedule.
$2.~1~\left| ~\mathop{\sum }^{}U_{j}^{B}\le Q~ \right|~\mathop{\sum }^{}C_{i}^{A}$ open Allesandro Agnetis et al. (2004)Ng et al. (2006)Leung et al. (2010) A Pseudo Polynomial Time Algorithm.
In an optimal solution, all A-jobs are ordered in SPT order, and all B-jobs are scheduled in EDD order.
$3.~1~\left| ~\mathop{\sum }^{}U_{j}^{B}\le Q~ \right|~\mathop{\sum }^{}w_{i}^{A}C_{i}^{A}$ binary NP-hard Allesandro Agnetis et al. (2004)Ng et al. (2006) --
$4.~1~\left| ~\mathop{\sum }^{}U_{j}^{B}=0~ \right|~\mathop{\sum }^{}w_{i}^{A}C_{i}^{A}$ strongly NP-hard Allesandro Agnetis et al. (2004)Ng et al. (2006) --
$5.~1~\left| ~\mathop{\sum }^{}U_{j}^{B}\le Q~ \right|~\mathop{\sum }^{}T_{i}^{A}$ binary NP-hard Leung et al. (2010) --
$6.1~\left| ~\mathop{\sum }^{}U_{j}^{B}=0~ \right|~\theta ~\mathop{\sum }^{}C_{i}^{A}+\left( 1-\theta \right)~L_{max}^{A}$, where 0 < θ < 1 strongly NP-hard Lee et al. (2013) Branch-and-Bound method;
A combined simulated annealing (SA) algorithm:
EDD rule and SPT rule; Neighborhood Generation Methods: PI, EFSR and EBSR.
$7.1~\left| ~\mathop{\sum }^{}U_{j}^{B}=0~ \right|~\mathop{\sum }^{}T_{i}^{A}$ NP-hard Wu (2013) Branch-and-Bound method;
Genetic Algorithm.
$8.~1~\left| ~\mathop{\sum }^{}w_{j}^{B}U_{j}^{B}\le Q~ \right|~\mathop{\sum }^{}w_{i}^{A}L_{i}^{A}$ NP-hard Wu (2013)Reisi-Nafchi and Moslehi (2015) An Integer Linear Programming model;
A hybrid meta-heuristic algorithm:
Combing a genetic algorithm and lnear programming
There exists an optimal solution, (1) A-jobs are scheduled in WSPT order; (2) in which the agent B tardy accepted orders are sequenced arbitrarily at the end of sequence; (3) in which the global arrangement of the agent B non-tardy accepted orders follows the EDD order and they are replced at the last possible positions before their due time.
$9.~1~\left| ~\mathop{\sum }^{}U_{j}^{B}=0,~~r,~~p=\text{ }\!\!\alpha\!\!\text{ }+\beta t \right|~\mathop{\sum }^{}w_{i}^{A}C_{i}^{A}$ strongly NP-hard Lee et al. (2010) Branch-and-Bound method;
A Heuristic algorithm.
An optimal schedule exists such that job i is the preceding job of job j when ri+pirj
Problem Complexity Reference Approach/Result
$1.1~\left| ~\mathop{\sum }^{}U_{j}^{B}\le Q~ \right|~\mathop{\sum }^{}U_{i}^{A}$ $O\left( {{n}^{3}} \right)$ Allesandro Agnetis et al. (2004) Dynamic Programming.
In an optimal solution, (1) all early jobs are scheduled consecutively in EDD order at the beginning of the schedule; (2) all tardy jobs are scheduled consecutively at the end of the schedule.
$2.~1~\left| ~\mathop{\sum }^{}U_{j}^{B}\le Q~ \right|~\mathop{\sum }^{}C_{i}^{A}$ open Allesandro Agnetis et al. (2004)Ng et al. (2006)Leung et al. (2010) A Pseudo Polynomial Time Algorithm.
In an optimal solution, all A-jobs are ordered in SPT order, and all B-jobs are scheduled in EDD order.
$3.~1~\left| ~\mathop{\sum }^{}U_{j}^{B}\le Q~ \right|~\mathop{\sum }^{}w_{i}^{A}C_{i}^{A}$ binary NP-hard Allesandro Agnetis et al. (2004)Ng et al. (2006) --
$4.~1~\left| ~\mathop{\sum }^{}U_{j}^{B}=0~ \right|~\mathop{\sum }^{}w_{i}^{A}C_{i}^{A}$ strongly NP-hard Allesandro Agnetis et al. (2004)Ng et al. (2006) --
$5.~1~\left| ~\mathop{\sum }^{}U_{j}^{B}\le Q~ \right|~\mathop{\sum }^{}T_{i}^{A}$ binary NP-hard Leung et al. (2010) --
$6.1~\left| ~\mathop{\sum }^{}U_{j}^{B}=0~ \right|~\theta ~\mathop{\sum }^{}C_{i}^{A}+\left( 1-\theta \right)~L_{max}^{A}$, where 0 < θ < 1 strongly NP-hard Lee et al. (2013) Branch-and-Bound method;
A combined simulated annealing (SA) algorithm:
EDD rule and SPT rule; Neighborhood Generation Methods: PI, EFSR and EBSR.
$7.1~\left| ~\mathop{\sum }^{}U_{j}^{B}=0~ \right|~\mathop{\sum }^{}T_{i}^{A}$ NP-hard Wu (2013) Branch-and-Bound method;
Genetic Algorithm.
$8.~1~\left| ~\mathop{\sum }^{}w_{j}^{B}U_{j}^{B}\le Q~ \right|~\mathop{\sum }^{}w_{i}^{A}L_{i}^{A}$ NP-hard Wu (2013)Reisi-Nafchi and Moslehi (2015) An Integer Linear Programming model;
A hybrid meta-heuristic algorithm:
Combing a genetic algorithm and lnear programming
There exists an optimal solution, (1) A-jobs are scheduled in WSPT order; (2) in which the agent B tardy accepted orders are sequenced arbitrarily at the end of sequence; (3) in which the global arrangement of the agent B non-tardy accepted orders follows the EDD order and they are replced at the last possible positions before their due time.
$9.~1~\left| ~\mathop{\sum }^{}U_{j}^{B}=0,~~r,~~p=\text{ }\!\!\alpha\!\!\text{ }+\beta t \right|~\mathop{\sum }^{}w_{i}^{A}C_{i}^{A}$ strongly NP-hard Lee et al. (2010) Branch-and-Bound method;
A Heuristic algorithm.
An optimal schedule exists such that job i is the preceding job of job j when ri+pirj
Table 5.  Summary of reviewed late work criteria related two-agent scheduling problems
Problem Complexity Reference Approach/Result
$1.~~1~\left| ~f_{max}^{B}\le Q~ \right|~\mathop{\sum }^{}w_{i}^{A}V_{i}^{A}$ $O({{n}_{A}}^{2}Q\left( \underset{i=1}{\overset{{{n}_{A}}}{\mathop \sum }}\,p_{i}^{A}+\underset{j=1}{\overset{{{n}_{B}}}{\mathop \sum }}\,p_{j}^{B} \right)+{{n}_{B}}\log {{n}_{B}}$ Xingong and Yong (2016) In an optimal schedule, all B-jobs are scheduled in the reserved interval it associated with.
The pre-emption constraint does not impact the optimal solution
$2.~~1~\left| ~f_{max}^{B}\le Q,~~d_{i}^{A}={{d}^{A}}~ \right|~\mathop{\sum }^{}w_{i}^{A}V_{i}^{A}$ $O\left( {{n}_{A}}\log {{n}_{A}}+{{n}_{B}}\log {{n}_{B}} \right)$
$3.~1~\left| ~f_{max}^{B}\le Q,~~p_{i}^{A}={{p}^{A}}~ \right|~\mathop{\sum }^{}w_{i}^{A}V_{i}^{A}$ $O\left( {{n}_{A}}^{3}+{{n}_{B}}\log {{n}_{B}} \right)$
$4.~1\left| ~L_{max}^{B}\le Q \right|\mathop{\sum }^{}V_{i}^{A}$ NP-hard Wang et al. (2017) Branch-and-Bound method;
Tabu-Search Heuristic;
In an optimal schedule, (1) all A-jobs and B-jobs are processed consecutively without idle time and the first job starts at time 0; (2) all early and partially early A-jobs and all B-jobs are scheduled before all tardy A-jobs; (3) the early and partially early A-jobs are scheduled in EDD order; (4) the B-jobs are scheduled in non-decreasing order of Q-djB
Problem Complexity Reference Approach/Result
$1.~~1~\left| ~f_{max}^{B}\le Q~ \right|~\mathop{\sum }^{}w_{i}^{A}V_{i}^{A}$ $O({{n}_{A}}^{2}Q\left( \underset{i=1}{\overset{{{n}_{A}}}{\mathop \sum }}\,p_{i}^{A}+\underset{j=1}{\overset{{{n}_{B}}}{\mathop \sum }}\,p_{j}^{B} \right)+{{n}_{B}}\log {{n}_{B}}$ Xingong and Yong (2016) In an optimal schedule, all B-jobs are scheduled in the reserved interval it associated with.
The pre-emption constraint does not impact the optimal solution
$2.~~1~\left| ~f_{max}^{B}\le Q,~~d_{i}^{A}={{d}^{A}}~ \right|~\mathop{\sum }^{}w_{i}^{A}V_{i}^{A}$ $O\left( {{n}_{A}}\log {{n}_{A}}+{{n}_{B}}\log {{n}_{B}} \right)$
$3.~1~\left| ~f_{max}^{B}\le Q,~~p_{i}^{A}={{p}^{A}}~ \right|~\mathop{\sum }^{}w_{i}^{A}V_{i}^{A}$ $O\left( {{n}_{A}}^{3}+{{n}_{B}}\log {{n}_{B}} \right)$
$4.~1\left| ~L_{max}^{B}\le Q \right|\mathop{\sum }^{}V_{i}^{A}$ NP-hard Wang et al. (2017) Branch-and-Bound method;
Tabu-Search Heuristic;
In an optimal schedule, (1) all A-jobs and B-jobs are processed consecutively without idle time and the first job starts at time 0; (2) all early and partially early A-jobs and all B-jobs are scheduled before all tardy A-jobs; (3) the early and partially early A-jobs are scheduled in EDD order; (4) the B-jobs are scheduled in non-decreasing order of Q-djB
Table 6.  Summary of two-agent scheduling problems, computational complexity and approach/result studied by Baker and Smith (2003)
Problem Complexity Approach/Result
$1.~~~1~\left| ~ \right|~\left( L_{max}^{A},~~~L_{max}^{B} \right)$ NP-hard Processing the jobs of two agents in EDD rule;
Using dynamic programming to find an optimal solution.
$2.~~~1~\left| ~ \right|~\left( C_{max}^{A},~~~L_{max}^{B} \right)$ $O\left( {{n_2}\log \;{n_2}} \right)$ Processing the jobs of the first agent consecutively;
Processing the jobs of the other agent in EDD rule;
Polynomial time algorithm.
$3.~~~1~\left| ~ \right|~\left( \mathop{\sum }^{}w_{i}^{A}C_{i}^{A},~~~L_{max}^{B} \right)$ NP-complete Processing the jobs of the first agent may not in WSPT rule;
Processing the jobs of the other agent in EDD rule;
For a special case with equal weights, using SPT and EDD rule. It can be solved by using the dynamic programming.
$4.~~~1~\left| ~ \right|~\left( C_{max}^{A},~L_{max}^{B},~\mathop{\sum }^{}w_{j}^{C}C_{j}^{C} \right)$ NP-hard Processing the jobs of the first agent consecutively;
Combing the contributions of the objectives of the first and third agent;
Problem Complexity Approach/Result
$1.~~~1~\left| ~ \right|~\left( L_{max}^{A},~~~L_{max}^{B} \right)$ NP-hard Processing the jobs of two agents in EDD rule;
Using dynamic programming to find an optimal solution.
$2.~~~1~\left| ~ \right|~\left( C_{max}^{A},~~~L_{max}^{B} \right)$ $O\left( {{n_2}\log \;{n_2}} \right)$ Processing the jobs of the first agent consecutively;
Processing the jobs of the other agent in EDD rule;
Polynomial time algorithm.
$3.~~~1~\left| ~ \right|~\left( \mathop{\sum }^{}w_{i}^{A}C_{i}^{A},~~~L_{max}^{B} \right)$ NP-complete Processing the jobs of the first agent may not in WSPT rule;
Processing the jobs of the other agent in EDD rule;
For a special case with equal weights, using SPT and EDD rule. It can be solved by using the dynamic programming.
$4.~~~1~\left| ~ \right|~\left( C_{max}^{A},~L_{max}^{B},~\mathop{\sum }^{}w_{j}^{C}C_{j}^{C} \right)$ NP-hard Processing the jobs of the first agent consecutively;
Combing the contributions of the objectives of the first and third agent;
Table 7.  Summary of reviewed late work criteria related two-agent scheduling problems (Minimality Model)
Problem Complexity Reference Approach/Result
$1.1~\left| ~ \right|~~\theta \mathop{\sum }^{}C_{i}^{A}+\left( 1-\theta \right)\mathop{\sum }^{}T_{j}^{B}$ NP-hard T. E. Cheng et al. (2014) Branch-and-Bound method;
Genetic Algorithm;
Simulated Annealing algorithm;
In an optimal solution, (1) if jobs i and j are belonging the agent A, pi < pj, then job i should be scheduled before job j; (2) if jobs i and j are belonging the agent B, pi < pj and di < dj, then job i should be scheduled before job j
$2.~1~\left| ~ \right|~\mathop{\sum }^{}w_{i}^{A}T_{i}^{A}+\mathop{\sum }^{}w_{j}^{B}T_{j}^{B}$ NP-hard Wu et al. (2014) Branch-and-Bound method;
Ant Colony Optimization algorithm;
Simulated Annealing algorithm.
Problem Complexity Reference Approach/Result
$1.1~\left| ~ \right|~~\theta \mathop{\sum }^{}C_{i}^{A}+\left( 1-\theta \right)\mathop{\sum }^{}T_{j}^{B}$ NP-hard T. E. Cheng et al. (2014) Branch-and-Bound method;
Genetic Algorithm;
Simulated Annealing algorithm;
In an optimal solution, (1) if jobs i and j are belonging the agent A, pi < pj, then job i should be scheduled before job j; (2) if jobs i and j are belonging the agent B, pi < pj and di < dj, then job i should be scheduled before job j
$2.~1~\left| ~ \right|~\mathop{\sum }^{}w_{i}^{A}T_{i}^{A}+\mathop{\sum }^{}w_{j}^{B}T_{j}^{B}$ NP-hard Wu et al. (2014) Branch-and-Bound method;
Ant Colony Optimization algorithm;
Simulated Annealing algorithm.
[1]

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

[2]

Muminu O. Adamu, Aderemi O. Adewumi. Minimizing the weighted number of tardy jobs on multiple machines: A review. Journal of Industrial & Management Optimization, 2016, 12 (4) : 1465-1493. doi: 10.3934/jimo.2016.12.1465

[3]

Mostafa Abouei Ardakan, A. Kourank Beheshti, S. Hamid Mirmohammadi, Hamed Davari Ardakani. A hybrid meta-heuristic algorithm to minimize the number of tardy jobs in a dynamic two-machine flow shop problem. Numerical Algebra, Control & Optimization, 2017, 7 (4) : 465-480. doi: 10.3934/naco.2017029

[4]

Chuanli Zhao. An fptas for the weighted number of tardy jobs minimization on a single machine with deteriorating jobs. Journal of Industrial & Management Optimization, 2017, 13 (2) : 587-593. doi: 10.3934/jimo.2016033

[5]

Chuanli Zhao, Yunqiang Yin, T. C. E. Cheng, Chin-Chia Wu. Single-machine scheduling and due date assignment with rejection and position-dependent processing times. Journal of Industrial & Management Optimization, 2014, 10 (3) : 691-700. doi: 10.3934/jimo.2014.10.691

[6]

Peng Guo, Wenming Cheng, Yi Wang. A general variable neighborhood search for single-machine total tardiness scheduling problem with step-deteriorating jobs. Journal of Industrial & Management Optimization, 2014, 10 (4) : 1071-1090. doi: 10.3934/jimo.2014.10.1071

[7]

Chunlai Liu, Yanpeng Fan, Chuanli Zhao, Jianjun Wang. Multiple common due-dates assignment and optimal maintenance activity scheduling with linear deteriorating jobs. Journal of Industrial & Management Optimization, 2017, 13 (2) : 713-720. doi: 10.3934/jimo.2016042

[8]

Zhichao Geng, Jinjiang Yuan. Scheduling family jobs on an unbounded parallel-batch machine to minimize makespan and maximum flow time. Journal of Industrial & Management Optimization, 2018, 14 (4) : 1479-1500. doi: 10.3934/jimo.2018017

[9]

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

[10]

Güvenç Şahin, Ravindra K. Ahuja. Single-machine scheduling with stepwise tardiness costs and release times. Journal of Industrial & Management Optimization, 2011, 7 (4) : 825-848. doi: 10.3934/jimo.2011.7.825

[11]

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

[12]

Cuixia Miao, Yuzhong Zhang. Scheduling with step-deteriorating jobs to minimize the makespan. Journal of Industrial & Management Optimization, 2019, 15 (4) : 1955-1964. doi: 10.3934/jimo.2018131

[13]

Futoshi Takahashi. On the number of maximum points of least energy solution to a two-dimensional Hénon equation with large exponent. Communications on Pure & Applied Analysis, 2013, 12 (3) : 1237-1241. doi: 10.3934/cpaa.2013.12.1237

[14]

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

[15]

Y. K. Lin, C. S. Chong. A tabu search algorithm to minimize total weighted tardiness for the job shop scheduling problem. Journal of Industrial & Management Optimization, 2016, 12 (2) : 703-717. doi: 10.3934/jimo.2016.12.703

[16]

Chengxin Luo. Single machine batch scheduling problem to minimize makespan with controllable setup and jobs processing times. Numerical Algebra, Control & Optimization, 2015, 5 (1) : 71-77. doi: 10.3934/naco.2015.5.71

[17]

Le Thi Hoai An, Tran Duc Quynh, Kondo Hloindo Adjallah. A difference of convex functions algorithm for optimal scheduling and real-time assignment of preventive maintenance jobs on parallel processors. Journal of Industrial & Management Optimization, 2014, 10 (1) : 243-258. doi: 10.3934/jimo.2014.10.243

[18]

Ji-Bo Wang, Mengqi Liu, Na Yin, Ping Ji. Scheduling jobs with controllable processing time, truncated job-dependent learning and deterioration effects. Journal of Industrial & Management Optimization, 2017, 13 (2) : 1025-1039. doi: 10.3934/jimo.2016060

[19]

David Auger, Irène Charon, Iiro Honkala, Olivier Hudry, Antoine Lobstein. Edge number, minimum degree, maximum independent set, radius and diameter in twin-free graphs. Advances in Mathematics of Communications, 2009, 3 (1) : 97-114. doi: 10.3934/amc.2009.3.97

[20]

Yibo Zhang, Jinfeng Gao, Jia Ren, Huijiao Wang. A type of new consensus protocol for two-dimension multi-agent systems. Numerical Algebra, Control & Optimization, 2017, 7 (3) : 345-357. doi: 10.3934/naco.2017022

2018 Impact Factor: 1.025

Metrics

  • PDF downloads (16)
  • HTML views (283)
  • Cited by (0)

Other articles
by authors

[Back to Top]