Scheduling linearly shortening jobs under precedence constraints |
| |
Authors: | Stanisław Gawiejnowicz Tsung-Chyan Lai Ming-Huang Chiang |
| |
Institution: | 1. Adam Mickiewicz University, Faculty of Mathematics and Computer Science, Umultowska 87, 61-614 Poznań, Poland;2. National Taiwan University, College of Management #2, Roosevelt Road 85, Section 4, Taipei 106, Taiwan |
| |
Abstract: | We consider the problem of scheduling a set of dependent jobs on a single machine with the maximum completion time criterion. The processing time of each job is variable and decreases linearly with respect to the starting time of the job. Applying a uniform approach based on the calculation of ratios of expressions that describe total processing times of chains of jobs, we show basic properties of the problem. On the basis of these properties, we prove that if precedence constraints among jobs are in the form of a set of chains, a tree, a forest or a series–parallel digraph, the problem can be solved in O(n log n) time, where n denotes the number of the jobs. |
| |
Keywords: | Time-dependent scheduling Shortening jobs Precedence constraints Polynomial algorithms |
本文献已被 ScienceDirect 等数据库收录! |
|