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.

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.

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

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