# 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)

## 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 |