The Problem of Tasks Scheduling with Due Dates in a Flexible Multi-machine Production Cell

摘要

In the paper we consider an NP-hard problem of tasks scheduling with due dates and penalties for the delay in a flexible production cell. Each task should be assigned to one of the cell's machines and the order of their execution on machines should be determined. The sum of penalties for tardiness of tasks execution should be minimized. We propose to use the tabu search algorithm to solve the problem. Neighborhoods are generated by moves based on changing the order of tasks on the machine and changing the machine on which the task will be performed. We prove properties of moves that significantly accelerate the search of the neighborhoods and shorten the time of the algorithm execution and in result significantly improves the efficiency of the algorithm compared to the version that does not use these properties.