Two-agent single-machine scheduling of jobs with time-dependent processing times and ready times. (English) Zbl 1299.90151
Summary: Scheduling involving jobs with time-dependent processing times has recently attracted much research attention. However, multiagent scheduling with simultaneous considerations of jobs with time-dependent processing times and ready times is relatively unexplored. Inspired by this observation, we study a two-agent single-machine scheduling problem in which the jobs have both time-dependent processing times and ready times. We consider the model in which the actual processing time of a job of the first agent is a decreasing function of its scheduled position while the actual processing time of a job of the second agent is an increasing function of its scheduled position. In addition, each job has a different ready time. The objective is to minimize the total completion time of the jobs of the first agent with the restriction that no tardy job is allowed for the second agent. We propose a branch-and-bound and several genetic algorithms to obtain optimal and near-optimal solutions for the problem, respectively. We also conduct extensive computational results to test the proposed algorithms and examine the impacts of different problem parameters on their performance.
MSC:
| 90B35 | Deterministic scheduling theory in operations research |
References:
| [1] | S. Browne and U. Yechiali, “Scheduling deteriorating jobs on a single processor,” Operations Research, vol. 38, no. 3, pp. 495-498, 1990. · Zbl 0703.90051 · doi:10.1287/opre.38.3.495 |
| [2] | D. Biskup, “Single-machine scheduling with learning considerations,” European Journal of Operational Research, vol. 115, no. 1, pp. 173-178, 1999. · Zbl 0946.90025 · doi:10.1016/S0377-2217(98)00246-X |
| [3] | J. N. D. Gupta and S. K. Gupta, “Single facility scheduling with nonlinear processing times,” Computers and Industrial Engineering, vol. 14, no. 4, pp. 387-393, 1988. |
| [4] | B. Alidaee and N. K. Womer, “Scheduling with time dependent processing times: review and extensions,” Journal of the Operational Research Society, vol. 50, no. 7, pp. 711-720, 1999. · Zbl 1054.90542 · doi:10.1057/palgrave.jors.2600740 |
| [5] | T. C. E. Cheng, Q. Ding, and B. M. T. Lin, “A concise survey of scheduling with time-dependent processing times,” European Journal of Operational Research, vol. 152, no. 1, pp. 1-13, 2004. · Zbl 1030.90023 · doi:10.1016/S0377-2217(02)00909-8 |
| [6] | D. Biskup, “A state-of-the-art review on scheduling with learning effects,” European Journal of Operational Research, vol. 188, no. 2, pp. 315-329, 2008. · Zbl 1129.90022 · doi:10.1016/j.ejor.2007.05.040 |
| [7] | J.-B. Wang, “Single-machine scheduling problems with the effects of learning and deterioration,” Omega, vol. 35, no. 4, pp. 397-402, 2007. · doi:10.1016/j.omega.2005.07.008 |
| [8] | J.-B. Wang and T. C. E. Cheng, “Scheduling problems with the effects of deterioration and learning,” Asia-Pacific Journal of Operational Research, vol. 24, no. 2, pp. 245-261, 2007. · Zbl 1121.90066 · doi:10.1142/S021759590700122X |
| [9] | X. Wang and T. C. Edwin Cheng, “Single-machine scheduling with deteriorating jobs and learning effects to minimize the makespan,” European Journal of Operational Research, vol. 178, no. 1, pp. 57-70, 2007. · Zbl 1110.90045 · doi:10.1016/j.ejor.2006.01.017 |
| [10] | J.-B. Wang and L.-L. Liu, “Two-machine flow shop problem with effects of deterioration and learning,” Computers and Industrial Engineering, vol. 57, no. 3, pp. 1114-1121, 2009. · doi:10.1016/j.cie.2009.05.002 |
| [11] | J.-B. Wang and Q. Guo, “A due-date assignment problem with learning effect and deteriorating jobs,” Applied Mathematical Modelling, vol. 34, no. 2, pp. 309-313, 2010. · Zbl 1185.90099 · doi:10.1016/j.apm.2009.04.020 |
| [12] | X. Zhang and G. Yan, “Single-machine group scheduling problems with deteriorated and learning effect,” Applied Mathematics and Computation, vol. 216, no. 4, pp. 1259-1266, 2010. · Zbl 1187.90147 · doi:10.1016/j.amc.2010.02.018 |
| [13] | S.-J. Yang, “Single-machine scheduling problems with both start-time dependent learning and position dependent aging effects under deteriorating maintenance consideration,” Applied Mathematics and Computation, vol. 217, no. 7, pp. 3321-3329, 2010. · Zbl 1202.90149 · doi:10.1016/j.amc.2010.08.064 |
| [14] | Z. Zhu, L. Sun, F. Chu, and M. Liu, “Due-window assignment and scheduling with multiple rate-modifying activities under the effects of deterioration and learning,” Mathematical Problems in Engineering, vol. 2011, Article ID 151563, 19 pages, 2011. · Zbl 1213.90095 · doi:10.1155/2011/151563 |
| [15] | P. Liu and L. Tang, “Two-agent scheduling with linear deteriorating jobs on a single machine,” Lecture Notes in Computer Science, vol. 5092, pp. 642-650, 2008. · Zbl 1148.90324 · doi:10.1007/978-3-540-69733-6_63 |
| [16] | P. Liu, X. Zhou, and L. Tang, “Two-agent single-machine scheduling with position-dependent processing times,” International Journal of Advanced Manufacturing Technology, vol. 48, no. 1-4, pp. 325-331, 2010. · doi:10.1007/s00170-009-2259-5 |
| [17] | T. C. E. Cheng, W.-H. Wu, S.-R. Cheng, and C.-C. Wu, “Two-agent scheduling with position-based deteriorating jobs and learning effects,” Applied Mathematics and Computation, vol. 217, no. 21, pp. 8804-8824, 2011. · Zbl 1231.90182 · doi:10.1016/j.amc.2011.04.005 |
| [18] | W.-H. Wu, S.-R. Cheng, C.-C. Wu, and Y. Yin, “Ant colony algorithms for a two-agent scheduling with sum-of processing times-based learning and deteriorating considerations,” Journal of Intelligent Manufacturing, vol. 23, no. 5, pp. 1985-1993, 2012. · doi:10.1007/s10845-011-0525-5 |
| [19] | C.-C. Wu, P.-H. Hsu, J.-C. Chen, and N.-S. Wang, “Genetic algorithm for minimizing the total weighted completion time scheduling problem with learning and release times,” Computers and Operations Research, vol. 38, no. 7, pp. 1025-1034, 2011. · Zbl 1205.90139 · doi:10.1016/j.cor.2010.11.001 |
| [20] | Y. H. V. Lun, K. H. Lai, C. T. Ng, C. W. Y. Wong, and T. C. E. Cheng, “Research in shipping and transport logistics,” International Journal of Shipping and Transport Logistics, vol. 3, pp. 1-5, 2011. |
| [21] | F. Zhang, C. T. Ng, G. Tang, T. C. E. Cheng, and Y. H. V. Lun, “Inverse scheduling: applications in shipping,” International Journal of Shipping and Transport Logistics, vol. 3, no. 3, pp. 312-322, 2011. · doi:10.1504/IJSTL.2011.040800 |
| [22] | A. Agnetis, P. B. Mirchandani, D. Pacciarelli, and A. Pacifici, “Scheduling problems with two competing agents,” Operations Research, vol. 52, no. 2, pp. 229-242, 2004. · Zbl 1165.90446 · doi:10.1287/opre.1030.0092 |
| [23] | K. R. Baker and J. C. Smith, “A multiple-criterion model for machine scheduling,” Journal of Scheduling, vol. 6, no. 1, pp. 7-16, 2003. · Zbl 1154.90406 · doi:10.1023/A:1022231419049 |
| [24] | J. J. Yuan, W. P. Shang, and Q. Feng, “A note on the scheduling with two families of jobs,” Journal of Scheduling, vol. 8, no. 6, pp. 537-542, 2005. · Zbl 1123.90040 · doi:10.1007/s10951-005-4997-z |
| [25] | T. C. E. Cheng, C. T. Ng, and J. J. Yuan, “Multi-agent scheduling on a single machine to minimize total weighted number of tardy jobs,” Theoretical Computer Science, vol. 362, no. 1-3, pp. 273-281, 2006. · Zbl 1100.68007 · doi:10.1016/j.tcs.2006.07.011 |
| [26] | T. C. E. Cheng, C. T. Ng, and J. J. Yuan, “Multi-agent scheduling on a single machine with max-form criteria,” European Journal of Operational Research, vol. 188, no. 2, pp. 603-609, 2008. · Zbl 1129.90023 · doi:10.1016/j.ejor.2007.04.040 |
| [27] | C. T. Ng, T. C. E. Cheng, and J. J. Yuan, “A note on the complexity of the problem of two-agent scheduling on a single machine,” Journal of Combinatorial Optimization, vol. 12, no. 4, pp. 387-394, 2006. · Zbl 1126.90027 · doi:10.1007/s10878-006-9001-0 |
| [28] | A. Agnetis, D. Pacciarelli, and A. Pacifici, “Multi-agent single machine scheduling,” Annals of Operations Research, vol. 150, no. 1, pp. 3-15, 2007. · Zbl 1144.90375 · doi:10.1007/s10479-006-0164-y |
| [29] | B. Mor and G. Mosheiov, “Scheduling problems with two competing agents to minimize minmax and minsum earliness measures,” European Journal of Operational Research, vol. 206, no. 3, pp. 540-546, 2010. · Zbl 1188.90103 · doi:10.1016/j.ejor.2010.03.003 |
| [30] | B. Mor and G. Mosheiov, “Single machine batch scheduling with two competing agents to minimize total flowtime,” European Journal of Operational Research, vol. 215, no. 3, pp. 524-531, 2011. · Zbl 1238.90069 · doi:10.1016/j.ejor.2011.06.037 |
| [31] | Y. Yin, W.-H. Wu, S.-R. Cheng, and C.-C. Wu, “An investigation on a two-agent single-machine scheduling problem with unequal release dates,” Computers and Operations Research, vol. 39, no. 12, pp. 3062-3073, 2012. · Zbl 1349.90425 · doi:10.1016/j.cor.2012.03.012 |
| [32] | Y. Yin, S. R. Cheng, T. C. E. Cheng, W. H. Wu, and C. C. Wu, “Two-agent single-machine scheduling with release times and deadlines,” International Journal of Shipping and Transport Logistics, vol. 5, pp. 76-94, 2013. |
| [33] | J. K. Lenstra, A. H. G. Rinnooy Kan, and P. Brucker, “Complexity of machine scheduling problems,” Annals of Discrete Mathematics, vol. 1, pp. 343-362, 1977. · Zbl 0353.68067 · doi:10.1016/S0167-5060(08)70743-X |
| [34] | S. K. Iyer and B. Saxena, “Improved genetic algorithm for the permutation flowshop scheduling problem,” Computers and Operations Research, vol. 31, no. 4, pp. 593-606, 2004. · Zbl 1046.90028 · doi:10.1016/S0305-0548(03)00016-9 |
| [35] | I. Essafi, Y. Mati, and S. Dauzère-Pérès, “A genetic local search algorithm for minimizing total weighted tardiness in the job-shop scheduling problem,” Computers and Operations Research, vol. 35, no. 8, pp. 2599-2616, 2008. · Zbl 1177.90155 · doi:10.1016/j.cor.2006.12.019 |
| [36] | O. Etiler, B. Toklu, M. Atak, and J. Wilson, “A genetic algorithm for flow shop scheduling problems,” Journal of the Operational Research Society, vol. 55, no. 8, pp. 830-835, 2004. · Zbl 1060.90035 · doi:10.1057/palgrave.jors.2601766 |
| [37] | C. Reeves, “Heuristics for scheduling a single machine subject to unequal job release times,” European Journal of Operational Research, vol. 80, no. 2, pp. 397-403, 1995. |
| [38] | C.-L. Chen, V. S. Vempati, and N. Aljaber, “An application of genetic algorithms for flow shop problems,” European Journal of Operational Research, vol. 80, no. 2, pp. 389-396, 1995. |
| [39] | M. L. Fisher, “A dual algorithm for the one-machine scheduling problem,” Mathematical Programming, vol. 11, no. 1, pp. 229-251, 1976. · Zbl 0359.90039 · doi:10.1007/BF01580393 |
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.
