Skip navigation

On-line algorithms for single machine scheduling with family setup times

On-line algorithms for single machine scheduling with family setup times

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:
Last Modified: 14 Oct 2016 09:02
Selected for GREAT 2016: None
Selected for GREAT 2017: None
Selected for GREAT 2018: None
URI: http://gala.gre.ac.uk/id/eprint/1011

Actions (login required)

View Item View Item