Design of a genetic algorithm for bi-objective unrelated parallel machines scheduling with sequence-dependent setup times and precedence constraints

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.cor.2009.02.012 Byline: R. Tavakkoli-Moghaddam (a), F. Taheri (b), M. Bazzazi (b), M. Izadi (c), F. Sassani (d) Abstract: This paper presents a novel, two-level mixed-integer programming model of scheduling N jobs on M parallel machines that minimizes bi-objectives, namely the number of tardy jobs and the total completion time of all the jobs. The proposed model considers unrelated parallel machines. The jobs have non-identical due dates and ready times, and there are some precedence relations between them. Furthermore, sequence-dependent setup times, which are included in the proposed model, may be different for each machine depending on their characteristics. Obtaining an optimal solution for this type of complex, large-sized problem in reasonable computational time using traditional approaches or optimization tools is extremely difficult. This paper proposes an efficient genetic algorithm (GA) to solve the bi-objective parallel machine scheduling problem. The performance of the presented model and the proposed GA is verified by a number of numerical experiments. The related results show the effectiveness of the proposed model and GA for small and large-sized problems. Author Affiliation: (a) Department of Industrial Engineering, College of Engineering, University of Tehran, Tehran, Iran (b) Department of Industrial Engineering, Mazandaran University of Science and Technology, Babol, Iran (c) Department of Computer Engineering and IT, Amirkabir University of Technology, Tehran, Iran (d) Department of Mechanical Engineering, The University of British Columbia, Vancouver, Canada