×

Scheduling jobs on a single serial-batching machine with dynamic job arrivals and multiple job types. (English) Zbl 1338.90181

Summary: This paper investigates a scheduling model with certain co-existing features of serial-batching, dynamic job arrival, multi-types of job, and setup time. In this proposed model, the jobs of all types are first partitioned into serial batches, which are then processed on a single serial-batching machine with an independent constant setup time for each new batch. In order to solve this scheduling problem, we divide it into two phases based on job arrival times, and we also derive and prove certain constructive properties for these two phases. Relying on these properties, we develop a two-phase hybrid algorithm (TPHA). In addition, a valid lower bound of the problem is also derived. This is used to validate the quality of the proposed algorithm. Computational experiments, both with small- and large-scale problems, are performed in order to evaluate the performance of TPHA. The computational results indicate that TPHA outperforms seven other heuristic algorithms. For all test problems of different job sizes, the average gap percentage between the makespan, obtained using TPHA, and the lower bound does not exceed 5.41 %.

MSC:

90B35 Deterministic scheduling theory in operations research
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Damodaran, P., Diyadawagamage, D.A., Ghrayeb, O., Vélez-Gallego, M.C.: A particle swarm optimization algorithm for minimizing makespan of nonidentical parallel batch processing machines. Int. J. Adv. Manuf. Technol. 58(9-12), 1131-1140 (2012) · doi:10.1007/s00170-011-3442-z
[2] Aloulou, M.A., Bouzaiene, A., Dridi, N., Vanderpooten, D.: A bicriteria two-machine flow-shop serial-batching scheduling problem with bounded batch size. J. Sched. 17(1), 17-29 (2014) · Zbl 1297.90027 · doi:10.1007/s10951-013-0340-2
[3] Ng, C.T., Cheng, T.C.E., Yuan, J.J., Liu, Z.H.: On the single machine serial batching scheduling problem to minimize total completion time with precedence constraints, release dates and identical processing times. Oper. Res. Lett. 31(4), 323-326 (2003) · Zbl 1145.90392
[4] Yuan, J.J., Yang, A.F., Cheng, T.C.E.: A note on the single machine serial batching scheduling problem to minimize maximum lateness with identical processing times. Eur. J. Oper. Res. 158(2), 525-528 (2004) · Zbl 1067.90051 · doi:10.1016/S0377-2217(03)00361-8
[5] Shen, L., Mönch, L., Buscher, U.: An iterative approach for the serial batching problem with parallel machines and job families. Ann. Oper. Res. 206(1), 425-448 (2013) · Zbl 1271.90037 · doi:10.1007/s10479-013-1339-y
[6] Aloulou, M.A., Bouzaiene, A., Dridi, N., Vanderpooten, D.: A bicriteria two-machine flow-shop serial-batching scheduling problem with bounded batch size. J. Sched. 17(1), 17-29 (2014) · Zbl 1297.90027 · doi:10.1007/s10951-013-0340-2
[7] Shabtay, D.: The single machine serial batch scheduling problem with rejection to minimize total completion time and total rejection cost. Eur. J. Oper. Res. 233(1), 64-74 (2014) · Zbl 1339.90153 · doi:10.1016/j.ejor.2013.08.013
[8] Pei, J., Liu, X., Pardalos, P.M., Fan, W., Yang, S.: Single machine serial-batching scheduling with independent setup time and deteriorating job processing times. Optimization Letters 9(1), 91-104 (2015) · Zbl 1306.90058
[9] Pei, J., Pardalos, P.M., Liu, X., Fan, W., Yang, S.: Serial batching scheduling of deteriorating jobs in a two-stage supply chain to minimize the makespan. Eur. J. Oper. Res (2014). doi:10.1016/j.ejor.2014.11.034 · Zbl 1346.90381
[10] Chou, F.-D., Chang, P.-C., Wang, H.-M.: A hybrid genetic algorithm to minimize makespan for the single batch machine dynamic scheduling problem. Int. J. Adv. Manuf. Technol. 31(3-4), 350-359 (2006) · doi:10.1007/s00170-005-0194-7
[11] Sahin, G., Ahuja, R.K.: Single-machine scheduling with stepwise tardiness costs and release times. J. Ind. Manag. Optim. 7(4), 825-848 (2011) · Zbl 1230.90099 · doi:10.3934/jimo.2011.7.825
[12] Lu, M.-S., Romanowski, R.: Multi-contextual ant colony optimization of intermediate dynamic job shop problems. Int. J. Adv. Manuf. Technol. 60(5-8), 667-681 (2012) · doi:10.1007/s00170-011-3634-6
[13] Lu, M.-S., Romanowski, R.: Multicontextual dispatching rules for job shops with dynamic job arrival. Int. J. Adv. Manuf. Technol. 67(1-4), 19-33 (2013) · doi:10.1007/s00170-013-4765-8
[14] Hosseini, N., Tavakkoli-Moghaddam, R.: Two meta-heuristics for solving a new two-machine flowshop scheduling problem with the learning effect and dynamic arrivals 65(5-8), 771-786 (2013) · Zbl 1304.90104
[15] Tao, J., Huang, R., Liu, T.: A 2:28-competitive algorithm for online scheduling on identical machines. J. Ind. Manag. Optim. 11(1), 185-198 (2015) · Zbl 1304.90104 · doi:10.3934/jimo.2015.11.185
[16] Chen, Z.L., Powell, W.B.: Exact algorithms for scheduling multiple families of jobs on parallel machines. Nav. Res. Logist. 50(7), 823-840 (2003) · Zbl 1044.90033 · doi:10.1002/nav.10091
[17] Obeid, A., Dauzere-Peres, S., Yugma, C.: Scheduling job families on non-identical parallel machines with time constraints. Ann. Oper. Res. 213(1), 221-234 (2014) · Zbl 1296.90055 · doi:10.1007/s10479-012-1107-4
[18] Li, W., Yuan, J.: Improved online algorithms for the batch scheduling of equal-length jobs with incompatible families to maximize the weighted number of early jobs. Optimization Letters 8(5), 1691-1706 (2014) · Zbl 1310.90046 · doi:10.1007/s11590-013-0650-5
[19] Pei, J., Liu, X., Pardalos, P.M., Fan, W., Yang, S., Wang, L.: Application of an effective modified gravitational search algorithm for the coordinated scheduling problem in a two-stage supply chain. Int. J. Adv. Manuf. Technol. 70(1-4), 335-348 (2014) · doi:10.1007/s00170-013-5263-8
[20] Graham, R.L., Lawler, E.L., Lenstra, J.K., Rinnooy Kan, A.H.G.: Optimization and approximation in deterministic machine scheduling: a survey. Ann. Discret. Math. 5, 287-326 (1979) · Zbl 0411.90044 · doi:10.1016/S0167-5060(08)70356-X
[21] Pei, J., Liu, X., Fan, W., Pardalos, P.M., Liu, L.: A novel hybrid dynamic programming algorithm for a two-stage supply chain scheduling problem. Lect. Notes Comput. Sci. 8426, 242-257 (2014) · doi:10.1007/978-3-319-09584-4_23
[22] Gottlieb, J., Raidl, G.R.: Evolutionary Computation in Combinatorial Optimization: 6th European Conference Proceedings. Springer, Berlin Heidelberg New York (2006) · Zbl 1369.68024 · doi:10.1007/11730095
[23] 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. Int. J. Prod. Econ. 98(1), 81-96 (2005) · doi:10.1016/j.ijpe.2004.10.001
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.