Phase 1: Assess attractiveness of additional setups

• 0) Let j denote a period index, let p( j) be the most recent production period prior to and including period j, and let s( j) be the next setup after period j. If no production period exists prior to and including j, set p( j) = 0. Set j = T and s( j) = T + 1 and let X _j denote the total planned production (in the current, possibly capacity-infeasible solution) for period j.

• 1) Determine the most recent setup p( j) as described in Step 0. If p( j) = 0, go to Phase II. If X _{p( j)} ? C _{p( j)}, set s( p( j) ? 1) = p( j) and j = p( j) 1 and repeat Step 1 (note that we maintain s( j) = j + 1). Otherwise, continue.

• 2) Compare the desired production in period p( j), X _{p( j)}, with actual capacities over the next s( j) ? p( j) periods. If X _{p( j)} > ? ^{s( j) ?1} _{t =p(j)} C _t, and the sum of the revenues for all selected orders for...