A comparison of algorithms for minimizing the sum of earliness and tardiness in hybrid flow-shop scheduling problem with unrelated parallel machines and sequence-dependent setup times

Document Type: Research Paper

Authors

Department of Industrial Engineering, K.N.ToosiUniversity of Technology, Tehran, Iran

Abstract

In this paper, the flow-shop scheduling problem with unrelated parallel machines at each stage as well as sequence-dependent setup times under minimization of the sum of earliness and tardiness are studied. The processing times, setup times and due-dates are known in advance. To solve the problem, we introduce a hybrid memetic algorithm as well as a particle swarm optimization algorithm combined with genetic operators. Also, an application of simulated annealing is presented for the evaluation of the algorithms. A Taguchi design is conducted to set their parameters. Finally, a comparison is made via 16 small size and 24 large size test problems and each problem is run 10times. The results of one-way ANOVA demonstrate that the proposed memetic algorithm performs as efficient as the HSA qualitatively and with 63.77% decline in elapsed time.

Keywords

Main Subjects


Acosta, J. H. T., González, V. A. P., & Bello, C. A. L. (2013). A Genetic Algorithm for
Simultaneous Scheduling Problem in Flexible Flow Shop Environments with Unrelated Parallel
Machines, Setup Time and Multiple Criteria. International Conference on Advanced
Manufacturing Engineering and Technologies. 203-210.
Attar, S.F., Mohammadi, M., & Tavakkoli-Moghaddam, R. (2009). Hybrid flexible flow-shop
scheduling problem with unrelated parallel machines and limited waiting times.Int J Adv Manuf
Technol, 68, 1583-1599.
Behnamian, j., Ghomi, S. M. T. F., & Zandieh, M. (2009). A multi-phase covering Paretooptimal
front method to multi-objective scheduling in a realistic hybrid flowshop using a hybrid
metaheuristic. Expert Syst Appl, 35, 11057-11069.
Behnamian, J., & Zandie, M. (2011). A discrete colonial competitive algorithm for hybrid
flowshop scheduling to minimize earliness and quadratic tardiness penalties. Expert Syst Appl,
38, 14490-14498.
Behnamian, J., & Zandie, M. (2012).Earliness and Tardiness minimizing on a realistic hybrid
flowshop scheduling with learning effect by advanced metaheuristic.Arab J Sci Eng, 38, 1229-
1242.
Crowder, B. (2006). Minimizing the Makespan in a Flexible Flowshop with Sequence
Dependent Setup Times, Uniform Machines, and Limited BuffersMinimizing the Makespan in a
Flexible Flowshop with Sequence Dependent Setup Times, Uniform Machines, and Limited
Buffers. West Virginia University, virginia.
Dai, M., Tang, D., Zheng, K. & Cai, Q. (2013). An improved Genetic-Simulated Annealing
Algorithm based on a Hormone Modulation Mechanism for a flexible flow-shop scheduling
problem. Advances in Mechanical Engineering, 2013, 13 pages, doi:10.1155/2013/124903.
Davoudpour, H., & Ashrafi, M. (2009). Solving multi -objective SDST flexible flow shop using
GRASP algorithm. Int J Adv Manuf Tech, 44, 737-747.
Farkhzad, M. B., & Heydari, M. (2008). A heuristic algorithm for hybrid flow-shop production
scheduling to minimize the sum of the earliness and tardiness costs. JCIIE, 25, 105-115.
Gupta, J. N. D. (1988). Two-stage, hybrid flowshop scheduling problem. J Oper Res Soc, 39,
359-364.
Haddad, M.N., Cota, L.P., Souza, M.J.F. & Maculan, N. (2014). A Heuristic Algorithm based
on Iterated Local Search and Variable Neigbourhood Descent for solving the unrelated parallel
machine scheduling problem with setup times. Proceedings of the 16th International Conference
on Enterprise Information Systems, 376-383.

Janiak, A., Kozan, E., Lichtenstein, M., & Eguz, C. (2007). Metaheuristic approaches to the
hybrid flow shop scheduling problem with a cost-related criterion. Int J Prod Econ, 105(2), 407-
424.
Jolai, F., Rabiee, M. & Asefi, H. (2012). A novel hybrid meta-heuristic algorithm for a no-wait
flexible flow shop scheduling problem with sequence dependent setup times. International
Journal of Production Research, 50(24), 7447-7466.
Jungwattanakit, J., Reodecha, M., Chaovalitwongse, P., & Werner, F. (2005). An Evaluation of
Sequencing Heuristics for Flexible Flowshop Scheduling Problems with Unrelated Parallel
Machines and Dual Criteria. Otto-von-Guericke-Universitat Magdeburg, 28(5), 1-23.
Jungwattanakit, J., Reodecha, M., Chaovalitwongse, P., & Werner, F. (2008). Algorithms for
flexible flow shop problems with unrelated parallel machines, setup times, and dual criteria. Int
J Adv Manuf Tech, 37, 354-370.
Jungwattanakit, J., Reodecha, M., Chaovalitwongse, P., & Werner, F. (2009). A comparison of
scheduling algorithms for flexible flow shop problems with unrelated parallel machines, setup
times, and dual criteria. Comput Oper Res, 36(2), 358-378.
Kurz, M. E., & Askin, R. G. (2004). Scheduling flexible flow lines with sequence-dependent
setup times. Euro JOper Res, 159, 66-82.
Liao, C.-J., Tsengb, C.-T., & Luarn, P. (2007). A discrete version of particle swarm
optimization for flowshop scheduling problems. Comput Oper Res, 34, 3099-3111.
Naderi, B., M. Z., , A. K. G. B., & , V. R. (2009). An improved simulated annealing for hybrid
flowshops with sequence-dependent setup and transportation times to minimize total completion
time and total tardiness. Expert Syst Appl, 36(6), 9625–9633.
Nahavandi, N., & Gangraj, E. A. (2014). A New Lower Bound for Flexible Flow Shop Problem
with Unrelated Parallel Machines. International Journal of Industrial Engineering, 25(1), 65-
70.
Niu, Q., Jiao, B., & Gu, X. (2008). Particle swarm optimization combined with genetic
operators for job shop scheduling problem with fuzzy processing time. Appl Math Comput, 205,
148-158.
Rabiee, M., Rad, R. S., Mazinani, M., & Shafaei, R. (2014). An intelligent hybrid metaheuristic
for solving a case of no-wait two-stage flexible flow shop scheduling problem with
unrelated parallel machines. The International Journal of Advanced Manufacturing Technology,
71(5-8), 1229-1245.
Rashidi, E., Jahandar, M., & Zandieh, M. (2010). An improved hybrid multi -objective parallel
genetic algorithm for hybrid flow shop scheduling with unrelated parallel machines. Int J Adv
Manuf Tech, 49, 1129-1139.
Ruiz, R., & Maroto, C. (2006). A genetic algorithm for hybrid flowshops with sequence
dependent setup times and machine eligibility. Eur J Oper Res, 169, 781-800.
Ruiz, R., & Vázquez-Rodríguez, J. A. (2010). The hybrid flow shop scheduling problem. Eur J
Oper Res, 205, 1-18.
Soltani, S. A., & Karimi, B. (2014). Cyclic hybrid flow shop scheduling problem with limited
buffers and machine eligibility constraints. The International Journal of Advanced
Manufacturing Technology, 1-17.

Tasgetiren, M. F., Liang, Y.-C., Sevlili, M., & Gencyilmaz, G. (2004). Particle Swarm
Optimization Algorithm for Single Machine Total Weighted Tardiness Problem. Paper presented
at the 2004 IEEE.
Urlings, T., Ruiz, R., & Serifo─člu, F. S. (2010). Genetic algorithms with different representation
schemes for complex hybrid flexible flow line problems. IJMHeur, 1(1), 30-54.
Yaurima, V., Burtseva, L., & Tchernykh, A. (2009). Hybrid flowshop with unrelated machines,
sequence-dependent setup time, availability constraints and limited buffers. Comput Oper Res,
56(4), 1452–1463.
Zandieh, M., FatemiGhomi, S. M. T., & MoattarHusseini, S. M. (2006). An immune algorithm
approach to hybrid flow shops scheduling with sequence-dependent setup times. Appl Math
Comput, 180(1), 111-127.
Zandieh, M., Mozaffari, E., & Gholami, M. (2010). A robust genetic algorithm for scheduling
realistic hybrid flexible flow line problems. J Intell Manufa, 21, 731-743.
Zhang, C., Ning, J., & Ouyang, D. (2010). A hybrid alternate two phases particle swarm
optimization algorithm for flow shop scheduling problem. Comput. Ind. Eng., 58, 1-11