A New Approach Generating Robust and Stable Schedules in m-Machine Flow Shop Scheduling Problems: A Case Study

Document Type : Original Article


1 Department of Industrial Engineering, College of Engineering, Shahed University, Tehran, Iran

2 Department of Industrial Engineering, K.N. Toosi University of Technology, Tehran, Iran


This paper considers a scheduling problem with uncertain processing times and machine breakdowns in industriall/office workplaces and solves it via a novel robust optimization method. In the traditional robust optimization, the solution robustness is maintained only for a specific set of scenarios, which may worsen the situation  for new scenarios. Thus, a two-stage predictive algorithm is proposed to efficiently handle the uncertainties and find robust and stable solutions. The first stage creates robust solutions and ensures their stability in the new scenarios. The second stage proposes a novel stability measure to proactively offset the effects of the machine breakdowns of the former stage. Moreover, a tri-component measure based on efficiency, robustness, and stability is proposed which aims to create a realistic schedule to satisfy the customers, manufacturers, and the staff. To meet the customer’s requirements, the robustness measure is defined based on the tardiness and the delivery dates of jobs. Finally, the proposed algorithm is applied to a case study, and the findings are compared with the empirical data. The results emphasize the superiority of the proposed technique in satisfying the customers, staff, and increasing the profitability and accountability of the company.


1. Rahmani, D., “A new proactive-reactive approach to hedge
against uncertain processing times and unexpected machine 
failures in the two-machine flow shop scheduling problems”,
Scientia Iranica, Vol. 24, No. 3, (2017), 1571–1584.  
2. Goren, S. and Sabuncuoglu, I., “Optimization of schedule
robustness and stability under random machine breakdowns and
processing time variability”, IIE Transactions (Institute of
Industrial Engineers), Vol. 42, No. 3, (2010), 203–220.  
3. Al-Hinai, N. and Elmekkawy, T.Y., “Robust and stable flexible
job shop scheduling with random machine breakdowns using a
hybrid genetic algorithm”, International Journal of Production
Economics, Vol. 132, No. 2, (2011), 279–291.  
4. Mehta, S. V. and Uzsoy, R. M., “Predictable scheduling of a job
shop subject to breakdowns”, IEEE Transactions on Robotics
and Automation, Vol. 14, No. 3, (1998), 365–378.  
5. Gören, S., “Robustness and stability measures for scheduling
policies in a single machine environment”, Doctoral dissertation,
Bilkent University, Turkey, (2002) 
6. Fazayeli, M., Aleagha, M.R., Bashirzadeh, R. and Shafaei, R., “A
hybrid meta-heuristic algorithm for flowshop robust scheduling
under machine breakdown uncertainty”, International Journal of
Computer Integrated Manufacturing, Vol. 29, No. 7, (2016),
7. Nouiri, M., Bekrar, A., Jemai, A., Trentesaux, D., Ammari, A.C.
and Niar, S., “Two stage particle swarm optimization to solve the
flexible job shop predictive scheduling problem considering
possible machine breakdowns”, Computers and Industrial
Engineering, Vol. 112, (2017), 595–606.  
8. González-Neira, E.M., Montoya-Torres, J.R., and Barrera, D.,
“Flow-shop scheduling problem under uncertainties: Review and
trends”, International Journal of Industrial Engineering
Computations, Vol. 8, No. 4, (2017), 399–426.  
9. Liao, W. and Fu, Y., “Min–max regret criterion-based robust
model for the permutation flow-shop scheduling problem”,
Engineering Optimization, (2019), 1–14.  
10. Framinan, J.M., Fernandez-Viagas, V. and Perez-Gonzalez, P.,
“Using real-time information to reschedule jobs in a flowshop
with variable processing times”, Computers and Industrial
Engineering, Vol. 129, (2019), 113–125.  
11. Ma, S., Wang, Y. and Li, M., “A Novel Artificial Bee Colony
Algorithm for Robust Permutation Flowshop Scheduling”, In
Natural Computing for Unsupervised Learning, Springer, Cham,
(2019), 163–182. 
12. Amirian, H. and Sahraeian, R., “Multi-objective Differential
Evolution for the Flow Shop Scheduling Problem with a Modified
Learning Effect”, International Journal of Engineering,
Transactions C: Aspects, Vol. 27, No. 9, (2014), 1395–1404.  
13. Mokhtari, H., Molla-Alizadeh, S. and Noroozi, A., “A Reliability
based Modelling and Optimization of an Integrated Production
and Preventive Maintenance Activities in Flowshop Scheduling
Problem”, International Journal of Engineering - Transactions
C: Aspects, Vol. 28, No. 12, (2015), 1774–1781.  
14. Tavakkoli-Moghaddam, R., Lotfi, M.M., Khademi Zare, H. and
Jafari, A. A., “Minimizing Makespan with Start Time Dependent
Jobs in a Two Machine Flow Shop”, International Journal of
Engineering - Transactions C: Aspects, Vol. 29, No. 6, (2016),
15. Kouvelis, P., Daniels, R.L., and Vairaktarakis, G., “Robust
scheduling of a two-machine flow shop with uncertain processing
times”, IIE Transactions (Institute of Industrial Engineers),
Vol. 32, No. 5, (2000), 421–432.  
16. Rahmani, D. and Heydari, M., “Robust and stable flow shop
scheduling with unexpected arrivals of new jobs and uncertain
processing times”, Journal of Manufacturing Systems, Vol. 33,
No. 1, (2014), 84–92.  
17. Cui, W., Lu, Z., Li, C. and Han, X., “A proactive approach to
solve integrated production scheduling and maintenance planning