×

A survey of due-date related single-machine with two-agent scheduling problem. (English) Zbl 1449.90110

Summary: 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.

MSC:

90B35 Deterministic scheduling theory in operations research
68M20 Performance evaluation, queueing, and scheduling in the context of computer systems
90-02 Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] A. Agnetis; G. de Pascale; D. Pacciarelli, A Lagrangian approach to single-machine scheduling problems with two competing agents, Journal of Scheduling, 12, 401-415 (2009) · Zbl 1185.90063 · doi:10.1007/s10951-008-0098-0
[2] A. Agnetis; P. B. Mirchandani; D. Pacciarelli; A. Pacifici, Scheduling problems with two competing agents, Operations Research, 52, 229-242 (2004) · Zbl 1165.90446 · doi:10.1287/opre.1030.0092
[3] K. R. Baker; J. Cole Smith, A multiple-criterion model for machine scheduling, Journal of Scheduling, 6, 7-16 (2003) · Zbl 1154.90406 · doi:10.1023/A:1022231419049
[4] P. Baptiste; J. Carlier; A. Jouglet, A branch-and-bound procedure to minimize total tardiness on one machine with arbitrary release dates, European Journal of Operational Research, 158, 595-608 (2004) · Zbl 1056.90054 · doi:10.1016/S0377-2217(03)00378-3
[5] J. Blazewicz, Scheduling preemptible tasks on parallel processors with information k s., (1984). · Zbl 0565.68037
[6] J. Błazewicz; M. Drozdowski; P. Formanowicz; W. Kubiak; G. Schmidt, Scheduling preemptable tasks on parallel processors with limited availability, Parallel Computing, 26, 1195-1211 (2000) · Zbl 0945.68015 · doi:10.1016/S0167-8191(00)00035-1
[7] P. J. Brewer; 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, 857-886 (1996) · doi:10.1016/0167-7187(96)01014-4
[8] S.-R. Cheng, Some new problems on two-agent scheduling to minimize the earliness costs, International Journal of Production Economics, 156, 24-30 (2014) · doi:10.1016/j.ijpe.2014.05.004
[9] T. E. Cheng; Y.-H. Chung; S.-C. Liao; W.-C. Lee, Two-agent singe-machine scheduling with release times to minimize the total weighted completion time, Computers & Operations Research, 40, 353-361 (2013) · Zbl 1349.90329 · doi:10.1016/j.cor.2012.07.013
[10] T. E. Cheng; C.-Y. Liu; W.-C. Lee; M. Ji, Two-agent single-machine scheduling to minimize the weighted sum of the agents’ objective functions, Computers & Industrial Engineering, 78, 66-73 (2014) · doi:10.1016/j.cie.2014.09.028
[11] T. E. Cheng; C. Ng; J. Yuan, Multi-agent scheduling on a single machine with max-form criteria, European Journal of Operational Research, 188, 603-609 (2008) · Zbl 1129.90023 · doi:10.1016/j.ejor.2007.04.040
[12] D. Elvikis; H. W. Hamacher; V. T’kindt, Scheduling two agents on uniform parallel machines with makespan and cost functions, Journal of Scheduling, 14, 471-481 (2011) · Zbl 1280.90042 · doi:10.1007/s10951-010-0201-1
[13] D. Elvikis; V. T’kindt, Two-agent scheduling on uniform parallel machines with min-max criteria, Annals of Operations Research, 213, 79-94 (2014) · Zbl 1296.90043 · doi:10.1007/s10479-012-1099-0
[14] E. Gerstl; G. Mosheiov, Scheduling problems with two competing agents to minimized weighted earliness-tardiness, Computers & Operations Research, 40, 109-116 (2013) · Zbl 1349.90347 · doi:10.1016/j.cor.2012.05.019
[15] E. Gerstl; G. Mosheiov, Single machine just-in-time scheduling problems with two competing agents, Naval Research Logistics (NRL), 61, 1-16 (2014) · Zbl 1411.90144 · doi:10.1002/nav.21562
[16] A. M. Hariri; C. N. Potts; L. N. Van Wassenhove, Single machine scheduling to minimize total weighted late work, ORSA Journal on Computing, 7, 232-242 (1995) · Zbl 0859.90084
[17] W. Horn, Some simple scheduling algorithms, Naval Research Logistics (NRL), 21, 177-185 (1974) · Zbl 0276.90024 · doi:10.1002/nav.3800210113
[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. · Zbl 1467.68065
[19] S. Kirkpatrick; C. D. Gelatt; M. P. Vecchi, Optimization by simulated annealing, Science, 220, 671-680 (1983) · Zbl 1225.90162 · doi:10.1126/science.220.4598.671
[20] W.-C. Lee; Y.-H. Chung; M.-C. Hu, Genetic algorithms for a two-agent single-machine problem with release time, Applied Soft Computing, 12, 3580-3589 (2012) · doi:10.1016/j.asoc.2012.06.015
[21] W.-C. Lee; Y.-H. Chung; Z.-R. Huang, A single-machine bi-criterion scheduling problem with two agents, Applied Mathematics and Computation, 219, 10831-10841 (2013) · Zbl 1302.90086 · doi:10.1016/j.amc.2013.05.025
[22] W.-C. Lee; W.-J. Wang; Y.-R. Shiau; C.-C. Wu, A single-machine scheduling problem with two-agent and deteriorating jobs, Applied Mathematical Modelling, 34, 3098-3107 (2010) · Zbl 1201.90080 · doi:10.1016/j.apm.2010.01.015
[23] J. Y.-T. Leung; M. Pinedo; G. Wan, Competitive two-agent scheduling and its applications, Operations Research, 58, 458-469 (2010) · Zbl 1233.90163 · doi:10.1287/opre.1090.0744
[24] H. Li; Y. Gajpal; C. Bector, Single machine scheduling with two-agent for total weighted completion time objectives, Applied Soft Computing, 70, 147-156 (2018) · doi:10.1016/j.asoc.2018.05.027
[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.
[26] M. Mezmaz; N. Melab; Y. Kessaci; Y. C. Lee; E.-G. Talbi; A. Y. Zomaya; D. Tuyttens, A parallel bi-objective hybrid metaheuristic for energy-aware scheduling for cloud computing systems, Journal of Parallel and Distributed Computing, 71, 1497-1508 (2011) · doi:10.1016/j.jpdc.2011.04.007
[27] J. M. Moore, An n job, one machine sequencing algorithm for minimizing the number of late jobs, Management Science, 15, 102-109 (1968) · Zbl 0164.20002 · doi:10.1287/mnsc.15.1.102
[28] B. Mor; G. Mosheiov, Scheduling problems with two competing agents to minimize minmax and minsum earliness measures, European Journal of Operational Research, 206, 540-546 (2010) · Zbl 1188.90103 · doi:10.1016/j.ejor.2010.03.003
[29] B. Mor; G. Mosheiov, A two-agent single machine scheduling problem with due-window assignment and a common flow-allowance, Journal of Combinatorial Optimization, 33, 1454-1468 (2017) · Zbl 1377.90033 · doi:10.1007/s10878-016-0049-1
[30] C. Ng; T. C. Cheng; J. Yuan, A note on the complexity of the problem of two-agent scheduling on a single machine, Journal of Combinatorial Optimization, 12, 387-394 (2006) · Zbl 1126.90027 · doi:10.1007/s10878-006-9001-0
[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.
[32] J. M. Peha, Heterogeneous-criteria scheduling: minimizing weighted number of tardy jobs and weighted completion time, Computers & Operations Research, 22, 1089-1100 (1995) · Zbl 0838.90067 · doi:10.1016/0305-0548(94)00090-U
[33] M. Pinedo, Scheduling, Theory, algorithms, and systems. Fourth edition. Springer, New York, 2012. · Zbl 1239.90002
[34] C. N. Potts; L. N. Van Wassenhove, Approximation algorithms for scheduling a single machine to minimize total late work, Operations Research Letters, 11, 261-266 (1992) · Zbl 0767.90039 · doi:10.1016/0167-6377(92)90001-J
[35] C. N. Potts; L. N. Van Wassenhove, Single machine scheduling to minimize total late work, Operations Research, 40, 586-595 (1992) · Zbl 0756.90051 · doi:10.1287/opre.40.3.586
[36] M. Reisi-Nafchi; G. Moslehi, A hybrid genetic and linear programming algorithm for two-agent order acceptance and scheduling problem, Applied Soft Computing, 33, 37-47 (2015) · doi:10.1016/j.asoc.2015.04.027
[37] R. Soltani; F. Jolai; M. Zandieh, Two robust meta-heuristics for scheduling multiple job classes on a single machine with multiple criteria, Expert Systems with Applications, 37, 5951-5959 (2010) · doi:10.1016/j.eswa.2010.02.009
[38] M. Soomer; G. J. Franx, Scheduling aircraft landings using airlines’ preferences, European Journal of Operational Research, 190, 277-291 (2008) · Zbl 1146.90424 · doi:10.1016/j.ejor.2007.06.017
[39] M. Sterna, A survey of scheduling problems with late work criteria, Omega, 39, 120-129 (2011) · doi:10.1016/j.omega.2010.06.006
[40] V. Suresh; D. Chaudhuri, Bicriteria scheduling problem for unrelated parallel machines, Computers & industrial engineering, 30, 77-82 (1996) · doi:10.1016/0360-8352(95)00028-3
[41] L. N. Van Wassenhove; C. N. Potts, Single machine scheduling to minimize total late work, Oper. Res., 40, 586-595 (1992) · Zbl 0756.90051 · doi:10.1287/opre.40.3.586
[42] D.-J. Wang; C.-C. Kang; Y.-R. Shiau; C.-C. Wu; P.-H. Hsu, A two-agent single-machine scheduling problem with late work criteria, Soft Computing, 21, 2015-2033 (2017) · Zbl 1381.90040 · doi:10.1007/s00500-015-1900-5
[43] D.-J. Wang; Y. Yin; S.-R. Cheng; T. Cheng; C.-C. Wu, Due date assignment and scheduling on a single machine with two competing agents, International Journal of Production Research, 54, 1152-1169 (2016)
[44] D.-J. Wang; Y. Yin; J. Xu; W.-H. Wu; S.-R. Cheng; C.-C. Wu, Some due date determination scheduling problems with two agents on a single machine, International Journal of Production Economics, 168, 81-90 (2015) · doi:10.1016/j.ijpe.2015.06.018
[45] W.-H. Wu, An exact and meta-heuristic approach for two-agent single-machine scheduling problem, Journal of Marine Science and Technology, 21, 215-221 (2013)
[46] W.-H. Wu; Y. Yin; W.-H. Wu; C.-C. Wu; 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, 591-611 (2014) · Zbl 1276.90029 · doi:10.3934/jimo.2014.10.591
[47] Z. Xingong; W. Yong, Two-agent scheduling problems on a single-machine to minimize the total weighted late work, Journal of Combinatorial Optimization, 33, 945-955 (2017) · Zbl 1372.90055 · doi:10.1007/s10878-016-0017-9
[48] M. Yazdani; F. Jolai, A Genetic Algorithm with Modified Crossover Operator for a Two-Agent Scheduling Problem, Shiraz Journal of System Management, 1, 1-13 (2013)
[49] Y. Yin; S.-R. Cheng; T. Cheng; D.-J. Wang; C.-C. Wu, Just-in-time scheduling with two competing agents on unrelated parallel machines, Omega, 63, 41-47 (2016) · doi:10.1016/j.omega.2015.09.010
[50] Y. Yin; S.-R. Cheng; T. Cheng; W.-H. Wu; C.-C. Wu, Two-agent single-machine scheduling with release times and deadlines, International Journal of Shipping and Transport Logistics, 5, 75-94 (2013) · doi:10.1504/IJSTL.2013.050590
[51] Y. Yin; T. Cheng; D.-J. Wang; C.-C. Wu, Two-agent flowshop scheduling to maximize the weighted number of just-in-time jobs, Journal of scheduling, 20, 313-335 (2017) · Zbl 1375.90140 · doi:10.1007/s10951-017-0511-7
[52] Y. Yin; W. Wang; D. Wang; T. Cheng, Multi-agent single-machine scheduling and unrestricted due date assignment with a fixed machine unavailability interval, Computers & Industrial Engineering, 111, 202-215 (2017) · doi:10.1016/j.cie.2017.07.013
[53] Y. Yin; C.-C. Wu; W.-H. Wu; C.-J. Hsu; W.-H. Wu, A branch-and-bound procedure for a single-machine earliness scheduling problem with two agents, Applied Soft Computing, 13, 1042-1054 (2013) · doi:10.1016/j.asoc.2012.09.026
[54] Y. Yin; W.-H. Wu; S.-R. Cheng; C.-C. Wu, An investigation on a two-agent single-machine scheduling problem with unequal release dates, Computers & Operations Research, 39, 3062-3073 (2012) · Zbl 1349.90425 · doi:10.1016/j.cor.2012.03.012
[55] Y. Yin; W.-H. Wu; T. Cheng; C.-C. Wu; W.-H. Wu, A honey-bees optimization algorithm for a two-agent single-machine scheduling problem with ready times, Applied Mathematical Modelling, 39, 2587-2601 (2015) · Zbl 1443.90200 · doi:10.1016/j.apm.2014.10.044
[56] J. Yuan; C. Ng; T. E. Cheng, Two-agent single-machine scheduling with release dates and preemption to minimize the maximum lateness, Journal of Scheduling, 18, 147-153 (2015) · Zbl 1311.90057 · doi:10.1007/s10951-013-0360-y
[57] F. Zhang; C. Ng; G. Tang; T. Cheng; Y. Lun, Inverse scheduling: Applications in shipping, International Journal of Shipping and Transport Logistics, 3, 312-322 (2011) · doi:10.1504/IJSTL.2011.040800
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.