Volume 18-Issue2-2009-RAJKUMAR

R. RAJKUMAR
Department of Mechanical Engineering, Mepco Schlenk Engineering College
Sivakasi, Tamil Nadu, India
Corresponding author

P. SHAHABUDEEN
Department of Industrial Engineering, Anna University
Chennai, India

P. NAGARAJ
Department of Mechanical Engineering, Mepco Schlenk Engineering College
Sivakasi, Tamil Nadu, India

S. ARUNACHALAM
School of Computing and Technology, University of East London
London

T. PAGE
Department of Design and Technology, Loughborough University
Loughborough, UK

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.

>Full text
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 (2), 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.