Modeling the Hybrid Flow Shop Scheduling Problem Followed by an Assembly Stage Considering Aging Effects and Preventive Maintenance Activities

Document Type: Research Paper


Industrial Engineering and Management Department, Shahrood University of Thechnology, Shahrood, Iran


Scheduling problem for the hybrid flow shop scheduling problem (HFSP) followed by an assembly stage considering aging effects additional preventive and maintenance activities is studied in this paper. In this production system, a number of products of different kinds are produced. Each product is assembled with a set of several parts. The first stage is a hybrid flow shop to produce parts. All machines can process all kinds of parts in this stage but each machine can process only one part at the same time. The second stage is a single assembly machine or a single assembly team of workers. The aim is to schedule the parts on the machines and assembly sequence and also determine when the preventive maintenance activities get done in order to minimize the completion time of all products (makespan). A mathematical modeling is presented and its validation is shown by solving an example in small scale. Since this problem has been proved strongly NP-hard, in order to solve the problem in medium and large scale, four heuristic algorithms is proposed based on the Johnson’s algorithm. The numerical experiments are used to run the mathematical model and evaluate the performance of the proposed algorithms.


Main Subjects

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

A. Bachman, A. Janiak. (2004) Scheduling jobs with position-dependent processing times. Journal of Operational Research Society. Vol. 55, pp. 257-264.

A. Berrichi, L. Amodeo, F. Yalaoui, E. Chatelet, M. Mezghiche. (2008) Bi-objective optimization algorithms for joint production and maintenance scheduling: Application to the parallel machine problem. Journal of Intelligent Manufacturing. Vol. 20, pp. 389–400.

AMA. Hariri, CN. Potts, (1997) A branch and bound algorithm for the two-stage assembly scheduling problem. European Journal of Operational Research. Vol. 103, pp. 547-556.

B. Alidaee, N.K. Womer. (1999) Scheduling with time dependent processing times: review and extensions. Journal of the Operational Research Society. Vol. 50, pp. 711-720.

C. Oguz, MF. Ercan, TCE. Cheng, YF. Fung. (2003) Heuristic algorithms for multiprocessor task scheduling in a two-stage hybrid flow-shop. European Journal of Operational Research. Vol. 149, pp. 390-403.

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

Ch. Koulamas, GJ. Kyparisis. (2001) The three-stage assembly flow shop scheduling problem. Computers & Operations Research, Vol. 28,  pp. 689-704.

CN. Potts, SV. Sevast'Janov, VA. Strusevich, LN. Van Wassenhove, CM. Zwaneveld. (1995) The two-stage assembly scheduling problem: Complexity and approximation. Operations Research. Vol. 43, pp. 346-355. 

CY. Lee, TCE. Cheng, BMT. Lin. (1993) Minimizing the makespan in the 3-machine assembly-type flowshop scheduling problem. Management Science, Vol. 39, pp. 616-25.

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

D. Yang, TCE. Cheng, S. Yang, Ch. Hsu. (2012) Unrelated parallel-machine scheduling with aging effects and multi-maintenance activities. Computers & Operations Research. Vol. 39, pp. 1458-1464.

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

G. Mosheiov. (2001) Parallel machine scheduling with a learning effect. Operational Research Society. Vol. 52, pp. 1165-1169.

G. Schmidt. (2000) Scheduling with limited machine availability, European Journal of Operational Research. Vol. 121, pp. 1-15.

H. Chou-Jung Hsu. (2013) Single-Machine Scheduling with Aging Effects and Optional Maintenance Activity Considerations. Mathematical Problems in Engineering. DOI: 10.1155/2013/634503.

H. Mokhtari, M. Dadgar. (2015) A Flexible Job Shop Scheduling Problem with Controllable Processing Times to Optimize Total Cost of Delay and Processing. International Journal of Supply and Operations Management. Vol. 2(3), pp. 871-887.

J. Blazewicz, K. EckeK, E. Pesch, G. Schmidt, J. Weglarz. Handbook on Scheduling from Theory to Application. Springer, USA, 2007.

M. Elbounjimi, G. Abdul-Nour, D. Ait-Kadi. (2015) A collocation-based approach to designing remanufacturing closed–loop supply chain network. International Journal of Supply and Operations Management. Vol. 2(3), pp. 820-832.

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

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

ML. Pinedo. Scheduling Theory, Algorithms, and Systems. Third Edition. Springer, USA, 2008.

TCE. Cheng, G. Wang. (1999) Scheduling the fabrication and assembly of components in a two-machine flow shop. IIE Transactions. Vol. 31, pp. 135-143.

P. Fattahi, SMH. Hosseini, F. Jolai, R. Tavakoli-Moghadam. (2014) A branch and bound algorithm for hybrid flow shop scheduling 4 problem with setup time and assembly operations. Applied Mathematical Modelling. Vol. 38, pp. 119-134.

P. Fattahi, SMH. Hosseini, F. Jolai. (2013) A mathematical model and extension algorithm for assembly flexible flow shop scheduling problem. International journal of advanced manufacturing technology. Vol. 65, pp. 787–802.

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

T.C.E. Cheng, O. Ding, B.M.T. Lin. (2004) A concise survey of scheduling with time-dependent processing times. European Journal of Operational Research. Vol. 152, pp. 1-13.

Y. Ma, C. Chu, C. Zuo A survey of scheduling with deterministic machine availability constraints. Computers & Industrial Engineering