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: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:	Publisher Publisher Organisation
Last Modified:	14 Oct 2016 09:02
URI:	http://gala.gre.ac.uk/id/eprint/1011

Actions (login required)

View Item