Two-agent scheduling on a single parallel-batching machine with equal processing time and non-identical job sizes. (English) Zbl 1394.90310
Summary: We schedule the jobs from two agents on a single parallel-batching machine with equal processing time and non-identical job sizes. The objective is to minimize the makespan of the first agent subject to an upper bound on the makespan of the other agent. We show that there is no polynomial-time approximation algorithm for solving this problem with a finite worst-case ratio, unless \(P = N P\). Then, we propose an effective algorithm \(LB\) to obtain a lower bound of the optimal solution, and two algorithms, namely, reserved-space heuristic (RSH) and dynamic-mix heuristic (DMH), to solve the two-agent scheduling problem. Finally, we evaluate the performance of the proposed algorithms with a set of computational experiments. The results show that algorithm \(LB\) works well and tends to perform better with the increase of the number of jobs. Furthermore, our results demonstrate that RSH and DMH work well on different cases. Specifically, when the optimal makespan on the first agent exceeds the upper bound of the makespan of the other agent, RSH outperforms or equals DMH, otherwise DMH is not less favorable than RSH.
MSC:
| 90B35 | Deterministic scheduling theory in operations research |
| 90C59 | Approximation methods and heuristics in mathematical programming |
| 90C60 | Abstract computational complexity for mathematical programming problems |
| 68M20 | Performance evaluation, queueing, and scheduling in the context of computer systems |
References:
| [1] | Agnetis, A.; Billaut, J.-C.; Gawiejnowicz, S.; Pacciarelli, D.; Soukhal, A., Multiagent scheduling-models and algorithms (2014), Springer · Zbl 1286.90002 |
| [2] | 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 |
| [3] | 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 |
| [4] | Baker, K. R.; Smith, J. C., A multiple-criterion model for machine scheduling, Journal of Scheduling, 6, 1, 7-16 (2003) · Zbl 1154.90406 |
| [5] | Chen, H.; Du, B.; Huang, G. Q., Scheduling a batch processing machine with non-identical job sizes: a clustering perspective, International Journal of Production Research, 49, 19, 5755-5778 (2011) |
| [6] | Cheng, T. C.E.; 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 |
| [7] | Chou, F.-D.; Chang, P.-C.; Wang, H.-M., A hybrid genetic algorithm to minimize makespan for the single batch machine dynamic scheduling problem, The International Journal of Advanced Manufacturing Technology, 31, 3-4, 350-359 (2005) |
| [8] | Damodaran, P.; Manjeshwar, P. K.; Srihari, K., Minimizing makespan on a batch-processing machine with non-identical job sizes using genetic algorithms, International Journal of Production Economics, 103, 2, 882-891 (2006) |
| [9] | Dupont, L.; Dhaenens-Flipo, C., Minimizing the makespan on a batch machine with non-identical job sizes: an exact procedure, Computers & Operations Research, 29, 7, 807-819 (2002) · Zbl 0995.90081 |
| [10] | Fan, B. Q.; Cheng, T. C.E.; Li, S. S.; Feng, Q., Bounded parallel-batching scheduling with two competing agents, Journal of Scheduling, 16, 3, 261-271 (2012) · Zbl 1280.90043 |
| [11] | Garey, M. R.; Johnson, D. S., Computers and intractability: A guide to the theory of NP-completeness (1979), W.H.Freeman & Co Ltd · Zbl 0411.68039 |
| [12] | Graham, R. L.; Lawler, E. L.; Lenstra, J. K.; Rinnooy-Kan, A. H.G., Optimization and approximation in deterministic sequencing and scheduling: A survey, Annals of Discrete Mathematics, 5, 287-326 (1979) · Zbl 0411.90044 |
| [13] | Hochbaum, D. S., Approximation algorithms for NP-hard problems (1996), PWS Publishing Co. · Zbl 1368.68010 |
| [14] | Ikura, Y.; Gimple, M., Efficient scheduling algorithms for a single batch processing machine, Operations Research Letters, 5, 2, 61-65 (1986) · Zbl 0594.90045 |
| [15] | Johnson, D. S., Near optimal bin packing algorithms (1973), Massachusetts Institute of Technology, Dept. of Mathematics, (Doctoral thesis) |
| [16] | Kashan, A. H.; Karimi, B.; Jolai, F., Effective hybrid genetic algorithm for minimizing makespan on a single-batch-processing machine with non-identical job sizes, International Journal of Production Research, 44, 12, 2337-2360 (2006) · Zbl 1095.90039 |
| [17] | Koh, S.-G.; Koo, P.-H.; Kim, D.-C.; Hur, W.-S., Scheduling a single batch processing machine with arbitrary job sizes and incompatible job families, International Journal of Production Economics, 98, 1, 81-96 (2005) |
| [18] | Lee, C. Y., Minimizing makespan on a single batch processing machine with dynamic job arrivals, International Journal of Production Research, 37, 1, 219-236 (1999) · Zbl 0939.90537 |
| [19] | Lee, C. Y.; Uzsoy, R.; Martin-Vega, L. A., Efficient algorithms for scheduling semiconductor burn-in operations, Operations Research, 40, 4, 764-775 (1992) · Zbl 0759.90046 |
| [20] | Leung, J. Y.-T.; Pinedo, M.; Wan, G., Competitive two-agent scheduling and its applications, Operations Research, 58, 2, 458-469 (2010) · Zbl 1233.90163 |
| [21] | Li, S.; Li, G.; Wang, X.; Liu, Q., Minimizing makespan on a single batching machine with release times and non-identical job sizes, Operations Research Letters, 33, 2, 157-164 (2005) · Zbl 1099.90021 |
| [22] | Li, S.; Yuan, J., Unbounded parallel-batching scheduling with two competitive agents, Journal of Scheduling, 15, 5, 629-640 (2011) · Zbl 1280.90061 |
| [23] | Liu, Z.; Yu, W., Scheduling one batch processor subject to job release dates, Discrete Applied Mathematics, 105, 1-3, 129-136 (2000) · Zbl 0969.90046 |
| [24] | Mathirajan, M.; Chandru, V.; Sivakumar, A. I., Heuristic algorithms for scheduling heat-treatment furnaces of steel casting industries, Sadhana, 32, 5, 479-500 (2007) |
| [25] | Mathirajan, M.; Sivakumar, A. I., A literature review, classification and simple meta-analysis on scheduling of batch processors in semiconductor, The International Journal of Advanced Manufacturing Technology, 29, 9-10, 990-1001 (2006) |
| [26] | Melouk, S.; Damodaran, P.; Chang, P.-Y., Minimizing makespan for single machine batch processing with non-identical job sizes using simulated annealing, International Journal of Production Economics, 87, 2, 141-147 (2004) |
| [27] | Mor, B.; Mosheiov, G., Single machine batch scheduling with two competing agents to minimize total flowtime, European Journal of Operational Research, 215, 3, 524-531 (2011) · Zbl 1238.90069 |
| [28] | Parsa, N. R.; Karimi, B.; Husseinzadeh-Kashan, A., A branch and price algorithm to minimize makespan on a single batch processing machine with non-identical job sizes, Computers & Operations Research, 37, 10, 1720-1730 (2010) · Zbl 1188.90105 |
| [29] | Perez-Gonzalez, P.; Framinan, J. M., A common framework and taxonomy for multicriteria scheduling problems with interfering and competing jobs: Multi-agent scheduling problems, European Journal of Operational Research, 235, 1, 1-16 (2014) · Zbl 1305.90196 |
| [30] | Potts, C. N.; Kovalyov, M. Y., Scheduling with batching: A review, European Journal of Operational Research, 120, 2, 228-249 (2000) · Zbl 0953.90028 |
| [31] | Siegel, S., Nonparametric statistics for the behavioral sciences. Nonparametric statistics for the behavioral sciences, McGraw-Hill series in psychology (1956), McGraw-Hill · Zbl 0071.35301 |
| [32] | Soomer, M. J.; Franx, G. J., Scheduling aircraft landings using airlines preferences, European Journal of Operational Research, 190, 1, 277-291 (2008) · Zbl 1146.90424 |
| [33] | Sung, C. S.; Choung, Y. I., Minimizing makespan on a single burn-in oven in semiconductor manufacturing, European Journal of Operational Research, 120, 3, 559-574 (2000) · Zbl 0971.90033 |
| [34] | Sung, C. S.; Choung, Y. I.; Hong, J. M.; Kim, Y. H., Minimizing makespan on a single burn-in oven with job families and dynamic job arrivals, Computers & Operations Research, 29, 8, 995-1007 (2002) · Zbl 0995.90036 |
| [35] | SURFsara, SURFsara - The Lisa system (2015) |
| [36] | Uzsoy, R., Scheduling a single batch processing machine with non-identical job sizes, International Journal of Production Research, 32, 7, 1615-1635 (1994) · Zbl 0906.90095 |
| [37] | Van-Der-Zee, D. J.; Harten, A. V.; Schuur, P. C., Dynamic job assignment heuristics for multi-server batch operations - A cost based approach, International Journal of Production Research, 35, 11, 3063-3094 (1997) · Zbl 0946.90525 |
| [38] | Wang, J.; Chen, J.; Zhang, Y.; Huang, G. Q., Schedule-based execution bottleneck identification in a job shop, Computers & Industrial Engineering, 98, 308-322 (2016) |
| [39] | Wang, J.; Leung, J. Y.T., Scheduling jobs with equal-processing-time on parallel machines with non-identical capacities to minimize makespan, International Journal of Production Economics, 156, 325-331 (2014) |
| [40] | Xu, R.; Chen, H.; Li, X., Makespan minimization on single batch-processing machine via ant colony optimization, Computers & Operations Research, 39, 3, 582-593 (2012) · Zbl 1251.90201 |
| [41] | Yaghubian, A. R.; Hodgson, T. J.; Joines, J. A., Dry-or-buy decision support for dry kiln scheduling in furniture production, IIE Transactions, 33, 2, 131-136 (2001) |
| [42] | Yin, Y.; Cheng, T. C.E.; Wan, L.; Wu, C.-C.; Liu, J., Two-agent single-machine scheduling with deteriorating jobs, Computer & Industrial Engineering, 81, 177-185 (2015) |
| [43] | Zhang, G.; Cai, X.; Lee, C. Y.; Wong, C. K., Minimizing makespan on a single batch processing machine with nonidentical job sizes, Naval Research Logistics, 48, 3, 226-240 (2001) · Zbl 1027.90041 |
| [44] | Zhao, K.; Lu, X., Approximation schemes for two-agent scheduling on parallel machines, Theoretical Computer Science, 468, 114-121 (2013) · Zbl 1259.68085 |
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.
