Robust and stable scheduling for FJSP under random machine breakdown by use of genetic algorithm and simulation

Document Type : Research Paper

Authors

1 Associate Prof., Department of Industrial Management, Accounting and Management Faculty, Shahid Beheshti University, G.C., Tehran, Iran

2 MSc., Department of Industrial Management, Accounting and Management Faculty, Shahid Beheshti University, G.C., Tehran, Iran

Abstract

Current research addresses finding robust and stable schedule for the flexible job shop problem under machine breakdown. We have used simulation to investigate the effect of machine breakdown. Two-stage of metaheuristic algorithm is developed to generate robust and stable schedule and is integrated with simulation algorithm. Because makespan is primitive objective of every scheduling problem, in the first stage of integrated algorithm, makespan is improved and in the second stage linear combination of stability, robustness and makespan is proposed. In our proposed model we provide condition that scheduler can decide which objective is important than the others, then scheduling scheme can be generated based on this decision. In the second stage, we have investigated four type of coefficient in combination cost function, and our experiment shows that it is possible to achieve high stability and robustness measures without sacrificing much from the makespan level. Genetic and differential evolution algorithms are used in proposed model then a statistical hypothesis test is conducted to compare the performance of them.

Keywords

References

Al-Hinai, N., ElMekkawy, T.Y. (2011a(. An efficient hybridized genetic algorithm architecture for the flexible job-shop scheduling problem. Flexible Services and Manufacturing Journal, 23 (1): 64-85.
Al-Hinai, N., ElMekkawy, T.Y. (2011b). Robust and stable flexible job shop scheduling with random machine breakdowns using a hybrid genetic algorithm. International Journal of  Production Economics, 132 (2): 279-291.
Anglani, A., Grieco, A., Guerriero, E., Musmanno, R., (2005). Robust scheduling of parallel machines with sequence-dependent set-up costs. European Journal of Operational Research, 161 (3):704-720.
Bouyahia, Z., Bellalouna, M., Jaillet, P., Ghedira, K. (2010). A priori parallel machines scheduling. Computers & Industrial Engineering, 58(3): 488-500.
Brandimarte, P. (1993). Routing and scheduling in a flexible job shop by tabu search. Annals of Operations Research, 41(3): 157–183.
Byeon, E., Wu, S.D. and Storer, R.H. (1998). Decomposition heuristics for robust job- shop scheduling. IEEE Transactions on Robotics and Automation, 4 (2): 303-313.
Cheng, R., Gen, M. and Tsujimura, Y. (1996). A tutorial survey of job-shop scheduling problems using genetic algorithms – I. Representation. Computers & Industrial Engineering, 30 (4): 983-997.
Gen, M. & Cheng, R. (2000). Genetic algorithms & engineering optimization, Wiley Series in Engineering Design and Automation, New York: John Wiley & Sons.
Gholami, M., Zandieh, M. (2009). Scheduling a hybrid flow shop with sequence dependent setup times and machines with random breakdowns. Tehran: Shahid Beheshti University. (in Persian)
Ho, N.B., Tay, J.C. & Lai, E. M-K. (2007). An effective architecture for learning and evolving flexible job-shop schedules. European Journal of Operational Research, 179 (2): 316-333.
Holthaus, O. (1999). Scheduling in job shops with machine breakdowns: an experimental study. Computers and Industrial Engineering, 36 (1):137–162.
Hurink, J., Jurisch, B., Thole, M. (1994).  Tabu search for the job shop scheduling problem with multi-purpose machines. Operations Research-Spektrum, 15 (4):  205-215.
Jensen, M.T. (2001b). Improving robustness and flexibility of tardiness and total flow time job shops using robustness measure. Applied Soft Computing, 1 (1): 35-52.
Jensen, M.T. (2003). Generating robust and flexible job shop schedules using genetic algorithms. IEEE Transactions on Evolutionary Computation, 7 (3): 275-288.
Kacem, I., Hammadi, S. & Borne, P. (2002a). Approach by localization and multiobjective evolutionary optimization for flexible job-shop scheduling problems. IEEE Transactions on Systems, Man and Cybernetics, 32 (1): 1-13.
Kouvelis, P., Daniels, R. L. & Vairaktarakis, G. (2000). Robust scheduling of a two machine flow shop with uncertain processing times. IIE Transactions, 32 (5): 421- 432.
Kutanoglu, E. & Wu, S.D. (1998). Improving schedule robustness via stochastic analysis and dynamic adaptation. IMSE Technical Report 98T-001. Available in: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.30.8534& rep= rep1&type=pdf.
Leon, V. J., Wu, S.D. & Storer, R. H. (1994). Robustness measures and robust scheduling for job shops. IIE Transactions, 26 (5): 32-43.
Liu, L., Gu, H., Xi, Y. (2007). Robust and stable scheduling of a single machine with Random machine breakdowns. International Journal of Advanced Manufacturing Technology, 31 (7-8): 645-654.
Mahmoudi, S., Lotfi, S. (2012). Discrete Manufacturing Cuckoo Search algorithm Case study: Graph Coloring Problem. Tabriz: University collage of Nabi Akram. (in Persian)
Matsveichuk, N.M., Sotskov, Yu. N., Egorova, N.G. and Lai, T.C. (2009). Schedule execution for two-machine flow-shop with interval processing times. Mathematical and Computers Modeling, 49 (5-6): 991-1011.
Mattfeld, D.C. (1996). Evolutionary search and the job shop: investigations on genetic algorithms for production scheduling, Germany: Heidelberg: Physica - Verlag.
Mesghouni, K., Hammadi, S., and Borne, P. (1997). Evolution programs for job-shop scheduling. IEEE International Conference on Systems, Man, and Cybernetics, Orlando, Florida, 1: 720-725.
Montemanni, R. (2007). A mixed integer programming formulation for the total flow time single machine robust scheduling problem with interval data. Journal of Mathematical Modeling Algorithms, 6 (2): 287-296.
Policella, N., Cesta, A., Oddi, A. & Smith, S.F. (2005). Schedule robustness through broader solve and robustify search for partial order schedules. Lecture Notes in Artificial Intelligence, 3673: 160-172.
Policella, N., Oddi, A., Smith, S.F. and Cesta, A. (2004). Generating robust partial order schedules. M. Wallace (Ed.): CP 2004, Lecture Notes in Computer Science, 3258: 496-511.
Rangsaritratsamee, R., Ferrell, W.G. & Kurtz, M.B. (2004). Dynamic rescheduling that simultaneously considers efficiency and stability. Computers & Industrial Engineering, 46 (1): 1-15.
Sevaux, M., Sorensen, K. (2004). A genetic algorithm for robust schedules in a one machine environment with ready times and due dates. Quarterly Journal of the Belgian, French and Italian Operations Research Societies, 4OR (2): 129-147.
Shafaei, R. & Brunn, P. (2000). Workshop scheduling using practical (inaccurate) data Part 3: A framework to integrate job releasing, routing and scheduling functions to 139 create a robust predictive schedule. International Journal of Production Research, 38 (1): 85 – 99.
Wei, Q. & Qiaoyun, L. (2009). Solving the flexible job shop scheduling problem based on the adaptive genetic algorithm. 2009 International Forum on Computer Science-Technology and Applications, 1: 97-100.
Industrial Management Journal
Volume 6, Issue 3
Autumn
October 2014
Pages 511-534

Files

Share

How to cite

Statistics