Multi-Objective Flow Shop Production Scheduling Via Robust Genetic Algorithms Optimization Technique
[1]
Ghorbanali Mohammadi, Industrial Engineering Department, College of Engineering, Qom University of Technology, Qom, Iran.
Production scheduling is generally considered to be the one of the most significant issue in the planning and operation of a manufacturing system. Better scheduling system has significant impact on cost reduction, increased productivity, customer satisfaction and overall competitive advantage. This paper discusses the application of Robust Genetic Algorithm to solve a flow-shop scheduling problem. Multi-objective flow shop scheduling with sequence dependent set up time also becomes NP hard with greater complexity toward optimality in a reasonable time. To tackle the complexity of the problem at hand, we propose an approach base on genetic algorithm (GA). However, the performance of most evolutionary algorithms is significantly impressed by the values determined for the miscellaneous parameters which these algorithms possess. Hence, response surface methodology is applied to set the parameters of GA and to estimate the proper values of GA parameters in continually intervals. Finally, problems of various sizes are utilized to test the performance of the proposed algorithm and to compare it with some existing heuristic in the literature such as LPT, SPT, EDD and NEH.
Flow Shop, Scheduling, Multi-Objectives, Sequence-Dependent Setup Times, GA
[1]
Carlier, J. and Rebai, I. (1996). Two branch and bound algorithms for the permutation flow shop problem. European Journal of Operational Research. 90, 238–251.
[2]
Dulluri, S., Mahesh, V. and Rao, C.S.P. (2008). A heuristic for priority-based scheduling in a turbine manufacturing job-shop. International Journal of Industrial and Systems Engineering, 3(6), 625 – 643.
[3]
Della Croce, F., Tadei, R., & Volta, G. (1995). A genetic algorithm for the job shop problem. Computers & Operations Research. 22(1), 15–24.
[4]
Eren, T. (20100 . A Bicriteria M-Machine Flowshop Scheduling with Sequence- Dependent Setup Times. Applied Mathematical Modelling . 34(2), 284 - 293.
[5]
French, S. (1982). Sequencing and Scheduling: An Introduction to the Mathematics of the Job-Shop. Ellis Horwood Limited.
[6]
Garey, M.R., Johnson, D.S. and Sethi, R.R., 1976. The complexity of flow shop and Job shop scheduling.. Operations Research. 1,117–129.
[7]
Gonzalez, T. and Sen, T. (1978). Flow shop and job shop schedules: complexity and approximations. Operations Research. 26, 36–52.
[8]
Goldberg, D.E., 1989. Genetic algorithms in search, optimization and machine learning. Addison-Wesley, Reading, MA.
[9]
Giffler, J., & Thompson, G. L. (1960). Algorithms for solving production scheduling problems. Operations Research. 8(4), 487–503.
[10]
Java Developers Journal webpage. (2007). An Introduction to Genetic Algorithms in Java (Harnessing the power of evolution’s optimization algorithm), retrieved 1/ 20/2007. Available from .
[11]
Kalczyncski, P.J. and Kamburowski, J. (2005). A heuristic for minimizing the makespan in no-idle permutation flow shops. Computers and Industrial Engineering. 49, 146–154.
[12]
Kim, Y.D. (1995) . Minimizing total tardiness in permutation flow shops. European Journal of Operational Research 85, 541–55.
[13]
Luo, X. and Chu, C. (2007). A branch-and-bound algorithm of the single machine schedule with sequence dependent setup times for minimizing maximum tardiness. European Journal of Operational Research. 180, 68–81.
[14]
Lee, G.C. and Kim, Y.D. (2004). A branch and bound algorithm for a two-stage hybrid flow shop scheduling problem minimizing total tardiness. International Journal of Production Research. 42(22), 4731 – 4743.
[15]
Marian, R., Luong, L., & Abhary, K. (2006). A genetic algorithm for the optimization of assembly sequences. Computers & Industrial Engineering,.50(4), 503–527.
[16]
Manikas, A., & Chang, Y. L. (2005). Using a genetic algorithm to solve the sequence dependent job shop scheduling problem. In Proceedings of INFORMS SE 2005, Myrtle Beach, South Carolina.
[17]
Miller, D., Chen, H.-C., Matson, J., & Liu, O. (1999). A hybrid genetic algorithm for the single machine scheduling problem. Journal of Heuristics. 5(4), 437–454.
[18]
Naderi, B., Zandieh, M., Balagh, K.K.G. and Roshanaei, V. (2009A). An improved simulated annealing for hybrid flow shops with sequence-dependent setup and transportation times to minimize total completion time and total tardiness. Expert Systems with Applications: an International Journa.l 36(6), 9625-9633.
[19]
Naderi, B., Zandieh, M., Balagh, K.K.G. and Roshanaei, V. (2009B). Scheduling hybrid flowshops with sequence dependent setup times to minimize makespan and maximum tardiness. International Journal of Advanced Manufacturing Technology. 41, 1186–1198.
[20]
Nawaz M., Enscore E. and Ham I. (1983). A heuristic algorithm for the m-machine n-job flow shop sequencing problem. Omega 11, 91–95.
[21]
Pinedo, M. (2005). Scheduling theory, algorithms, and system, (Prentice-Hall).
[22]
Park, B. J., Choi, H. R., & Kim, H. S. (2003). A hybrid genetic algorithm for the job shop scheduling problems. Computers & Industrial Engineering, 45, 597–613.
[23]
Ronconi, D. P. (2004). A note on constructive heuristics for the flow shop problem with blocking. International Journal of Production Economics. 87, 39–48.
[24]
Pasupathy, T., Rajendran, C. and Suresh, R.K. (2006). Multi-objective genetic algorithm for scheduling in flow shops to minimize the makespan and total flow time of jobs. International Journal of Advanced Manufacturing Technology. 27, 804–815.
[25]
Ruiz, R., Sivrikay Serifoglu, F.,&Urlings, T. (2006). Modeling realistic hybrid flexible flowshop scheduling problems. Computers & Operations Research, 35(4), 1151–1175. doi:10.1016/j.cor.2006.07.014.
[26]
Rajendran, C. and Chaudhuri, D. 91992 0. An efficient heuristic approach to the scheduling of jobs in a flow-shop. European Journal of Operational Research. 61, 318– 325.
[27]
Ravindran, D., Noorul Haq, A., Selvakumar, S. J. and Sivaraman, R.. (2005). Flow shop scheduling with multiple objective of minimizing makespan and total flow time. International Journal of Advanced Manufacturing Technology. 25, 1007–1012.
[28]
Taillard, E., 1993. Benchmarks of basic scheduling problems. European Journal of Operation Research .64, 278– 285.
[29]
Tang, L., Liu, J. and Liu, W. (2005). A neural network model and algorithm for the hybrid flow shop scheduling problem in a dynamic environment. Journal of Intelligent Manufacturing .16, 361–370.
