A heuristic for the problem of scheduling production on parallel machines unrelated to batching, task families and setup times

This work is motivated by the diffusion operations required for semiconductor manufacturing. Silicon wafers are grouped into different, often incompatible, product families and processed in batches on parallel machines. The objective is to minimize the sum of the task completion times (flow time), considering the existence of setups in the transition between the different families. A formal definition of the problem is then presented and, due to the fact that it is considered strongly NP-difficult, a constructive heuristic is proposed. The heuristic is compared to other algorithms reported for similar problems across distance from optimal solutions in small-sized instances. The results show that the proposed heuristic achieves better solutions, however, it has a higher degree of complexity.