On the Solution of 2-Machine Flow Shop Problems With a Common Due Date

What is it about?

We study two machine flow shop problems with earliness and tardiness penalties and a common due date. For a job-independent penalty function with some reasonable monotonicity features, we present an enumerative algorithm with branch and bound components. The algorithm can solve problems with up to 20 jobs. Additionally, a beam search algorithm derived from the exact algorithm and two local search heuristics are discussed.

Featured Image