On-line algorithms for single machine scheduling with family setup times
Tools
Tools
Potts, Chris N., Strusevich, Vitaly A. and Whitehead, Jonathan D. (2006) On-line algorithms for single machine scheduling with family setup times. In: 12th IFAC Symposium on Information Control Problems in Manufacturing, 2006 [Proceedings]. Information Control Problems in Manufacturing (12:1). International Federation of Automatic Control, Laxenburg, Austria, pp. 135-141. ISBN 9783902661043 (doi:https://doi.org/10.3182/20060517-3-FR-2903.00084)
Full text not available from this repository.Abstract
The paper considers an on-line single machine scheduling problem where the goal is to minimize the makespan. The jobs are partitioned into families and a setup is performed every time the machine starts processing a batch of jobs of the same family. The scheduler is aware of the number of families and knows the setup time of each family, although information about a job only becomes available when that job is released. We give a lower bound on the competitive ratio of any on-line algorithm. Moreover, for the case of two families, we provide an algorithm with a competitive ratio that achieves this lower bound. As the number of families increases, the lower bound approaches 2, and we give a simple algorithm with a competitive ratio of 2.
| Item Type: | Conference Proceedings |
|---|---|
| Title of Proceedings: | 12th IFAC Symposium on Information Control Problems in Manufacturing, 2006 [Proceedings] |
| Additional Information: | [1] This paper was first presented at the 12th IFAC Symposium on Information Control Problems in Manufacturing, 2006 held from 17-19 May 2006 in Saint-Etienne, France. |
| Uncontrolled Keywords: | scheduling algorithms, batch,on-line, analytic approximations |
| Subjects: | Q Science > QA Mathematics Q Science > QA Mathematics > QA76 Computer software |
| Pre-2014 Departments: | School of Computing & Mathematical Sciences School of Computing & Mathematical Sciences > Department of Mathematical Sciences School of Computing & Mathematical Sciences > Statistics & Operational Research Group |
| Related URLs: | |
| Last Modified: | 14 Oct 2016 09:02 |
| URI: | http://gala.gre.ac.uk/id/eprint/1011 |
Actions (login required)
 |
View Item |