Local search algorithms for one optimal scheduling problem

The problem of scheduling work for a set of machines is considered. The main characteristics of the problem include the existence of a common due date for all the machines, different unrelated productivity of the machines, the partial strict ordering set for the tasks and the value set for each of the tasks to be scheduled. The semantic and formal models of the problem are specified. Two local search algorithms are suggested: a deterministic local search algorithm and a simulated annealing algorithm. Key implementation points for each of the algorithms are covered; the algorithms' as sequences of steps are described and a comparison of the suggested algorithms' results when used on 16 input data sets is performed.