The problem of scheduling unit length tasks on identical machines in an industrial production unit is considered. The tasks belong to k part types, such that any task may and must belong to one part type. Every machine needs a setup time, say S, when changing from one part type to another. The problem is to obtain an assignment of tasks on machines such that the makespan is minimized. For the case of k=2 part types, a method that leads to the optimal solution (i.e.to the minimum makespan), as well as the associated algorithm are presented. For the case of k>2 part types, a method is presented that reduces the complexity of the optimal algorithm, and helps in the construction of approximate heuristic algorithms. A 2-part type example is provided that illustrates the application of the optimal algorithm, and shows the effect of the machines set-up time upon the optimal schedule.
All articles published by Studies in Informatics and Control (SIC) are published in accordance with the terms and conditions of the Creative Commons Attribution License (CC BY-NC-SA 4.0).