Simple matching vs linear assignment in scheduling models with positional effects: a critical review
Rustogi, Kabir and Strusevich, Vitaly A. (2012) Simple matching vs linear assignment in scheduling models with positional effects: a critical review. European Journal of Operational Research, 222 (3). pp. 393-407. ISSN 0377-2217Full text not available from this repository.
This paper addresses scheduling models in which a contribution of an individual job to the objective function is represented by the product of its processing time and a certain positional weight. We review most of the known results in the area and demonstrate that a linear assignment algorithm as part of previously known solution procedures can be replaced by a faster matching algorithm that minimizes a linear form over permutations. Our approach reduces the running time of the resulting algorithms by up to two orders, and carries over to a wider range of models, with more general positional effects. Besides, the same approach works for the models with no prior history of study, e.g., parallel machine scheduling with deterioration and maintenance to minimize total flow time.
|Additional Information:|| First published online: 14 May 2012|
|Uncontrolled Keywords:||scheduling, single machine, parallel machines, positional effects, job deterioration, assignment problem|
|Subjects:||Q Science > QA Mathematics|
|School / Department / Research Groups:||School of Computing & Mathematical Sciences|
|Last Modified:||06 Nov 2012 15:58|
Actions (login required)