Tool- and setup-constrained capacity -allocation problem with assignment restrictions

We address a shift-level production planning problem motivated by applications in the semiconductor industry. A number of jobs must be allocated among a number of non-identical parallel machines subject to constraints due to operational policy and resource requirements. The operational policy constraints are due to management policies, such as limiting the number of different setups on a machine during a shift. The resource constraints are due to the limited availability of secondary resources such as tooling needed to process a job at a machine. The objective is to assign the jobs to the machines in a manner that maximizes the total throughput of the machines, i.e., the total number of jobs processed over the planning horizon. We follow the approach of several industrial practitioners in decomposing this problem into two separate problems, that of allocating the work to the workcenters and that of sequencing the jobs on the individual machines, and focus our attention on the former. We first examine the computational complexity of this problem, relating it to a number of other problems in the literature and resolving the complexity of two open cases. After demonstrating that commercial integer programming software is unable to reliably solve even relatively small instances in short CPU times, we develop a number of polynomial-time constructive heuristics and derive analytical worst-case performance bounds for two of these. Extensive computational experiments on randomly generated test problems indicate that the heuristics perform very well, both on average and in the worst case. We then proceed to develop a scheme for local improvement heuristic, which further improves upon the performance of the constructive heuristics. Finally, we explore exact solution procedures for the problem, examining the performance of different lower bounds as well as several different heuristic branching rules. While we are able to match the performance of the commercial software in some cases, we are unable to significantly improve over it in others. We conclude that the development of consistently effective exact solution methods is a difficult task due to the inherent degeneracy of the problem, and discuss a number of avenues for future research