Minimizing the number of early jobs on a proportionate flowshop

Abstract

A proportionate flowshop is a special case of the classical flowshop, where the job processing times are machine-independent. We study the problem of minimizing the number of early jobs in this machine setting. This objective function has hardly been investigated on a single machine, and never on a flowshop. We introduce an efficient iterative solution algorithm. In each iteration, a single job is moved to the first position (and is added to the set of early jobs), and the remaining jobs are rescheduled such that the maximum earliness is minimized. The algorithm guarantees an optimal solution in O(n³) time, where n is the number of jobs.

Keywords:

• scheduling
• proportionate flowshop
• number of early jobs

Acknowledgements

This research was supported by the Israel Science Foundation (grant No. 1286/14). The second author was supported in part by the Recanati Fund of The School of Business Administration, and Charles I. Rosen Chair of Management, The Hebrew University, Jerusalem, Israel.