A bi-objective model for a scheduling problem of unrelated parallel batch processing machines with fuzzy parameters by two fuzzy multi-objective meta-heuristics

Document Type: Research Paper

Authors

1 Department of Industrial Engineering, Science and Research Branch, Islamic Azad University,Tehran, Iran

2 School of Industrial Engineering, College of Engineering, University of Tehran, Tehran, Iran and Arts et Mtiers ParisTech, LCFC, Metz, France

3 Department of Industrial Engineering, Faculty of Engineering, Kharazmi University, Tehran, Iran

Abstract

This paper considers a bi-objective model for a scheduling problem of unrelated parallel batch processing machines to minimize the makespan and maximum tardiness, simultaneously. Each job has a specific size and the data corresponding to its ready time, due date and processing time-dependent machine are uncertain and determined by trapezoidal fuzzy numbers. Each machine has a specific capacity, in which the number of jobs assigned to each batch on the machine does not violate the machine capacity. The batch processing time, the batch ready time and the batch due date are presented by the longest processing time, the longest ready time and the shortest due date of the jobs that belong to the batch, respectively. To determine the longest and shortest time, the method suggested by Jiménez et al.\cite{c18} is used for ranking the fuzzy numbers. A bi-objective fuzzy mixed-integer linear programming model is proposed and solved by two exact methods (i.e., two-phase fuzzy and $\epsilon$-constraint) for small-sized problems to obtain a set of Pareto solutions. Because the problem belongs to the class NP-hard, two meta-heuristics, namely fuzzy non-dominated sorting genetic algorithm (FNSGA-II) and fuzzy multi-objective discrete teaching–learning-based optimization (FMODTLBO), are proposed. Then, the comparison of results is illustrated to show their performances. Furthermore, a new representation of the solutions is a matrix with two rows and $N$ columns (i.e., jobs) used to assign the jobs to the batches that processed on the machines.

Keywords


[1] J. E. Arroyo, J. Leung, Scheduling unrelated parallel batch processing machines with non-identical job sizes and
unequal ready times, Computers and Operations Research, 78 (2017), 117{128.
[2] J. E. Arroyo, J. Leung, An effective iterated greedy algorithm for scheduling unrelated parallel batch machines with
non-identical capacities and unequal ready times, Computer and Industrial Engineering, 105 (2017), 84{100.
[3] S. F. Attar, M. Mohammadi, R. Tavakkoli-Moghaddam, Hybrid flexible owshop scheduling problem with unrelated
parallel machines and limited waiting times, International Journal Advanced Manufacturing Technology, 68 (2013),
1583{1599.
[4] J. Brank, K. Deb, K. Miettinen, R. Slowinski, Multiobjective optimization- interactive and evolutionary approach,
Springer, 2008.
[5] B. Cheng, K. Li, B. Chen, Scheduling a single batch-processing machine with non-identical job size in fuzzy envi-
ronment using an improved ant colony optimization, Journal of Manufacturing Systems, 29(1) (2010), 29{34.
[6] B. Cheng, S. Yang, X. Hu, B. Chen, Minimizing makespan and total completion time for parallel batch processing
machines with non-identical job sizes, Applied Mathematical Modelling, 36(7) (2012), 3161{3167.
[7] B. Cheng, Q. Wang, S. Yang, X. Hu, An improved ant colony optimization for scheduling identical parallel batching
machines with arbitrary job sizes, Applied Soft Computing, 13(2) (2013), 765{772.
[8] P. Damodaran, M. C. Velez-Gallego, Heuristics for makespan minimization on parallel batch processing machines
with unequal job ready times, International Journal Advanced Manufacturing Technology, 49(9) (2010), 1119{1128.

[9] P. Damodaran, M. C. Velez-Gallego, A simulated annealing algorithm to minimize makespan of parallel batch pro-
cessing machines with unequal job ready times, Expert Systems with Applications, 39(1) (2012), 1451{1458.
[10] P. Damodaran, M. C. Velez-Gallego, J. Maya, A GRASP approach for makespan minimization on parallel batch
processing machines, 22(5) (2011), 767{777.
[11] K. Deb, A. Pratap, S. Agarwal, T. Meyarivan, A fast and elitist multiobjective genetic algorithm: NSGA-II, IEEE
Transactions on Evolutionary Computation, 6(2) (2002), 182{197.
[12] S. Dousthaghi, R. Tavakoli-Moghadam, A. Makui, Solving the economic lot and delivery scheduling problem in a
flexible job shop with unrelated parallel machines and a shelf life by a proposed hybrid PSO, International Journal
Advanced Manufacturing Technology, 68 (2013), 1401{1416.
[13] A. H. Gharehgozli, R. Tavakkoli-Moghaddam, N. Zaerpour, A fuzzy-mixed-integer goal programming model for a
parallel-machine scheduling problem` with sequence-dependent setup times and release dates, Robotics and Computer-
Integrated Manufacturing, 25 (2009), 853{859.
[14] Y. Y. Han, X. W. Gong, X. Y. Sun, Q. K. Pan, An improved NSGA-II algorithm for multi- objective lot-streaming
flow shop scheduling problem, International Journal of Production Research, 25(8) (2013), 2211{2231.
[15] M. Huletta, P. Damodaran, M. Amouie, Scheduling non-identical parallel batch processing machines to minimize
total weighted tardiness using particle swarm optimization, Computers and Industrial Engineering, 113 (2017),
425{436.
[16] Z. Jia, Y. Zhang, J. Leung, K. Li, Bi-criteria ant colony optimization algorithm for minimizing makespan and
energy consumption on parallel batch machines, Applied Soft Computing, 55 (2017), 226{237.

[17] L. Jiang, J. Pei, X. Liu, P. M. Pardalos, Y. Yang, X. Qian, Uniform parallel batch machines scheduling consid-
ering transportation using a hybrid DPSO-GA algorithm, The International Journal of Advanced Manufacturing
Technology, 89 (2017), 1887{1900.
[18] M. Jimnez, M. Arenas, A. Bilbao, M. V. Rodrguez, Linear programming with fuzzy parameters: an interactive
method resolution, European Journal of Operational Research, 177 (2007), 1599{1609.
[19] C. M. Joo, B. S. Kim, Rule-based meta-heuristics for integrated scheduling of unrelated parallel machines, batches,
and heterogeneous delivery trucks, Applied Soft Computing, 53 (2017), 457{476.
[20] A. H. Kashan, B. Karimi, F. Jolai, An effective hybrid multi-objective genetic algorithm for bi-criteria scheduling
on a single batch processing machine with non-identical job sizes, Engineering Applications of Arti cial Intelligence,
23(6) (2010), 911{922.
[21] X. Li, Y. Huang, Q. Tan, H.P. Chen, Scheduling unrelated parallel batch processing machines with non-identical
job sizes, Computers and Operations Research, 40(12) (2013), 2983{2990.
[22] X. Li, H. Ishii, M. Chen, Single machine parallel-batching scheduling problem with fuzzy due-date and fuzzy prece-
dence relation, International Journal of Production Research, 53(9) (2015), 2707{2717.
[23] J. Q. Li, Q. K. Pan, K. Mao, A discrete teaching learning based optimization algorithm for realistic flowshop
rescheduling problem, Engineering Application of Artifi cial Intelligence, 37 (2015), 279{292.
[24] X. Q. Li, B. Zhang, H. Li, Computing efficient solutions to fuzzy multiple objective linear programming problems,
Fuzzy Sets and Systems, 157 (2006), 1328{1332.
[25] R. Ma, L. Wan, L. Wei, J. Yuan, Online bounded-batch scheduling to minimize total weighted completion time on
parallel machines, International Journal of Production Economics, 156 (2014), 31{38.
[26] E. Mehdizadeh, R. Tavakkoli-Moghaddam, M. Yazdani, A vibration damping optimization algorithm for a parallel
machines scheduling problem with sequence-independent family setup times, Applied Mathematical Modelling, 39
(2015), 6845{6859.
[27] A. Mehrabian, R. Tavakoli-Moghaddam, K. Khalili-Damaghani, Multi-objective routing and scheduling in flexible
manufacturing system under uncertainty, Iranian Journal of Fuzzy Systems, 14 (2017), 45{77.
[28] S. Molla-Alizadeh-Zavardehi, R. Tavakkoli-Moghaddam, F. Hosseinzadeh Lotfi , A modifi ed imperialist competitive
algorithm for scheduling single batch-processing machine with fuzzy due date, The International Journal of Advanced
Manufacturing Technology, 85(12) (2016), 2439{2458.
[29] D. C. Montgomery, Design and analysis of experiments, 8th Ed., Mississauga, John Wiley and Sons, 2012.
[30] M. Naderi-Beni, E. Ghobadian, S. Ebrahimnejad, R. TavakkoliMoghaddam, Fuzzy bi-objective formulation for
a parallel machine scheduling problem with machine eligibility restrictions and sequence-dependent setup times,
International Journal of Production Research, 52(19) (2014), 5799{5822.
[31] F. Nadi, A. Tajudin Khader, A study on the utility of parametric uniform crossover for adaptation of crossover
operator, Arti cial Intelligence: Methodology, Systems, and Applications, 7557 (2012), 178{183.
[32] R. V. Rao, V. J. Savsani, D. P. Vakharia, Teachinglearning-based optimization: A novel method for constrained
mechanical design optimization problems, Computer-Aided Design, 43 (2011), 303{315.
[33] B. Shahidi-Zadeh, R. Tavakkoli-Moghaddam, A. Taheri-Moghadamb, I. Rastgar, Solving a bi-objective unrelated
parallel batch processing machines scheduling problem: A comparison study, Computers and Operations Research,
88 (2017), 71{90.
[34] O. Shahvari, R. Logendran, An Enhanced tabu search algorithm to minimize a bi-criteria objective in batching
and scheduling problems on unrelated-parallel machines with desired lower bounds on batch sizes, Computers and
Operations Research, 77 (2017), 154{176.
[35] O. Shahvari, R. Logendran, A bi-objective batch processing problem with dual-resources on unrelated-parallel ma-
chines, Applied Soft Computing, 61 (2017), 174{192.

[36] R. Tavakkoli-Moghaddam, F. Taheri, M. Bazzazi, M. Izadi, F. Sassani, Design of a genetic algorithm for bi-objective
unrelated parallel machines scheduling with sequence-dependent setup times and precedence constraints, Computers
and Operations Research, 36 (2009), 3224{3230.
[37] H. M. Wang, F. D. Chou, Solving the parallel batch-processing machines with different release times, job sizes, and
capacity limits by meta-heuristics, Expert Systems with Applications, 37 (2010), 1510{1521.
[38] R. Xu, H. Chen, X. Li, A bi-objective scheduling problem on batch machines via a pareto-based ant colony system,
International Journal of Production Economics, 145(1) (2013), 371{386.
[39] S. Zhou, M. Liu, H. Chen, X. Li, An effective discrete differential evolution algorithm for scheduling uniform parallel
batch processing machines with non-identical capacities and arbitrary job sizes, International Journal of Production
Economics, 179 (2016), 1{11.
[40] H. J. Zimmermann, Fuzzy programming and linear programming with several objective functions, Fuzzy Sets and
Systems, 1 (1978), 45{55.