Two-agent scheduling to minimize the maximum cost with position-dependent jobs. (English) Zbl 1418.90122
Summary: This paper investigates a single-machine two-agent scheduling problem to minimize the maximum costs with position-dependent jobs. There are two agents, each with a set of independent jobs, competing to perform their jobs on a common machine. In our scheduling setting, the actual position-dependent processing time of one job is characterized by variable function dependent on the position of the job in the sequence. Each agent wants to fulfil the objective of minimizing the maximum cost of its own jobs. We develop a feasible method to achieve all the Pareto optimal points in polynomial time.
MSC:
| 90B35 | Deterministic scheduling theory in operations research |
References:
| [1] | Agnetis, A.; Mirchandani, P. B.; Pacciarelli, D.; Pacifici, A., Scheduling problems with two competing agents, Operations Research, 52, 2, 229-242 (2004) · Zbl 1165.90446 · doi:10.1287/opre.1030.0092 |
| [2] | Baker, K. R.; Smith, J. C., A multiple-criterion model for machine scheduling, Journal of Scheduling, 6, 1, 7-16 (2003) · Zbl 1154.90406 · doi:10.1023/A:1022231419049 |
| [3] | Yuan, J. J.; Shang, W. P.; Feng, Q., A note on the scheduling with two families of jobs, Journal of Scheduling, 8, 6, 537-542 (2005) · Zbl 1123.90040 · doi:10.1007/s10951-005-4997-z |
| [4] | Biskup, D., Single-machine scheduling with learning considerations, European Journal of Operational Research, 115, 1, 173-178 (1999) · Zbl 0946.90025 · doi:10.1016/S0377-2217(98)00246-X |
| [5] | Mosheiov, G., Scheduling problems with a learning effect, European Journal of Operational Research, 132, 3, 687-693 (2001) · Zbl 1017.90051 · doi:10.1016/S0377-2217(00)00175-2 |
| [6] | Janiak, A.; Kovalyov, M. Y., Scheduling jobs with position-dependent processing times, Journal of the Operational Research Society, 63, 7, 1018-1020 (2012) · doi:10.1057/jors.2012.18 |
| [7] | Wang, J.-B.; Xia, Z.-Q., Flow-shop scheduling with a learning effect, Journal of the Operational Research Society, 56, 11, 1325-1330 (2005) · Zbl 1082.90041 · doi:10.1057/palgrave.jors.2601856 |
| [8] | Wang, J.-B., Flow shop scheduling jobs with position-dependent processing times, Journal of Applied Mathematics & Computing, 18, 1-2, 383-391 (2005) · Zbl 1077.90032 · doi:10.1007/BF02936581 |
| [9] | Yin, Y.; Xu, D.; Sun, K.; Li, H., Some scheduling problems with general position-dependent and time-dependent learning effects, Information Sciences, 179, 14, 2416-2425 (2009) · Zbl 1166.90342 · doi:10.1016/j.ins.2009.02.015 |
| [10] | 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, 7, 3321-3329 (2010) · Zbl 1202.90149 · doi:10.1016/j.amc.2010.08.064 |
| [11] | Biskup, D., A state-of-the-art review on scheduling with learning effects, European Journal of Operational Research, 188, 2, 315-329 (2008) · Zbl 1129.90022 · doi:10.1016/j.ejor.2007.05.040 |
| [12] | Liu, P.; Zhou, X.; Tang, L., Two-agent single-machine scheduling with position-dependent processing times, The International Journal of Advanced Manufacturing Technology, 48, 1-4, 325-331 (2010) · doi:10.1007/s00170-009-2259-5 |
| [13] | Wan, L., Two-agent pareto optimization problems with position-dependent jobs |
| [14] | 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 · doi:10.1016/j.ins.2011.11.035 |
| [15] | Yin, Y. Q.; Wu, W.-H.; Cheng, T. C. E.; Wu, C.-C., Single-machine scheduling with time-dependent and position-dependent deteriorating jobs, International Journal of Computer Integrated Manufacturing (2014) · doi:10.1080/0951192X.2014.900872 |
| [16] | Yin, Y.; Cheng, T. C. E.; Wu, C.-C., Scheduling with time-dependent processing times, Mathematical Problems in Engineering, 2014 (2014) · doi:10.1155/2014/201421 |
| [17] | Smith, W. E., Various optimizers for single-stage production, Naval Research Logistics Quarterly, 3, 59-66 (1956) · doi:10.1002/nav.3800030106 |
| [18] | Hoogeveen, J. A., Single-machine scheduling to minimize a function of two or three maximum cost criteria, Journal of Algorithms, 21, 2, 415-433 (1996) · Zbl 0857.68012 · doi:10.1006/jagm.1996.0051 |
| [19] | Sourd, F., Preemptive scheduling with two minimax criteria, Annals of Operations Research, 107, 303-319 (2001) · Zbl 1015.90044 · doi:10.1023/A:1014971620268 |
| [20] | Wan, L.; Wei, L. J.; Sheng, J. L.; Yuan, J. J., Pareto optimization scheduling with two competing agents and linear non-increasing deterioration to minimize earliness penalties |
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.
