Two-agent scheduling of time-dependent jobs. (English) Zbl 1382.90035
Summary: We consider the problem of scheduling deteriorating jobs or shortening jobs with two agents \(A\) and \(B\). We are interested in generating all Pareto-optimal schedules for the two criteria: (1) the total completion time of the jobs in \(A\) and the maximum cost of the jobs in \(B\), and (2) the maximum cost of the jobs in \(A\) and the maximum cost of the jobs in \(B\). We show that all Pareto-optimal schedules for both problems can be generated in polynomial time, whether the jobs are deteriorating or shortening.
MSC:
| 90B35 | Deterministic scheduling theory in operations research |
Keywords:
scheduling; two agents; deteriorating jobs; shortening jobs; total completion time; maximum costReferences:
| [1] | Agnetis A, Mirchani PB, Pacciarelli D, Pacifici A (2004) Scheduling problems with two competing agents. Oper Res 52:229-242 · Zbl 1165.90446 · doi:10.1287/opre.1030.0092 |
| [2] | Agnetis A, Pacciarelli D, Pacifici A (2007) Multi-agent single machine scheduling. Ann Oper Res 150:3-15 · Zbl 1144.90375 · doi:10.1007/s10479-006-0164-y |
| [3] | Agnetis A, Billaut JC, Gawiejnowicz S, Pacciarelli D, Soukhal A (2014) Multiagent scheduling: models and algorithms. Springer, Berlin · Zbl 1286.90002 · doi:10.1007/978-3-642-41880-8 |
| [4] | Alidaee B, Womer NK (1999) Scheduling with time dependent processing times: review and extensions. J Oper Res Soc 50:711-720 · Zbl 1054.90542 · doi:10.1057/palgrave.jors.2600740 |
| [5] | Baker KR, Smith JC (2003) A multiple criterion model for machine scheduling. J Sched 6:7-16 · Zbl 1154.90406 · doi:10.1023/A:1022231419049 |
| [6] | Browne S, Yechiali U (1990) Scheduling deteriorating jobs on a single processor. Oper Res 38:495-498 · Zbl 0703.90051 · doi:10.1287/opre.38.3.495 |
| [7] | Brucker P (2001) Scheduling algorithms, 3rd edn. Springer, Berlin · Zbl 1051.90011 · doi:10.1007/978-3-662-04550-3 |
| [8] | Cheng TCE, Ding Q, Lin BMT (2004) A concise survey of scheduling with time-dependent processing times. Eur J Oper Res 152:1-13 · Zbl 1030.90023 · doi:10.1016/S0377-2217(02)00909-8 |
| [9] | Cheng TCE, Ng CT, Yuan JJ (2006) Multi-agent scheduling on a single machine to minimize total weighted number of tardy jobs. Theor Comput Sci 362:273-281 · Zbl 1100.68007 · doi:10.1016/j.tcs.2006.07.011 |
| [10] | Cheng TCE, Ng CT, Yuan JJ (2008) Multi-agent scheduling on a single machine with max-form criteria. Eur J Oper Res 188:603-609 · Zbl 1129.90023 · doi:10.1016/j.ejor.2007.04.040 |
| [11] | Graham RL, Lawler EL, Lenstra JK, Rinnooy Kan AHG (1979) Optimization and approximation in deterministic sequencing and scheduling: a survey. Ann Discrete Math 5:287-326 · Zbl 0411.90044 · doi:10.1016/S0167-5060(08)70356-X |
| [12] | Gupta JND, Gupta SK (1988) Single facility scheduling with nonlinear processing times. Comput Ind Eng 14:387-393 · doi:10.1016/0360-8352(88)90041-1 |
| [13] | Ho KIJ, Leung JY-T, Wei W-D (1993) Complexity of scheduling tasks with time-dependent execution times. Inf Process Lett 48:315-320 · Zbl 0942.68508 · doi:10.1016/0020-0190(93)90175-9 |
| [14] | Hoogeveen H (2005) Multicriteria scheduling. Eur J Oper Res 167:592-623 · Zbl 1154.90458 · doi:10.1016/j.ejor.2004.07.011 |
| [15] | Leung JY-T, Pinedo M, Wan G (2010) Competitive two-agent scheduling and its applications. Oper Res 58:458-469 · Zbl 1233.90163 · doi:10.1287/opre.1090.0744 |
| [16] | Liu P, Tang L (2008) Two-agent scheduling with linear deteriorating jobs on single-machine. Lect Notes Comput Sci 5029:642-650 · Zbl 1148.90324 · doi:10.1007/978-3-540-69733-6_63 |
| [17] | Liu P, Yi N, Zhou XY (2011) Two-agent single-machine scheduling problems under increasing linear deterioration. Appl Math Model 35:2290-2296 · Zbl 1217.90108 · doi:10.1016/j.apm.2010.11.026 |
| [18] | Ng CT, Cheng TCE, Bachman A, Janiak A (2002) Three scheduling problems with deteriorating jobs to minimize the total completion time. Inf Process Lett 81:327-333 · Zbl 1059.90063 · doi:10.1016/S0020-0190(01)00244-7 |
| [19] | Ng CT, Cheng TCE, Yuan JJ (2006) A note on the complexity of the problem of two-agent scheduling on a single machine. J Comb Optim 12:387-394 · Zbl 1126.90027 · doi:10.1007/s10878-006-9001-0 |
| [20] | Wan G, Vakati SR, Leung JY-T, Pinedo M (2010) Scheduling two agents with controllable processing times. Eur J Oper Res 205:528-539 · Zbl 1188.90114 · doi:10.1016/j.ejor.2010.01.005 |
| [21] | Wang JB (2010) A note on single-machine scheduling with decreasing time-dependent job processing times. Appl Math Model 34:294-300 · Zbl 1185.90098 · doi:10.1016/j.apm.2009.04.018 |
| [22] | Yin YQ, Cheng SR, Wu CC (2012) Scheduling problems with two agents and a linear non-increasing deterioration to minimize earliness penalties. Inf Sci 189:282-292 · Zbl 1247.90165 · doi:10.1016/j.ins.2011.11.035 |
| [23] | Yuan JJ, Shang WP, Feng Q (2005) A note on the scheduling with two families of jobs. J Sched 8:537-542 · Zbl 1123.90040 · doi:10.1007/s10951-005-4997-z |
| [24] | Zhao CL, Zhang QL, Tang HY (2003) Scheduling problems under linear deterioration. Acta Autom Sin 29:531-535 · Zbl 1498.90109 |
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.
