A note on a two-agent scheduling problem related to the total weighted late work. (English) Zbl 1423.90104
Summary: We revisit a two-agent scheduling problem in which a set of jobs belonging to two agents \(A\) and \(B\) (without common jobs) will be processed on a single machine for minimizing the total weighted late work of agent \(A\) subject to the maximum cost of agent \(B\) being bounded. Z. Xingong and W. Yong [J. Comb. Optim. 33, No. 3, 945–955 (2017; Zbl 1372.90055)] studied three versions of the problem: (i) the \(A\)-jobs having a common due date, (ii) the \(A\)-jobs having a common processing time, (iii) the general version. The authors presented polynomial-time algorithms for the first two versions and a pseudo-polynomial-time algorithm for the last one. However, their algorithm for the first version is invalid. Then we show the NP-hardness and provide a pseudo-polynomial-time algorithm for the first version with the cost of agent \(B\) being makespan, present a polynomial-time algorithm for an extension of the second version, and show that the third version is solvable in pseudo-polynomial-time by a new technique.
MSC:
| 90B35 | Deterministic scheduling theory in operations research |
Citations:
Zbl 1372.90055References:
| [1] | Agnetis A, Mirchandani 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] | 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 |
| [5] | Blazewicz J (1984) Scheduling preemptible tasks on parallel processors with information loss. Tech Sci Inf 3(6):415-420 · Zbl 0565.68037 |
| [6] | Chen, B.; Potts, CN; Woeginger, GJ; Du, D-Z (ed.); Pardalos, PM (ed.), A review of machine scheduling, 21-169 (1998), Boston · Zbl 0944.90022 |
| [7] | 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 |
| [8] | 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 |
| [9] | Garey MR, Johnson DS (1979) Computers and intractability: a guide to the theory of NP-completeness. Freeman, San Francisco · Zbl 0411.68039 |
| [10] | Hariri AMA, Potts CN, Van Wassenhove LN (1995) Single machine scheduling to minimize total weighted late work. ORSA J Comput 7:232-242 · Zbl 0859.90084 · doi:10.1287/ijoc.7.2.232 |
| [11] | Lawler EL (1976) Combinatorial optimization: networks and matroids. Holt, Rinehart and Winston, New York · Zbl 0413.90040 |
| [12] | Leung, JYT; Leung, JYT (ed.), Minimizing total weighted error for imprecise computation tasks and related problems, 34.1-34.16 (2004), Boca Raton |
| [13] | Ng CT, Cheng TE, Yuan JJ (2006) A note on the complexity of the problem of two-agent scheduling on a single machine. J Comb Optim 12:87-394 · Zbl 1126.90027 · doi:10.1007/s10878-006-9001-0 |
| [14] | Potts CN, Van Wassenhove LN (1992) Single machine scheduling to minimize total late work. Oper Res 40:586-595 · Zbl 0756.90051 · doi:10.1287/opre.40.3.586 |
| [15] | Sterna M (2011) A survey of scheduling problems with late work criteria. Omega 39:120-129 · doi:10.1016/j.omega.2010.06.006 |
| [16] | Wang DJ, Yin YQ, Cheng SR, Cheng TCE, Wu CC (2016) Due date assignment and scheduling on a single machine with two competing agents. Int J Prod Res 54:1152-1169 · doi:10.1080/00207543.2015.1056317 |
| [17] | Wang DJ, Kang CC, Shiau YR, Wu CC, Hsu PH (2017) A two-agent single-machine scheduling problem with late work criteria. Soft Comput 21:2015-2033 · Zbl 1381.90040 · doi:10.1007/s00500-015-1900-5 |
| [18] | Yin YQ, Wang DJ, Wu CC, Cheng TCE (2016) CON/SLK due date assignment and scheduling on a single machine with two agents. Nav Res Logist 63:416-429 · Zbl 1411.90166 · doi:10.1002/nav.21700 |
| [19] | Yuan JJ (2016) Complexities of some problems on multi-agent scheduling on a single machine. J Oper Res Soc China 4:379-384 · Zbl 1368.90080 · doi:10.1007/s40305-016-0124-4 |
| [20] | 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 |
| [21] | Zhang XG, Wang Y (2017) Two-agent scheduling problems on a single-machine to minimize the total weighted late work. J Comb Optim 33:945-955 · Zbl 1372.90055 · doi:10.1007/s10878-016-0017-9 |
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.
