Group Scheduling with Controllable Setup and Processing Times: Minimizing Total Weighted Completion Time |
| |
Authors: | C T Ng T C Edwin Cheng Adam Janiak Mikhail Y Kovalyov |
| |
Institution: | (1) Department of Logistics, The Hong Kong Polytechnic University, Hung Hom, Kowloon, Hong Kong;(2) Institute of Engineering Cybernetics, Wroclaw University of Technology, Janiszewskiego 11/17, 50-372 Wroclaw, Poland;(3) United Institute of Informatics Problems, National Academy of Sciences of Belarus, Surganova 6, 220012 Minsk, Belarus |
| |
Abstract: | The following single machine scheduling problem is studied. A partition of a set of n jobs into g groups on the basis of group technology is given. The machine processes jobs of the same group contiguously, with a sequence
independent setup time preceding the processing of each group. The setup times and the job processing times are controllable
through the allocation of a continuously divisible or discrete resource to them. Each job uses the same amount of the resource.
Each setup also uses the same amount of resource, which may be different from that for the jobs. Polynomial-time algorithms
are constructed for variants of the problem of finding an optimal job sequence and resource values so as to minimize the total
weighted job completion time, subject to given restrictions on resource consumption. The algorithms are based on a polynomial
enumeration of the candidates for an optimal job sequence and solving the problem with a fixed job sequence by linear programming.
This research was supported in part by The Hong Kong Polytechnic University under grant number G-T246 and the Research Grants
Council of Hong Kong under grant number PolyU 5191/01E. In addition, the research of M.Y. Kovalyov was supported by INTAS
under grant number 00-217. |
| |
Keywords: | single machine scheduling group technology total weighted completion time controllable setup and processing times |
本文献已被 SpringerLink 等数据库收录! |
|