##
**Scheduling problems with two agents and a linear non-increasing deterioration to minimize earliness penalties.**
*(English)*
Zbl 1247.90165

Summary: We consider a scheduling environment with two agents and a linear non-increasing deterioration. By the linear non-increasing deterioration we mean that the actual processing time of a job belonging to the two agents is defined as a non-increasing linear function of its starting time. Two agents compete to perform their respective jobs on a common single machine and each agent has his own criterion to be optimized. The goal is to schedule the jobs such that the combined schedule performs well with respect to the measures of both agents. Three different objective functions are considered for one agent, including the maximum earliness cost, total earliness cost and total weighted earliness cost, while keeping the maximum earliness cost of the other agent below or at a fixed level \(U\). We propose the optimal (nondominated) properties and present the complexity results for the problems addressed here.

### MSC:

90B35 | Deterministic scheduling theory in operations research |

Full Text:
DOI

### References:

[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] | Alidaee, B.; Womer, N. K., Scheduling with time dependent processing times: review and extensions, Journal of the Operational Research Society, 50, 711-729 (1999) · Zbl 1054.90542 |

[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] | Balin, S., Parallel machine scheduling with fuzzy processing times using a robust genetic algorithm and simulation, Information Sciences, 181, 17, 3551-3569 (2011) |

[6] | Cheng, T. C.E.; Ding, Q.; Lin, B. M.T., A concise survey of scheduling with time-dependent processing times, European Journal of Operational Research, 152, 1-13 (2004) · Zbl 1030.90023 |

[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.; Yang, S. J.; Yang, D. L., Common due-window assignment and scheduling of linear time-dependent deteriorating jobs and a deteriorating maintenance activity, International Journal of Production Economics, 135, 1, 154-161 (2012) |

[10] | Graham, R. L.; Lawler, E. L.; Lenstra, J. K.; Rinnooy Kan, A. H.G., Optimization and heuristic in deterministic sequencing and scheduling: a survey, Annals of Discrete Mathematics, 5, 287-326 (1979) · Zbl 0411.90044 |

[11] | Ho, K. I.J.; Leung, J. Y.T.; Wei, W.-D., Complexity of scheduling tasks with time-dependent execution times, Information Processing Letter, 48, 315-320 (1993) · Zbl 0942.68508 |

[12] | Hsu, C. J.; Cheng, T. C.E.; Yang, D. L., Unrelated parallel-machine scheduling with rate-modifying activities to minimize the total completion time, Information Sciences, 181, 20, 4799-4803 (2011) · Zbl 1252.90024 |

[13] | Inderfurth, K.; Janiak, A.; Kovalyov, M. Y.; Werner, F., Batching work and rework processes with limited deterioration of reworkables, Computers and Operations Research, 33, 1595-1605 (2006) · Zbl 1087.90008 |

[14] | A. Janiak, M.Y. Kovalyov, Scheduling deteriorating jobs, in: A. Janiak (Ed.), Scheduling in Computer and Manufacturing Systems, Warszawa, WKL, 2006, pp. 12-25.; A. Janiak, M.Y. Kovalyov, Scheduling deteriorating jobs, in: A. Janiak (Ed.), Scheduling in Computer and Manufacturing Systems, Warszawa, WKL, 2006, pp. 12-25. |

[15] | Kuo, W. H.; Yang, D. L., Note on “Single-machine and flowshop scheduling with a general learning effect model” and “Some single-machine and m-machine flowshop scheduling problems with learning considerations, Information Sciences, 180, 19, 3814-3816 (2010) · Zbl 1194.90041 |

[16] | 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 |

[17] | Lee, W. C.; Chen, S. K.; Chen, W. C.; Wu, C. C., A two-machine flowshop problem with two agents, Computers and Operations Research, 38, 98-104 (2011) · Zbl 1231.90204 |

[18] | Lee, W. C.; Chen, S. K.; Wu, C. C., Branch-and-bound and simulated annealing algorithms for a two-agent scheduling problem, Expert Systems with Applications, 37, 6594-6601 (2010) |

[19] | Lee, W. C.; Lai, P. J., Scheduling problems with general effects of deterioration and learning, Information Sciences, 181, 6, 1164-1170 (2011) · Zbl 1208.90072 |

[20] | Li, Y.; Li, G.; Sun, L.; Xu, Z., Single machine scheduling of deteriorating jobs to minimize total absolute differences in completion Times, International Journal of Production Economics, 118, 424-429 (2009) |

[21] | Liu, P.; Tang, L. X.; Zhou, X. Y., Two-agent group scheduling with deteriorating jobs on a single machine, The International Journal of Advanced Manufacturing Technology, 47, 657-664 (2010) |

[22] | 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 |

[23] | Mazdeh, M. M.; Zaerpour, F.; Zareei, A.; Hajinezhad, A., Parallel machines scheduling to minimize job tardiness and machine deteriorating cost with deteriorating jobs, Applied Mathematical Modelling, 34, 1498-1510 (2010) · Zbl 1193.90105 |

[24] | 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 |

[25] | Ng, C. T.; Cheng, T. C.E.; Bachman, A.; Janiak, A., Three scheduling problems with deteriorating jobs to minimize the total completion time, Information Processing Letters, 81, 327-333 (2002) · Zbl 1059.90063 |

[26] | Ng, C. T.; Cheng, C. T.E.; 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 |

[27] | Pan, Q. K.; Fatih Tasgetiren, M.; Suganthan, P. N.; Chua, T. J., A discrete artificial bee colony algorithm for the lot-streaming flow shop scheduling problem, Information Sciences, 181, 12, 2455-2468 (2011) |

[28] | Qi, X.; Tu, F. S., Scheduling a single-machine to minimize earliness penalties subject to the SLK due-date determination method, European Journal of Operational Research, 105, 502-508 (1998) · Zbl 0955.90031 |

[29] | 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) |

[30] | Valente, J. M.S., Local and global dominance conditions for the weighted earliness scheduling problem with no idle time, Computers & Industrial Engineering, 51, 765-780 (2006) |

[31] | Wan, G.; Vakati, R. S.; Leung, J. Y.T.; Pinedo, M., Scheduling two agents with controllable processing times, European Journal of Operational Research, 205, 528-539 (2010) · Zbl 1188.90114 |

[32] | Wang, J. B., A note on single-machine scheduling with decreasing time-dependent job processing times, Applied Mathematical Modelling, 34, 294-300 (2010) · Zbl 1185.90098 |

[33] | Wang, J. B.; Cheng, T. C.E., Scheduling problems with the effects of deterioration and learning, Asia Pacific Journal of Operational Research, 24, 245-261 (2007) · Zbl 1121.90066 |

[34] | Wang, J. B.; Jiang, Y.; Wang, G., Single-machine scheduling with past-sequence-dependent setup times and effects of deterioration and learning, The International Journal of Advanced Manufacturing Technology, 41, 1221-1226 (2009) |

[35] | Wang, X. R.; Huang, X.; Wang, J. B., Single-machine scheduling with linear decreasing deterioration to minimize earliness penalties, Applied Mathematical Modelling, 35, 3509-3515 (2011) · Zbl 1221.90051 |

[36] | Wang, L. Y.; Wang, J. B.; Gao, W. J.; Huang, X.; Feng, E. M., Two single-machine scheduling problems with the effects of deterioration and learning, The International Journal of Advanced Manufacturing Technology, 46, 715-720 (2010) |

[37] | Wang, X. Y.; Wang, M. Z.; Wang, J. B., Flow shop scheduling to minimize makespan with decreasing linear deterioration, Computers & Industrial Engineering, 60, 840-844 (2011) |

[38] | Wang, J. B.; Wei, C. M., Parallel machines scheduling with a deteriorating maintenance activity and total absolute differences penalties, Applied Mathematics and Computation, 217, 8093-8099 (2011) · Zbl 1230.90103 |

[39] | Wang, J. B.; Xia, Z. Q., Scheduling jobs under decreasing linear deterioration, Information Processing Letter, 94, 63-69 (2005) · Zbl 1182.68359 |

[40] | Wu, C. C.; Lee, W. C.; Shiau, Y. R., Minimizing the total weighted completion time on a single machine under linear deterioration, International Journal of Advanced Manufacturing Technology, 33, 1237-1243 (2007) |

[41] | Yin, Y.; Xu, D.; Huang, X., Notes on “some single-machine scheduling problems with general position-dependent and time-dependent learning effect, Information Sciences, 181, 11, 2209-2217 (2011) · Zbl 1231.90223 |

[42] | Yang, S. J.; Yang, D. L., Minimizing the makespan on single-machine scheduling with aging effect and variable maintenance activities, Omega, 38, 528-533 (2010) |

[43] | Zhao, C.; Tang, H., A note to due-window assignment and single machine scheduling with deteriorating jobs and a rate-modifying activity, Computers and Operations Research, 39, 6, 1300-1303 (2012) · Zbl 1251.90209 |

[44] | Zhao, C.; Tang, H., Rescheduling problems with deteriorating jobs under disruptions, Applied Mathematical Modelling, 34, 238-243 (2010) · Zbl 1185.90114 |

[45] | Zhao, C. L.; Zhang, Q. L.; Tang, H. Y., Scheduling problems under linear deterioration, Acta Automatica Sinica, 29, 531-535 (2003) · 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.