Some heuristics for the hybrid flow shop scheduling problem with setup and assembly operations

Abstract: This paper presents a two-stage hybrid flow shop scheduling problem with setup and assembly operations. The proposed study of this paper considers one kind of product with a quantity of demand where each product is made by assembling a set of different parts. At first, the parts are manufactured in a two-stage hybrid flow-shop and then the parts are assembled into products on assembly stage. Setup operations are needed when a machine starts processing the parts or it changes items. The considered objective is minimizing the completion time of all products. Since the problem is classified as NP-hard class, a combinatorial algorithm is proposed. The proposed algorithm is a three-step procedure where we use heuristic, genetic algorithm (GA), simulated annealing (SA), NEH and Johnson’s algorithm. Three lower bounds are presented and improved to evaluate the proposed algorithms. An extensive computational experiment is conducted to compare the performances of the proposed algorithms.

How to cite this paper

 Fattahi, P., Hosseini, S & Jolai, F. (2013). Some heuristics for the hybrid flow shop scheduling problem with setup and assembly operations.International Journal of Industrial Engineering Computations , 4(3), 393-416.

Refrences

Al-Anzi, F.S., & Allahverdi, A. (2009). Heuristics for a two-stage assembly flow shop with bicriteria of maximum lateness and makespan. Computers & Operations Research, 36, 2682-2689.

Allahverdi, A., & Al-Anzi, F.S. (2009). The two-stage assembly scheduling problem to minimize total completion time with setup times. Computers & Operations Research, 36, 2740-2747.

Allahverdi, A., Gupta, J.N.D., & Aldowaisan, T. (1999). A review of scheduling research involving setup considerations. Omega, International Journal of Management Science, 27, 219-239.

Anandaraman, C. (2011). An improved sheep flock heredity algorithm for job shop scheduling and flow shop scheduling problems. International Journal of Industrial Engineering Computations, 2, 749–764.

Blazewicz, J., Ecker, K., Pesch, E., Schmidt. G., & Weglarz, J. (2007). Handbook on Scheduling From Theory to Application. Springer, USA.Blazsik, Z., Imreh, C., & Kovacs, Z. (2008).
Heuristic algorithms for a complex parallel machine scheduling problem. Central European Journal of Operations Research, 16, 379–390.

Chakrabortty, R.K., & Hasin, Md. A. A. (2013). Solving an aggregate production planning problem by using multi-objective genetic algorithm (MOGA) approach. International Journal of Industrial Engineering Computations, 4, 1–12.

Cheng, T.C.E., & Wang, G. (1999). Scheduling the fabrication and assembly of components in a two-machine flow shop. IIE Transactions, 31, 135-143.

Fattahi, P., Hosseini, S.M.H., & Jolai, F. (2012). A mathematical model and extension algorithm for assembly flexible flow shop scheduling problem. International Journal of Advance Manufacture Technology, DOI 10.1007/s00170-012-4217-x.

Gupta, J.N.D. (1988). Two stage hybrid flowshop scheduling problem. Journal of Operational Research, Society 39 (4), 359–364.

Gaafar, L.K., & Masoud, S.A. (2005). Genetic algorithms and simulated annealing for scheduling in agile manufacturing. International Journal of Production Research, 43(14) 3069-3085.

Hariri, A.M.A., & Potts, C.N. (1997). A branch and bound algorithm for the two-stage assembly scheduling problem. European Journal of Operational Research, 103, 547-556.

Hentsch, K., & Kochel, P. (2011). Job scheduling with forbidden setups and two objectives using genetic algorithms and penalties. Central European Journal of Operations Research, 19, 285-298.

Jin, Zh., Yang, Z., & Ito, T. (2006). Metaheuristic algorithms for the multistage hybrid flowshop scheduling problem, International Journal of Production Economics, 100, 322–334.
Kadipasaoglu, S.N. (1997). A note on scheduling hybrid flow systems. International Journal of Production Research, 35(5), 1491-1494.

Khalouli, S., Ghedjati, F., & Hamzaoui, A. (2010). A meta-heuristic approach to solve a JIT scheduling problem in hybrid flow shop. Engineering Applications of Artificial Intelligence, 23, 765–771.
Koulamas, Ch., & Kyparisis, G. (2001). The three-stage assembly flow shop scheduling problem. Computers & Operations Research, 28, 689-704.

Kumar, S., Bagchi, T.P., & Sriskandarajah, C. (2000). Lot streaming and scheduling heuristics for m-machine no-wait flowshops. Computers & Industrial Engineering, 38, 149-172.

Lee, C.Y., Cheng, T.C.E., & Lin, B.M.T. (1993). Minimizing the makespan in the 3-machine assembly-type flowshop scheduling problem. Management Science, 39, 616-625.

Luo, H., Huang, G.Q., Zhang, Y.F., & Dai, Q.Y. (2011). Hybrid flowshop scheduling with batch-discrete processors and machine maintenance in time windows. International Journal of Production Research, 49(6), 1575-1603.

Maniezzo, V., Stutzle, T., & Vob, S. (2009). Hybridizing Metaheuristics and Mathematical Programming. Springer, London.
Marimuthu, S., Ponnambalam, S.G., & Jawahar, N. (2008). Evolutionary algorithms for scheduling m-machine flow shop with lot streaming. Robotics and Computer-Integrated Manufacturing, 24, 125–139.

Naderi-Beni, M., Tavakkoli-Moghaddam, R., Naderi, B., Ghobadian, E., & Pourrousta, A. (2012). A two-phase fuzzy programming model for a complex bi-objective no-wait flow shop scheduling. International Journal of Industrial Engineering Computations, 3, 617–626.

Pinedo, M.L. (2008). Scheduling. Theory, Algorithms, and Systems. Third Edition. Springer, USA.Potts, C.N., Sevast & apos; Janov, S.V., Strusevich, V.A., Van Wassenhove, L.N., & Zwaneveld, C.M. (1995). The two-stage assembly scheduling problem: Complexity and approximation. Operations Research, 43, 346-355.

Quadt, D., & Kuhn, H. (2007). A taxonomy of flexible flow line scheduling procedures. European Journal of Operational Research, 178, 686-698.

Ribas, I., Leisten, R., & Framinan, J.M. (2010). Review and classification of hybrid flow shop scheduling problems from a production system and a solutions procedure perspective. Computers & Operations Research, 37, 1439–1454.

Ruiz, R., & Vazquez-Rodriguez, J.A. (2010). Invited Review The hybrid flow shop scheduling problem. European Journal of Operational Research, 205, 1-18.

Schneider, U. (2011). A tabu search tutorial based on a real-world scheduling problem. Central European Journal of Operations Research, 19, 467–493.

Sun, X., Morizawa, K., & Nagasawa, H. (2003). Powerful heuristics to minimize makespan in fixed, 3-machine, assembly-type flow shop scheduling. European Journal of Operational Research, 146, 498-516.

Sung, C.S., & Kim, H.Ah. (2008). A two-stage multiple-machine assembly scheduling problem for minimizing sum of completion times. International Journal of Production Economics, 113, 1038-1048.

Tseng, C.T., & Liao, C.J. (2008). A particle swarm optimization algorithm for hybrid flow-shop scheduling with multiprocessor tasks. International Journal of Production Research, 46(17), 4655-4670.

Walter, R. (2011). Comparing the minimum completion times of two longest-first scheduling-heuristics. Central European journal of operations research, doi:10.1007/s10100-011-0217-4.

Yang, J. (2010). A new complexity proof for the two-stage hybrid flow shop scheduling problem with dedicated machines. International Journal of Production Research, 48(5), 1531-1538.

Ying, K.Ch., & Lin, Sh.W. (2006). Multiprocessor task scheduling in multistage hybrid flow-shops: an ant colony system approach. International Journal of Production Research, 44(16), 3161-3177.

Yokoyama, M. (2001). Hybrid flow-shop scheduling with assembly operations. International Journal of Production Economics, 73, 103-116.

Yokoyama, M. (2008). Flow-shop scheduling with setup and assembly operations. European Journal of Operational Research, 187, 1184–1195.

Yokoyama, M., & Santos, D.L. (2005). Three-stage flow-shop scheduling with assembly operations to minimize the weighted sum of product completion times. European Journal of Operational Research, 161, 754-770.