Parallel Machine Scheduling with Resources Constraint and Sequence Dependent Setup Times
This paper considered the scheduling problem of minimizing makespan on parallel machines with multiple resources constraint and job sequence dependent setup times. We proposed a mixed integer programming model to formulate the problem and used commercial
- PDF / 116,204 Bytes
- 11 Pages / 439.37 x 666.142 pts Page_size
- 21 Downloads / 214 Views
Parallel Machine Scheduling with Resources Constraint and Sequence Dependent Setup Times Zheng-liang Hou and Xiu-ping Guo
Abstract This paper considered the scheduling problem of minimizing makespan on parallel machines with multiple resources constraint and job sequence dependent setup times. We proposed a mixed integer programming model to formulate the problem and used commercial software to get the optimal solution and Gantt chart of a small-size case. Then a Genetic Algorithm (GA) was developed to solve the problem in an acceptable time for large-size cases. Computational experiences shown that the proposed GA can achieve high quality solutions comparable to those obtained by commercial software and outperform the schedule rules existing in real manufacturing operation. Keywords Genetic Algorithm • Makespan • Parallel machine • Resources constraint • Scheduling • Sequence dependent setup times
Introduction In this paper we studied the parallel machine scheduling problem with multiple resources constrain and job sequence dependent setup times (RSPS), which is encountered in many manufacturing environment, such as the semiconductor wafer and final test operation, plastic forming plant and computer operating systems. The RSPS can be formulated as follows. We are given a set N ¼ fJ1 ; J2 ; . . . ; Jn g of jobs that have to be processed on exactly one machine out of a set M ¼ fM1 ; M2 ; . . . ; Mm g of identical parallel machines. The processing time of job Jj is a positive number denoted as pj . There are s 1 types of renewable resources, and or 1 units of resource r ð1 r sÞ are available at Z.-l. Hou • X.-p. Guo (*) Department of Management Science and Engineering, School of Economics and Management, Southwest Jiaotong University, Chengdu, China e-mail: [email protected] R. Dou (ed.), Proceedings of 2012 3rd International Asia Conference on Industrial Engineering and Management Innovation(IEMI2012), DOI 10.1007/978-3-642-33012-4_80, # Springer-Verlag Berlin Heidelberg 2013
801
802
Z.-l. Hou and X.-p. Guo
any time. Job Jj requires qjr units of resource r at any time of its processing and different jobs can be processed simultaneously only when their total consumption of resources does not exceed the resources capacity. Moreover, the setup times between consecutive jobs of different produce type are sequence dependent, that is, stjk can be different from stkj . No machine can process more than one job at a time, that means, the machines considered here are not batch processing machines. Furthermore, we assume that machine breakdown will not happen and no job can be preempted. Normally, the scheduling problem was denoted by a three-field notation α=β=γ, where α describes the machine environment, β indicates the characteristics of job, and γ denotes the optimizing objective. J. Blazewicz et al. gave out a classification scheme resλσρ in β field to specify the resources constraint. Detail description was introduced in Blazewicz et al. (1983). Based on the three-field notation, RSPS can be expressed as Pm
Data Loading...
