Scheduling unit processing time jobs on an m-machine flow-shop

Abstract

The sequential production of identical jobs and the flow-shop machine setting are extremely common in real-life applications. We study a scheduling problem that combines these two elements: jobs of identical processing time, with job-dependent weights, and a given common due date processed on an m-machine flow-shop. The (just-in-time) objective is to minimize the maximum earliness/tardiness cost. We introduce a polynomial time solution in both cases of (i) a non-restrictive (ie, sufficiently large) due date, and (ii) a restrictive due date (which restricts the number of early jobs).

Keywords:

• scheduling
• flow-shop
• just-in-time

Acknowledgements

This paper was supported in part by the Recanati Fund of The School of Business Administration, The Hebrew University, Jerusalem, Israel.