# Proportionate flow shop with controllable processing times

Cheng, T.C. Edwin and Shakhlevich, Natalia
(1999)
*Proportionate flow shop with controllable processing times.*
Journal of Scheduling, 2 (6).
pp. 253-265.
ISSN 1094-6136 (Print), 1099-1425 (Online)
(doi:10.1002/(SICI)1099-1425(199911/12)2:6<253::AID-JOS30>3.0.CO;2-R)

## Abstract

This paper considers a special class of flow-shop problems, known as the proportionate flow shop. In such a shop, each job flows through the machines in the same order and has equal processing times on the machines. The processing times of different jobs may be different. It is assumed that all operations of a job may be compressed by the same amount which will incur an additional cost. The objective is to minimize the makespan of the schedule together with a compression cost function which is non-decreasing with respect to the amount of compression. For a bicriterion problem of minimizing the makespan and a linear cost function, an O(n log n) algorithm is developed to construct the Pareto optimal set. For a single criterion problem, an O(n2) algorithm is developed to minimize the sum of the makespan and compression cost. Copyright © 1999 John Wiley & Sons, Ltd.

Item Type: | Article |
---|---|

Uncontrolled Keywords: | flowshop scheduling, controllable processing times, multiple criteria |

Subjects: | Q Science > QA Mathematics |

Pre-2014 Departments: | School of Computing & Mathematical Sciences |

Related URLs: | |

Last Modified: | 14 Oct 2016 09:00 |

URI: | http://gala.gre.ac.uk/id/eprint/492 |

### Actions (login required)

View Item |