1. Scheduling with controllable release dates and processing times: Total completion time minimization
- Author
-
Cheng, T.C. Edwin, Kovalyov, Mikhail Y., and Shakhlevich, Natalia V.
- Subjects
Machinery ,Magneto-electric machines ,Algorithms ,Universities and colleges ,Algorithm ,Business ,Business, general ,Business, international - Abstract
To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.ejor.2005.06.072 Byline: T.C. Edwin Cheng (a), Mikhail Y. Kovalyov (b), Natalia V. Shakhlevich (c) Keywords: Scheduling; Single machine; Parallel machines; Total completion time; Controllable processing times; Controllable release dates; Due-date scheduling Abstract: The single machine scheduling problem with two types of controllable parameters, job processing times and release dates, is studied. It is assumed that the cost of compressing processing times and release dates from their initial values is a linear function of the compression amounts. The objective is to minimize the sum of the total completion time of the jobs and the total compression cost. For the problem with equal release date compression costs we construct a reduction to the assignment problem. We demonstrate that if in addition the jobs have equal processing time compression costs, then it can be solved in O(n.sup.2) time. The solution algorithm can be considered as a generalization of the algorithm that minimizes the makespan and total compression cost. The generalized version of the algorithm is also applicable to the problem with parallel machines and to a range of due-date scheduling problems with controllable processing times. Author Affiliation: (a) Department of Logistics, The Hong Kong Polytechnic University, Hung Hom, Kowloon, Hong Kong (b) Faculty of Economics, Belarus State University, and United Institute of Informatics Problems, National Academy of Sciences of Belarus, Nezavisimosti 4, 220030 Minsk, Belarus (c) School of Computing, University of Leeds, Leeds LS2 9JT, UK Article History: Received 27 April 2004; Accepted 1 June 2005 Article Note: (footnote) [star] This research was supported in part by The Hong Kong Polytechnic University under a grant from the Area of Strategic Development in China Business Services. The research of the second and third authors was additionally supported by INTAS (Project INTAS-96-0820).
- Published
- 2006