Search

We study the use of flow‐based algorithmic and proof techniques applied to preemptive scheduling of jobs on parallel identical machines. For the classical problem in which the jobs have individual release dates and must be finished by a common deadline, we present and prove unified necessary and sufficient conditions for the existence of a feasible schedule by examining the structure of minimum cuts in a special network. We then study an enhanced model that allows the presence of additional resources, provided that some jobs at any time of their processing require one unit of a particular resource. We extend our argument developed for the classical case to this enhanced model. The generalized necessary and sufficient conditions for the existence of a feasible schedule are presented and proved using the max‐flow/min‐cut reasoning. [ABSTRACT FROM AUTHOR]

Abstract. In this paper, we propose a new methodology for the speed-scaling problem based on its link to scheduling with controllable processing times and submodular optimization. It results in faster [...]

In this paper, we study a scheduling problem on a single machine, provided that the jobs have individual release dates and deadlines, and the processing times are controllable. The objective [...]

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).

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.ejor.2005.06.021 Byline: T.C. Edwin Cheng (a), Mikhail Y. Kovalyov (b), Natalia V. Shakhlevich (c) Keywords: Scheduling; Single-machine; Makespan; Controllable processing times; Controllable release dates Abstract: The paper deals with the single-machine scheduling problem in which job processing times as well as release dates are controllable parameters and they may vary within given intervals. While all release dates have the same boundary values, the processing time intervals are arbitrary. It is assumed that the cost of compressing processing times and release dates from their initial values is a linear function of the compression amount. The objective is to minimize the makespan together with the total compression cost. We construct a reduction to the assignment problem for the case of equal release date compression costs and develop an O(n.sup.2) algorithm for the case of equal release date compression costs and equal processing time compression costs. For the bicriteria version of the latter problem with agreeable processing times, we suggest an O(n.sup.2) algorithm that constructs the breakpoints of the efficient frontier. 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, Skorini 4, 220050 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).

A polyhedron scheduling process for unit time operations of parallel machines and open shop machine problems is constructed. This process aims at minimizing non-decreasing separable objective function of time taken for completing jobs.

In this paper, we study a scheduling problem on a single machine, provided that the jobs have individual release dates and deadlines, and the processing times are controllable. The objective is to find a feasible schedule that minimizes the total cost of reducing the processing times. We reformulate the problem in terms of maximizing a linear function over a submodular polyhedron intersected with a box. For the latter problem of submodular optimization, we develop a recursive decomposition algorithm and apply it to solving the single machine scheduling problem to achieve the best possible running time. [ABSTRACT FROM AUTHOR]