On modelling the maximum workload allocation for parallel unrelated machines with setups |
| |
Authors: | Brenda L Dietrich Laureano F Escudero |
| |
Institution: | (1) IBM Research, T.J. Watson Research Center, 10598 Yorktown Heights, NY, USA;(2) UITESA and Mathematical Sciences School, Complutense University of Madrid, 28040 Madrid, Spain |
| |
Abstract: | Consider 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. We present two equivalent 0–1 models. The first model arises by considering the assignment of individual parts to machines. It is amenable to Lagrangian 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. We report about our computational experience for finding lower bounds of the optimal solution by appending violated cuts and, ultimately, obtaining the optimal solution of real-life problems. |
| |
Keywords: | Production allocation equivalent 0– 1 models cutting planes cliques covers LP relaxation |
本文献已被 SpringerLink 等数据库收录! |
|