OPEN SHOP SCHEDULING WITH UET TASKS AND TIME DELAYS

摘要

When considering the time incurred by the transfer of tasks from one machine to another, as it occurs in the real world, the resolution of the corresponding scheduling problem becomes harder to solve from the computational point of view. In this paper, heuristics along with their worst case analyses are presented to solve the open shop problem, mainly for the case of unit execution times (UET) tasks, so as to minimize the overall completion time, also called the makespan.