Sequencing with setup time and order tardiness trade-offs

The authors consider the problem of scheduling customer orders on a single facility where each order consists of several jobs that can be clustered into several groups. When a facility is changed over to another group, a setup time associated with the new group is required. Two particular problems are considered in this context. One is to consider the total setup time and the number of tardy orders jointly. The other is to consider the total setup time and the maximum tardiness jointly. The total setup time in both problems represents a measure of internal efficiency, whereas the number of tardy orders and the maximum tardiness represent a measure of external efficiency. In any shop, the decision maker must consider the trade-offs between large setup costs associated with a more frequent changeover schedule versus the cost of tardy orders that might be induced by a less-frequent changeover schedule. In this article branch-and-bound algorithms are proposed to identify the set of nondominated schedules for the two bicriteria problems.