×

zbMATH — the first resource for mathematics

Bi-objective scheduling on a restricted batching machine. (English) Zbl 06938902
Summary: In this work, we consider a batching machine that can process several jobs at the same time. Batches have a restricted batch size, and the processing time of a batch is equal to the largest processing time among all jobs within the batch. We solve the bi-objective problem of minimizing the maximum lateness and number of batches. This function is relevant as we are interested in meeting due dates and minimizing the cost of handling each batch. Our aim is to find the Pareto-optimal solutions by using an epsilon-constraint method on a new mathematical model that is enhanced with a family of valid inequalities and constraints that avoid symmetric solutions. Additionally, we present a biased random-key genetic algorithm to approximate the optimal Pareto points of larger instances in reasonable time. Experimental results show the efficiency of our methodologies.

MSC:
90B Operations research and management science
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Aloulou, M. A.; Bouzaiene, A.; Dridi, N.; Vanderpooten, D., A bicriteria two-machine flow-shop serial-batching scheduling problem with bounded batch size, J. Schedul., 17, 1, 17-29, (2014) · Zbl 1297.90027
[2] Brucker, P.; Gladky, A.; Hoogeveen, H.; Kovalyov, M.; Potts, C.; Tautenhahn, T.; van de Velde, S., Scheduling a batching machine, J. Schedul., 1, 1, 31-54, (1998) · Zbl 0909.90172
[3] Cabo, M.; Possani, E.; Potts, C. N.; Song, X., Split-merge: using exponential neighborhood search for scheduling a batching machine, Comput. Oper. Res., 63, 125-135, (2015) · Zbl 1349.90322
[4] Damm, R. B.; Resende, M. G.; Ronconi, D. P., A biased random key genetic algorithm for the field Technician scheduling problem, Comput. Oper. Res., 75, 49-63, (2016) · Zbl 1349.90334
[5] Dauzère-Pérès, S.; Mönch, L., Scheduling jobs on a single batch processing machine with incompatible job families and weighted number of tardy jobs objective, Comput. Oper. Res., 40, 5, 1224-1233, (2013) · Zbl 1352.90035
[6] Ehrgott, M., Multicriteria optimization, (2006), Springer Science & Business Media
[7] Fan, B.; Yuan, J.; Li, S., Bi-criteria scheduling on a single parallel-batch machine, Appl. Math. Model., 36, 1338-1346, (2012) · Zbl 1243.90061
[8] Feng, Q.; Yuan, J.; Liu, H.; He, C., A note on two-agent scheduling on an unbounded parallel-batching machine with makespan and maximum lateness objectives, Appl. Math. Model., 37, 10-11, 7071-7076, (2013)
[9] Geng, Z.; Yuan, J., Pareto optimization scheduling of family jobs on a p-batch machine to minimize makespan and maximum lateness, Theor. Comput. Sci., 570, 22-29, (2015) · Zbl 1306.90051
[10] Gonçalves, J. F.; Resende, M. G., Biased random-key genetic algorithms for combinatorial optimization, J. Heuristics, 17, 5, 487-525, (2011)
[11] Graham, R. L.; Lawler, E. L.; Lenstra, J. K.; Rinnoy Kan, A. H.G., Optimization and approximation in deterministic sequencing and scheduling: a survey, Ann. Discrete Math., 5, 287-326, (1979) · Zbl 0411.90044
[12] He, C.; Lin, H.; Lin, Y., Bounded serial-batching scheduling for minimizing maximum lateness and makespan, Discrete Optim., 16, 70-75, (2015) · Zbl 1387.90090
[13] He, C.; Lin, H.; Lin, Y.; Tian, J., Bicriteria scheduling on a series-batching machine to minimize maximum cost and makespan, Central Euro. J. Oper. Res., 21, 1, 177-186, (2013) · Zbl 1339.90139
[14] Hoogeveen, H., Multicriteria scheduling, Euro. J. Oper. Res., 167, 592-623, (2005) · Zbl 1154.90458
[15] Mathirajan, M.; Sivakumar, A., A literature review, classification and simple meta-analysis on scheduling of batch processors in semiconductor, Int. J. Adv. Manuf. Technol., 29, 9, 990-1001, (2006)
[16] Mathirajan, M.; Sivakumar, A.; P., K., An efficient simulated annealing algorithm for scheduling burn-in oven with non-identical job-sizes, Int. J. Appl. Manag. Technol., 2, 2, 117-138, (2004)
[17] Matin, H. N.; Salmasi, N.; Shahvari, O., Makespan minimization in flowshop batch processing problem with different batch compositions on machines, Int. J. Product. Econ., 193, 832-844, (2017)
[18] Mavrotas, G., Effective implementation of the ε-constraint method in multi-objective mathematical programming problems, Appl. Math. Comput., 213, 2, 455-465, (2009) · Zbl 1168.65029
[19] Mönch, L.; Fowler, J. W.; Dauzère-Pérès, S.; Mason, S. J.; Rose, O., A survey of problems, solution techniques, and future challenges in scheduling semiconductor manufacturing operations, J. Schedul., 14, 6, 583-599, (2011)
[20] Morán-Mirabal, L. F.; González-Velarde, J. L.; Resende, M. G., Randomized heuristics for the family traveling salesperson problem, Int. Trans. Oper. Res., 21, 1, 41-57, (2014) · Zbl 1291.90206
[21] Ruiz, E.; Albareda-Sambola, M.; Fernández, E.; Resende, M. G., A biased random-key genetic algorithm for the capacitated minimum spanning tree problem, Comput. Oper. Res., 57, 95-108, (2015) · Zbl 1348.90553
[22] Sabouni, M. T.Y.; Jolai, F., Optimal methods for batch processing problem with makespan and maximum lateness objectives, Appl. Math. Model., 34, 314-324, (2010) · Zbl 1185.90092
[23] Shahvari, O.; Logendran, R., A bi-objective batch processing problem with dual-resources on unrelated-parallel machines, Appl. Soft Comput., 61, Supplement C, 174-192, (2017)
[24] Tangpattanakul, P.; Jozefowiez, N.; Lopez, P., Biased random key genetic algorithm with hybrid decoding for multi-objective optimization, Computer Science and Information Systems (FedCSIS), 2013 Federated Conference on, 393-400, (2013), IEEE
[25] Toso, R. F.; Resende, M. G., A C++ application programming interface for biased random-key genetic algorithms, Optim. Methods Softw., 30, 1, 81-93, (2015)
[26] Wang, C.-S.; Uzsoy, R., A genetic algorithm to minimize lateness on a batch processing machine, Comput. Oper. Res., 29, 1621-1640, (2002)
[27] Wolsey, L. A., Integer programming, Vol. 42, (1998), Wiley New York · Zbl 0930.90072
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.