| Article ID: | iaor1994899 |
| Country: | Switzerland |
| Volume: | 43 |
| Issue: | 1/4 |
| Start Page Number: | 359 |
| End Page Number: | 377 |
| Publication Date: | Oct 1993 |
| Journal: | Annals of Operations Research |
| Authors: | Escudero Laureano F., Dietrich Brenda L. |
Considering a manufacturing process in which a group of machines (or people) perform a single operation on a number of different parts. The processing time depends on both the part and the machine. In addition, each machine requires significant setup time between processing different part types. The problem consists of obtaining a feasible allocation of parts to machines such that the makespan (i.e. greatest machine workload) is minimized. The authors present two equivalent 0-1 models. The first model arises by considering the assignment of individual parts to machines. It is amenable to Lagrangean decomposition techniques. The second model is more hierarchical in nature; it considers the two options of assigning an entire part type to a single machine, or of splitting the type across machines. The second model is more amenable than the first to branch-and-bound techniques. They report about the present computational experience for finding lower bounds of the optimal solution by appending violated cuts and, ultimately, obtaining the optimal solution of real-life problems.