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-2217 (doi:https://doi.org/10.1016/j.ejor.2012.04.037)

Full text not available from this repository.

Abstract

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.

Item Type:	Article
Additional Information:	[1] First published online: 14 May 2012. [2] Published in print: 1 November 2012
Uncontrolled Keywords:	scheduling, single machine, parallel machines, positional effects, job deterioration, assignment problem
Subjects:	Q Science > QA Mathematics
Pre-2014 Departments:	School of Computing & Mathematical Sciences
Related URLs:	Publisher
Last Modified:	14 Oct 2016 09:22
URI:	http://gala.gre.ac.uk/id/eprint/9024

Actions (login required)

View Item