A single-machine two-agent scheduling problem by a branch-and-bound and three simulated annealing algorithms. (English) Zbl 1418.90117
Summary: In the field of distributed decision making, different agents share a common processing resource, and each agent wants to minimize a cost function depending on its jobs only. These issues arise in different application contexts, including real-time systems, integrated service networks, industrial districts, and telecommunication systems. Motivated by its importance on practical applications, we consider two-agent scheduling on a single machine where the objective is to minimize the total completion time of the jobs of the first agent with the restriction that an upper bound is allowed the total completion time of the jobs for the second agent. For solving the proposed problem, a branch-and-bound and three simulated annealing algorithms are developed for the optimal solution, respectively. In addition, the extensive computational experiments are also conducted to test the performance of the algorithms.
MSC:
| 90B35 | Deterministic scheduling theory in operations research |
References:
| [1] | Purnomo, H.; Guizol, P., Simulating forest plantation co-management with a multi-agent system, Mathematical and Computer Modelling, 44, 5-6, 535-552 (2006) · Zbl 1132.91587 · doi:10.1016/j.mcm.2006.01.009 |
| [2] | Bessonov, N.; Demin, I.; Pujo-Menjouet, L.; Volpert, V., A multi-agent model describing self-renewal of differentiation effects on the blood cell population, Mathematical and Computer Modelling, 49, 11-12, 2116-2127 (2009) · Zbl 1171.92312 · doi:10.1016/j.mcm.2008.07.023 |
| [3] | Agnetis, A.; Pacciarelli, D.; Pacifici, A., Multi-agent single machine scheduling, Annals of Operations Research, 150, 1, 3-15 (2007) · Zbl 1144.90375 · doi:10.1007/s10479-006-0164-y |
| [4] | 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 |
| [5] | 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 |
| [6] | 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 |
| [7] | Cheng, T. C.; 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, 1-3, 273-281 (2006) · Zbl 1100.68007 · doi:10.1016/j.tcs.2006.07.011 |
| [8] | Ng, C. T.; Cheng, T. C.; Yuan, J. J., A note on the complexity of the problem of two-agent scheduling on a single machine, Journal of Combinatorial Optimization, 12, 4, 387-394 (2006) · Zbl 1126.90027 · doi:10.1007/s10878-006-9001-0 |
| [9] | Cheng, T. C.; Ng, C. T.; Yuan, J. J., Multi-agent scheduling on a single machine with max-form criteria, European Journal of Operational Research, 188, 2, 603-609 (2008) · Zbl 1129.90023 · doi:10.1016/j.ejor.2007.04.040 |
| [10] | Agnetis, A.; de Pascale, G.; Pacciarelli, D., A Lagrangian approach to single-machine scheduling problems with two competing agents, Journal of Scheduling, 12, 4, 401-415 (2009) · Zbl 1185.90063 · doi:10.1007/s10951-008-0098-0 |
| [11] | Lee, K.; Choi, B. C.; Leung, J. Y.; Pinedo, M. L., Approximation algorithms for multi-agent scheduling to minimize total weighted completion time, Information Processing Letters, 109, 16, 913-917 (2009) · Zbl 1205.68516 · doi:10.1016/j.ipl.2009.04.018 |
| [12] | Leung, J. Y.; Pinedo, M.; Wan, G., Competitive two-agent scheduling and its applications, Operations Research, 58, 2, 458-469 (2010) · Zbl 1233.90163 · doi:10.1287/opre.1090.0744 |
| [13] | Yin, Y.; Cheng, S.-R.; Cheng, T. C.; Wu, C.-C.; Wu, W.-H., Two-agent single-machine scheduling with assignable due dates, Applied Mathematics and Computation, 219, 4, 1674-1685 (2012) · Zbl 1291.90102 · doi:10.1016/j.amc.2012.08.008 |
| [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.; Wu, C.-C.; Wu, W.-H.; Hsu, C.-J.; Wu, W.-H., A branch-and-bound procedure for a single-machine earliness scheduling problem with two agents, Applied Soft Computing Journal, 13, 2, 1042-1054 (2013) · doi:10.1016/j.asoc.2012.09.026 |
| [16] | Nong, Q. Q.; Cheng, T. C.; Ng, C. T., Two-agent scheduling to minimize the total cost, European Journal of Operational Research, 215, 1, 39-44 (2011) · Zbl 1237.90094 · doi:10.1016/j.ejor.2011.05.041 |
| [17] | Wan, G.; Vakati, S. R.; Leung, J. Y.; Pinedo, M., Scheduling two agents with controllable processing times, European Journal of Operational Research, 205, 3, 528-539 (2010) · Zbl 1188.90114 · doi:10.1016/j.ejor.2010.01.005 |
| [18] | Luo, W.; Chen, L.; Zhang, G., Approximation schemes for two-machine flow shop scheduling with two agents, Journal of Combinatorial Optimization, 24, 3, 229-239 (2012) · Zbl 1261.90019 · doi:10.1007/s10878-011-9378-2 |
| [19] | Yin, Y.; Cheng, S.-R.; Cheng, T. C. E.; Wu, W.-H.; Wu, C.-C., Two-agent single-machine scheduling with release times and deadlines, International Journal of Shipping and Transport Logistics, 5, 1, 75-94 (2013) · doi:10.1504/IJSTL.2013.050590 |
| [20] | Liu, P.; Tang, L., Two-agent scheduling with linear deteriorating jobs on a single machine, Computing and Combinatorics: Proceedings of the 14th Annual International Conference, COCOON 2008 Dalian, China, June 27-29, 2008. Computing and Combinatorics: Proceedings of the 14th Annual International Conference, COCOON 2008 Dalian, China, June 27-29, 2008, Lecture Notes in Computer Science, 5092, 642-650 (2008), Berlin, Germany: Springer, Berlin, Germany · Zbl 1148.90324 · doi:10.1007/978-3-540-69733-6_63 |
| [21] | Liu, P.; Yi, N.; Zhou, X., Two-agent single-machine scheduling problems under increasing linear deterioration, Applied Mathematical Modelling, 35, 5, 2290-2296 (2011) · Zbl 1217.90108 · doi:10.1016/j.apm.2010.11.026 |
| [22] | 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, 21, 8804-8824 (2011) · Zbl 1231.90182 · doi:10.1016/j.amc.2011.04.005 |
| [23] | Cheng, T. C.; Chung, Y. H.; Liao, S. C.; Lee, W. C., Two-agent singe-machine scheduling with release times to minimize the total weighted completion time, Computers & Operations Research, 40, 1, 353-361 (2013) · Zbl 1349.90329 · doi:10.1016/j.cor.2012.07.013 |
| [24] | Wu, C.-C.; Huang, S.-K.; Lee, W.-C., Two-agent scheduling with learning consideration, Computers and Industrial Engineering, 61, 4, 1324-1335 (2011) · doi:10.1016/j.cie.2011.08.007 |
| [25] | Li, D.-C.; Hsu, P.-H., Solving a two-agent single-machine scheduling problem considering learning effect, Computers and Operations Research, 39, 7, 1644-1651 (2012) · Zbl 1251.90165 · doi:10.1016/j.cor.2011.09.018 |
| [26] | Yin, Y.; Liu, M.; Hao, J.; Zhou, M., Single-machine scheduling with job-position-dependent learning and time-dependent deterioration, IEEE Transactions on Systems, Man, and Cybernetics, Part A: Systems and Humans, 42, 1, 192-200 (2012) · doi:10.1109/TSMCA.2011.2147305 |
| [27] | 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 |
| [28] | Yin, Y.; 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 |
| [29] | Wu, W.-H., Solving a two-agent single-machine learning scheduling problem, International Journal of Computer Integrated Manufacturing, 27, 1, 20-35 (2014) · doi:10.1080/0951192X.2013.800229 |
| [30] | Li, D.-C.; Hsu, P.-H.; Chang, C.-C., A genetic algorithm-based approach for single-machine scheduling with learning effect and release time, Mathematical Problems in Engineering, 2014 (2014) · Zbl 1407.90160 · doi:10.1155/2014/249493 |
| [31] | Kirkpatrick, S.; Gelatt, J.; Vecchi, M. P., Optimization by simulated annealing, Science, 220, 4598, 671-680 (1983) · Zbl 1225.90162 · doi:10.1126/science.220.4598.671 |
| [32] | Kim, B.-I.; Chang, S. Y.; Chang, J.; Han, Y.; Koo, J.; Lim, K.; Shin, J.; Jeong, S.; Kwak, W., Scheduling of raw-material unloading from ships at a steelworks, Production Planning and Control, 22, 4, 389-402 (2011) · doi:10.1080/09537287.2010.488923 |
| [33] | Sun, Y.; Fowler, J. W.; Shunk, D. L., Policies for allocating product lots to customer orders in semiconductor manufacturing supply chains, Production Planning and Control, 22, 1, 69-80 (2011) · doi:10.1080/09537287.2010.490020 |
| [34] | Nawaz, M.; Enscore, E. E.; Ham, I., A heuristic algorithm for the m-machine, n-job flow-shop sequencing problem, Omega, 11, 1, 91-95 (1983) · doi:10.1016/0305-0483(83)90088-9 |
| [35] | Ben-Arieh, D.; Maimon, O., Annealing method for PCB assembly scheduling on two sequential machines, International Journal of Computer Integrated Manufacturing, 5, 6, 361-367 (1992) · doi:10.1080/09511929208944543 |
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.
