Permutation Flowshop Scheduling with Earliness and Tardiness Penalties

Abstract

We address the permutation flowshop scheduling problem with earliness and tardiness penalties (E/T) and common due date of jobs. Large number of process and discrete parts industries follow flowshop type of production process. There are very few results reported for multi-machine E/T scheduling problems. We show that the problem can be sub-divided into three groups- one, where the due date is such that all jobs are necessarily tardy; the second, where the due date is such that it is not tight enough to act as a constraint on scheduling decision; and the third is a group of problems where the due date is in between the above two. We develop analytical results and heuristics for problems arising in each of these three classes. Computational results of the heuristics are reported. Most of the problems in this research are addressed for the first time in the literature. For problems with existing heuristics, the heuristic solution is found to perform better than the existing results.