Two-agent single-machine scheduling with assignable due dates. (English) Zbl 1291.90102

Summary: We consider several two-agent scheduling problems with assignable due dates on a single machine, where each of the agents wants to minimize a measure depending on the completion times of its own jobs and the due dates are treated as given variables and must be assigned to individual jobs. The goal is to assign a due date from a given set of due dates and a position in the sequence to each job so that the weighted sum of the objectives of both agents is minimized. For different combinations of the objectives, which include the maximum lateness, total (weighted) tardiness, and total (weighted) number of tardy jobs, we provide the complexity results and solve the corresponding problems, if possible.


90B35 Deterministic scheduling theory in operations research
Full Text: DOI


[1] Agnetis, A.; Mirchandani, P.B.; Pacciarelli, D.; Pacifici, A., Scheduling problems with two competing agents, Operations research, 52, 229-242, (2004) · Zbl 1165.90446
[2] Agnetis, A.; Pacciarelli, D.; Pacifici, A., Multi-agent single machine scheduling, Annals of operations research, 150, 3-15, (2007) · Zbl 1144.90375
[3] Agnetis, A.; Pascale, G.; Pacciarelli, D., A Lagrangian approach to single-machine scheduling problems with two competing agents, Journal of scheduling, 12, 401-415, (2009) · Zbl 1185.90063
[4] Baker, K.R.; Smith, J.C., A multiple criterion model for machine scheduling, Journal of scheduling, 6, 7-16, (2003) · Zbl 1154.90406
[5] Cheng, T.C.E.; Cheng, S.-R.; Wu, W.-H.; Hsu, P.-H.; Wu, C.-C., A two-agent single- machine scheduling problem with truncated sum-of-processing-times-based learning considerations, Computers & industrial engineering, 60, 534-541, (2011)
[6] Cheng, T.C.E.; Gupta, M.C., Survey of scheduling research involving due-date determination decisions, European journal of operational research, 38, 156-166, (1989) · Zbl 0658.90049
[7] Cheng, T.C.E.; Ng, C.T.; Yuan, J.J., Multi-agent scheduling on a single machine to minimize total weighted number of tardy jobs, Theoretical computer science, 362, 273-281, (2006) · Zbl 1100.68007
[8] Cheng, T.C.E.; Ng, C.T.; Yuan, J.J., Multi-agent scheduling on a single machine with MAX-form criteria, European journal of operational research, 188, 603-609, (2008) · Zbl 1129.90023
[9] Cheng, T.C.E.; Wu, W.-H.; Cheng, S.-R.; Wu, C.-C., Two-agent scheduling with position-based deteriorating jobs and learning effects, Applied mathematics and computation, 217, 8804-8824, (2011) · Zbl 1231.90182
[10] Gordon, V.S.; Proth, J.M.; Chu, C., Due date assignment and scheduling: SLK, TWK and other due date assignment models, Production planning and control, 13, 117-132, (2002)
[11] Gordon, V.S.; Proth, J.M.; Chu, C., A survey of the state-of-the-art of common due date assignment and scheduling research, European journal of operational research, 139, 1-25, (2002) · Zbl 1009.90054
[12] Gordon, V.; Strusevich, V.; Dolgui, A., Scheduling with due date assignment under special conditions on job processing, Journal of scheduling, (2010)
[13] Hall, N.G., Scheduling problems with generalized due dates, IIE transactions, 18, 220-222, (1986)
[14] Hsu, C.J.; Yang, S.J.; Yang, D.L., Two due date assignment problems with position-dependent processing time on a single-machine, Computers & industrial engineering, 60, 796-800, (2011)
[15] Lauff, V.; Werner, F., Scheduling with common due date, earliness and tardiness penalties for multimachine problems: a survey, Mathematical and computer modelling, 40, 637-655, (2004) · Zbl 1098.90031
[16] Lee, H.-T.; Yang, D.L.; Yang, S.-J., Multi-machine scheduling with deterioration effects and maintenance activities for minimizing the total earliness and tardiness costs, International journal of advanced manufacturing technology, (2012)
[17] Lee, K.; Choi, B.C.; Leung, J.Y.T.; Pinedo, M.L., Approximation algorithms for multi-agent scheduling to minimize total weighted completion time, Information processing letters, 109, 913-917, (2009) · Zbl 1205.68516
[18] Leung, J.Y.T.; Pinedo, M.L.; Wan, G., Competitive two-agent scheduling and its applications, Operations research, 58, 2, 458-469, (2010) · Zbl 1233.90163
[19] Liu, P.; Tang, L.X.; Zhou, X.Y., Two-agent group scheduling with deteriorating jobs on a single machine, International journal of advanced manufacturing technology, 47, 657-664, (2010)
[20] Liu, P.; Yi, N.; Zhou, X.Y., Two-agent single-machine scheduling problems under increasing linear deterioration, Applied mathematical modelling, 35, 2290-2296, (2011) · Zbl 1217.90108
[21] Lu, Y.-Y.; Li, G.; Wu, Y.-B.; Ping, J., Optimal due-date assignment problem with learning effect and resource-dependent processing times, Optimization letters, (2012)
[22] Mor, B.; Mosheiov, G., 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
[23] Mor, B.; Mosheiov, G., Single machine batch scheduling with two competing agents to minimize total flowtime, European journal of operational research, 215, 524-531, (2011) · Zbl 1238.90069
[24] Mosheiov, G.; Oron, D., Due-date assignment and maintenance activity scheduling problem, Mathematical and computer modelling, 44, 1053-1057, (2006) · Zbl 1161.90397
[25] Ng, C.T.; E Cheng, T.C.; Yuan, J.J., A note on the complexity of the two-agent scheduling on a single machine, Journal of combinatorial optimization, 12, 387-394, (2006) · Zbl 1126.90027
[26] Qi, X.T.; Yu, G.; Bard, J.F., Single machine scheduling with assignable due dates, Discrete applied mathematics, 122, 211-233, (2002) · Zbl 1019.90024
[27] Rudek, R., The strong NP-hardness of the maximum lateness minimization scheduling problem with the processing-time based aging effect, Applied mathematics and computation, 218, 6498-6510, (2012) · Zbl 1237.90096
[28] Shabtay, D., Scheduling and due date assignment to minimize earliness, tardiness, holding, due date assignment and batch delivery costs, International journal of production economics, 123, 235-242, (2010)
[29] Sriskandarajah, C., A note on the generalized due dates scheduling problems, Naval research logistics, 37, 587-597, (1990) · Zbl 0712.90032
[30] Tanaka, K.; Vlach, M., Single machine scheduling to minimize the maximum lateness with both specific and generalized due dates, IEICE transactions on fundamentals of electronics, communications and computer sciences, 80, 557-563, (1997)
[31] Tanaka, K.; Vlach, M., Minimizing maximum absolute lateness and range of lateness under generalized due dates on a single machine, Annals of operations research, 86, 507-526, (1999) · Zbl 0922.90092
[32] Wan, G.; Vakati, R.S.; Leung, J.Y.T.; Pinedo, M.L., Scheduling two agents with controllable processing times, European journal of operational research, 205, 528-539, (2010) · Zbl 1188.90114
[33] Wang, J.-B.; Wang, M.Z., Single machine multiple common due dates scheduling with learning effects, Computers and mathematics with applications, 60, 2998-3002, (2010) · Zbl 1207.90059
[34] Wang, J.B.; Guo, Q., A due-date assignment problem with learning effect and deteriorating jobs, Applied mathematical modelling, 34, 309-313, (2010) · Zbl 1185.90099
[35] Wang, X.-Y.; Wang, M.-Z., Single machine common flow allowance scheduling with a rate-modifying activity, Computers and industrial engineering, 59, 898-902, (2010)
[36] Wang, J.-B.; Wei, C.-M., Parallel machine scheduling with a deteriorating maintenance activity and total absolute differences penalties, Applied mathematics and computation, 217, 8093-8099, (2011) · Zbl 1230.90103
[37] Yang, S.-J., Single-machine scheduling problems with both start-time dependent learning and position dependent aging effects under deteriorating maintenance consideration, Applied mathematics and computation, 217, 3321-3329, (2010) · Zbl 1202.90149
[38] Yang, S.-J.; Hsu, C.J.; Yang, D.-L., Single-machine scheduling and slack due-date assignment with aging effect and deteriorating maintenance, Optimization letters, (2011)
[39] Yin, Y.; Cheng, S.-R.; Wu, C.-C., Scheduling problems with two agents and a linear non-increasing deterioration to minimize earliness penalties, Information sciences, 189, 282-292, (2012) · Zbl 1247.90165
[40] Y. Yin, S.-R. Cheng, T.C.E. Cheng, W.-H. Wu, C.-C. Wu, Two-agent single-machine scheduling with release times and deadlines, International Journal of Shipping and Transport Logistics, forthcoming.
[41] Yuan, J.J.; Shang, W.P.; Feng, Q., A note on the scheduling with two families of jobs, Journal of scheduling, 8, 537-542, (2005) · Zbl 1123.90040
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.