A Bi-Criteria Approach to the M-machine Flowshop Scheduling Problem
Department of Mechanical Engineering, Mepco Schlenk Engineering College
Sivakasi, Tamil Nadu, India
Department of Industrial Engineering, Anna University
Department of Mechanical Engineering, Mepco Schlenk Engineering College
Sivakasi, Tamil Nadu, India
School of Computing and Technology, University of East London
Department of Design and Technology, Loughborough University
Abstract: This paper considers the problem of permutation flowshop scheduling with the objectives of minimising the makespan and total flowtime of jobs, and presents an Improved Genetic Algorithm (IGA). The initial population of the genetic algorithm is created using the popular NEH constructive heuristic (Nawaz et al., 1983). In IGA, multi-crossover operators and multi-mutation operators are applied randomly to subpopulations divided from the original population to enhance the exploring potential and to enrich the diversity of the crossover templates. The performance of the proposed algorithm is demonstrated by applying it to benchmark problems available in the OR-Library. Computation results based on some permutation flowshop scheduling benchmark problems show that the IGA gives better solution when compared with the earlier reported results.
Keywords: Flowshop scheduling, Makespan, Total flowtime, Genetic Algorithm.
Dr. R. Rajkumar is currently Assistant Professor at Mepco Schlenk Engineering college, in the Department of Mechanical Engineering. His areas of specialisation are Operation research, Manufacturing scheduling, Meta-Heuristics, etc. He had his Bachelor degree in Mechanical Engineering and Master Degree in Industrial Engineering from Madurai Kamaraj University and Ph.D from Anna University, Chennai. Dr.R.Rajkumar is grateful to the Management, the Principal and the Head of Mechanical Engineering Department of MEPCO Schlenk Engineering College, Sivakasi, Tamilnadu, India for their support of this paper.
Dr. P. Shahabudeen is currently Professor & Head of Industrial Engineering Department at College of Engineering, Anna University, Chennai, India. His areas of specialisation are Simulation, Optimisation, Information Systems, Design of Manufacturing systems etc. He had his Bachelor degree in Mechanical Engineering from Madurai Kamaraj University Madurai, Master Degree as well as Doctoral degree in Industrial Engineering from Anna University. Currently he is guiding doctoral students in areas like Supply Chain Management, Manufacturing Scheduling, Kanban systems, Taguchi Methods in Manufacturing, E commerce applications etc.
Dr. P. Nagaraj is currently Professor & Head in the Department of Mechanical Engineering, Mepco Schlenk Engineering College, Sivakasi, India. His areas of specialisation are Operation Research, Fuzzy logic, Inventory control etc. He had his Bachelor degree in Mechanical Engineering and Master Degree in Industrial Engineering from Madurai Kamaraj University and Ph.D from Bharathiyar University, Coimbatore, India.
Dr. Subramaniam Arunachalam is a senior lecturer in Manufacturing Systems Engineering in university of East London, UK. He has many years of experience in teaching and developing course materials in manufacturing and operations management disciplines. His fields of research interest include lean concepts, manufacturing systems engineering, strategy and management, quality management, supply chain management, manufacturing simulation, production management, total quality management and project management.
Dr T. Page is a lecturer in Electronic Product Design in the Department of Design and Technology at Loughborough University UK. Tom is an external examiner on Engineering and Manufacturing programmes at Sheffield Halllam University. Dr Page is a visiting scholar at Iceland University and the University of Lapland in Finland and has been an external examiner on undergraduate fields in Product Design and Manufacturing Engineering at the University of East London. Dr Page is co-founder of the European Society for Virtual Reality Learning Environment Research and Development.
CITE THIS PAPER AS:
R. RAJKUMAR, P. SHAHABUDEEN, P. NAGARAJ, S. ARUNACHALAM, T. PAGE, A Bi-Criteria Approach to the M-machine Flowshop Scheduling Problem, Studies in Informatics and Control, ISSN 1220-1766, vol. 18 (4), pp. 127-136, 2009.
1. Introduction and Literature Review
The problem of scheduling in permutation flow shops has been extensively investigated by many researchers. Its aim is to determine the sequence for processing jobs on a given set of machines. The need for scheduling arises from the limited resources available to the decision-maker and it is an important aspect of operational level shop floor decisions. Its importance and relevance to industry has prompted researchers to study it from different perspectives. Flowshop is the classical and most studied manufacturing environment in scheduling literature. A general flowshop in which n jobs to be processed through m machines has been considered. The processing times are fixed and non-negative. Further assumptions are that each job can be processed on only one machine at a time, the operations are not pre-emptable, the jobs are available for processing at time zero and setup times are sequence independent. Here we consider the permutation flowshop shop problem, the same job order is chosen on every machine. The objective then is to find a sequence, i.e., a permutation of the numbers 1,…,n that minimizes the makespan and total flow time. Makespan and total flow-time are two commonly used performance measures in flowshop scheduling literature (Baker, 1974; Garey et al., 1976; Nagar et al., 1995). Flowtime is defined as the time spent by each job in the system and makespan is the time at which the last job completes its processing on the last machine. Minimising makespan is important in situations where a simultaneously received batch of jobs is required to be completed as soon as possible, for example, a multi-item order submitted by a single customer that must be delivered in the minimal possible time. The makespan criterion increases the use of resources. There are other real-life situations in which each completed job is required as soon as it is processed. In such situations, we are interested in minimising the mean or sum of flowtimes of all jobs rather than minimising makespan. This objective is particularly important in real-life situations in which reducing inventory or maintaining cost is of primary concern. We have so far seen the development of various heuristic methods that consider a single measure of performance, viz., makespan. However, the desirability of a schedule being evaluated by more than one performance measure is often cited in the literature. Apart from the makespan objective, other significant objectives in flowshop scheduling problem is the minimisation of total (or mean) flowtime of all jobs.
Optimisation algorithms for the two- and three-machine flowshop problems with respect to different objectives have been developed by Johnson (1954) and Ignall and Schrage (1965). The NP- completeness of various scheduling problems has been discussed widely in the literature (Garey et al., 1976, Pinedo, 2002). As the vast majority of flowshop scheduling problems is NP-complete, research is mostly directed towards the development of heuristic or near-optimal methods. Some of the heuristic procedures developed so far are due to Campbell et al., (1970), Dannenbring (1977), King and Spachis (1980), Nawaz et al., (1983), Widmer and Hertz (1989), Osman and Potts (1989), Ogbu and Smith (1990), Ishibuchi et al., (1995), and Ben-Daya and Al-Fawzan (1998). Nagar et al., (1995) gave a survey of the existing multicriteria approaches of scheduling problems. Nagar et al., (1995) were the first to address the two-machine flowshop problem using the weighted sum of makespan and flow-time criteria.
They presented a branch-and-bound algorithm that works well for special cases. Yeh (1999) developed additional branch-and-bound algorithms for the same problem. For the problem of scheduling in a flowline-based manufacturing cell with missing operations for jobs in a part-family, Logendran and Nudtasomboon (1991), Sridhar and Rajendran (1993) and Ravindran et al. (2005) have proposed heuristics to minimise makespan and total flowtime, respectively.
In this paper an attempt is made to present an efficient Improved Genetic Algorithm (IGA) to solve the Bi-criteria flowshop scheduling problem for minimising makespan and total Flowtime of jobs. As discussed in the literature review, we have identified that among the flowshop scheduling heuristics, the algorithm by Rajendran (1995) and Ravindran et al. (2005) aims at minimising not only makespan, but also total flowtime of jobs. Ravindran et al. (2005) claimed that their heuristic procedure giving better results than Rajendran (1995). Hence in this work, we have chosen to compare the performance of the proposed algorithm IGA with that of Ravindran et al. (2005) algorithm. The proposed algorithm is coded in C and run on a PC Pentium 2.80 GHz under the Windows operating environment. The results of the evaluation of performance of the proposed algorithm and that of Ravindran et al. (2005) are presented for benchmark problems. An extensive experimental investigation has been conducted to relatively evaluate the performances.
This paper has addressed the problem of scheduling in flowshop manufacturing systems with the objective of minimizing makespan and total flowtime. A correct formulation of makespan and total flowtime in a flowshop environment is first presented. Then the Improved Genetic Algorithm approach is highlighted under the multi objective criteria. Finally, the proposed methods are applied to a number of multi machine and multi machine combinations which are available as benchmark problems in OR Library. The results show that Improved Genetic Algorithm gives better result than the results of earlier literature. Further this IGA can be extended to handle other types of objectives like minimizing total tardiness, number of tardy job, machine idle time etc. in various manufacturing environments.
- Baker, K. R. (1974) Introduction to sequencing and scheduling. Wiley, New York.
- Ben-Daya, M. and Al-Fawzan, M. (1998). A tabu search approach for the flow shop scheduling problem. European Journal of Operational Research, Vol. 109, pp. 88-95.
- Biegal J.E. and Davem J.J. (1990), Genetic algorithms and job shop scheduling, Computers and Industrial Engineering Vol. 19, pp. 81-91.
- Campbell, H. G., Dudek, R. A. and Smith, M. L. (1970) A heuristic algorithm for the n-job, m-machine sequencing problem. Management Science, Vol. 16, Part B, pp. 630-637.
- Chen, C. L., Vempati, V. S., and Aljaber, N. (1995), An application of genetic algorithms for flow shop problems, European Journal of Operational Research, Vol. 80, No. 2, pp. 389-396.
- Dannenbring, D. G. (1977), An evaluation of flow-shop sequencing heuristics. Management Science, Vol. 23, pp. 1174-1182.
- Garey M. R., Johnson D. S. and Sethi R. (1976), Complexity of flowshop and jobshop scheduling, Mathematics of Operations Research; Vol.1. pp. 117-129.
- Goldberg, D. E. (1989), Genetic algorithms in search, optimisation and machine learning, Addison Wesley, Reading, MA.
- Goldberg D.E. and Lingle Jr. R. (1985), Alleles, loci and the Travelling Salesman Problem, Proceedings of International Conference on Genetic Algorithms and their Applications, Carnegie-Mellon University, Pittsburgh, PA, pp. 154-159.
- Ignall, E. and Schrage, L. (1965), Application of the branch-and-bound technique to some flowshop scheduling problems, Operations Research. Vol. 13, pp. 400-412.
- Ishibuchi, H., Misaki, S. and Tanaka H. (1995), Modified simulated annealing algorithms for the flow shop sequencing problems. European Journal of Operational Research, Vol. 81, pp. 388-398.
- Johnson, S. M. (1954), Optimal two and three-stage production schedules with setup times included, Nav Res Log Vol. 1, pp. 61-68.
- King, J. R. and Spachis, A. S. (1980), Heuristics for flow-shop scheduling. International Journal of Production Research, Vol. 18, pp. 345-357.
- Leung, Y., Gao, Y. and Xu Z. B. (1997), Degree of population diversity – a perspective on premature convergence in genetic algorithms and its Markov-chain analysis, IEEE Transaction Neural Networks Vol. 8, No. 5, pp. 1165-1176.
- Logendran, R. and Nudtasomboon, N. (1991), Minimising the makespan of a group scheduling problem: a new heuristic. International Journal of Production Research, Vol. 22, pp. 217-230.
- Murata T., Ishibuchi H. and Tanaka H. (1996), Multi-objective genetic algorithm and its application to flowshop scheduling, Computers Ind. Eng., Vol. 30, No. 4, pp. 957-968.
- Nagar, A., Haddock, J. and Heragu, S. (1995), Multiple and bicriteria scheduling: A Literature survey, European Journal of Operational Research Vol. 81, pp. 88-104.
- Nawaz, M., Enscore, E. and Ham, I. (1983), A heuristic algorithm for the m- machine, n- machine flow shop sequencing problem. Omega Vol. 11, No.1, pp. 91-95.
- Neppalli V.R. Chen C.L. and Aljaber N.J. (1994), An effective heuristic for the flow shop problem with weighted tardiness, Proceedings of the Third Industrial Engineering Research Conference, pp. 634-638.
- Ogbu, F. A. and Smith D. K. (1990), The applications of the simulated annealing algorithm to the solution of the n/m/Cmax flowshop problem. Computers and Operations Research Vol. 17. No. 3, pp. 243-253.
- Osman, I. and Potts, C. (1989), Simulated annealing for permutation flow-shop scheduling. OMEGA, The International Journal of Management Science, Vol. 17, No. 6, pp. 551-557.
- Pinedo, M. (2002), Scheduling: Theory, Algorithms, and Systems, Second Edition, Prentice Hall.
- Rajendran C. (1995), Heuristic for scheduling in flow shop with multiple objectives. European Journal of operational Research, Vol. 82: pp. 540-555.
- Ravindran, D., Noorul Haq, A., Selvakumar, S. J. and Sivaraman, R., (2005), Flow shop scheduling with multiple objective of minimising makespan and total flow time. International Journal of Advanced Manufacturing Technology; Vol. 25, pp. 1007-1012.
- Ruben Ruiz, Concepcion Maroto and Javier Alcaraz (2003), New genetic algorithms for the permutation flowshop scheduling problem, Proceedings of the Fifth Metaheuristics International Conference, Kyoto, Japan, August 25-28, pp 63.1-63.8.
- Sridhar, J. and Rajendran, C. (1993), Scheduling in a cellular manufacturing system – a simulated annealing approach. International Journal of Production Research; Vol. 31, pp. 2927-2945.
- Taillard, E. (1993), Benchmarks of basic scheduling problems. European Journal of Operational Research Vol. 64, pp. 278-285.
- Neppalli, V. R., Chen, C-L, and Gupta, J. N. D. (1996), The Two-Stage Bicriteria Flowshop Problem – A Genetic Algorithms Approach, European Journal of Operational Research, Vol. 95, pp. 356-373.
- Vempati V.S., Chen C.L. and Bullington S.F. (1993), An application of genetic algorithms to the Flow Shop Problem, Proceedings of 15th International Conference of Computers and Industrial Engineering.
- Widmer, M. and Hertz, A. (1989), A new heuristic method for the flow shop sequencing problem. European Journal of Operational Research, Vol. 41, No. 2, pp. 186-193.
- Yeh, W. C. (1999), A new branch-and-bound approach for the n/2/flowshop/ αF+βCmax flowshop scheduling problem, Computers and Operations Research, Vol. 26, pp. 1293-1310.
- Yenlay O. (2001), A comparison of the performance between a Genetic Algorithm and the Taguchi method over artificial problems, Turkish Journal of Engineering Environmental Science, Vol. 25, pp. 561-568.