Задача поиска оптимального расписания одного станка с директивными сроками работ

The article is concerned with the single machine optimization problem that is typical for scheduling production processes with a number of consecutive and non-preemptive operations. A paper machine, a plywood press or a corrugator execution plan construction can be considered as an example. The processing work should start at a particular release time and should be completed no later than the relative due date. Otherwise, a proportional to the violation fine is imposed. The objective of the problem is to find a processing order of the works that minimize total weighted tardiness. Moreover, the study covers the case of the total number of violated due dates minimization and an option with the works available at zero start time. The solution of the problem is based on metaheuristic algorithms that provide an opportunity to obtain sufficiently good result. Additionally, the author proposes a new combined algorithm that exploits basic metaheuristics in order to consistently improve the current plan. Inversion operators, shift forward, shift back and shift forward, and back operators are used to employ obtained solutions in practice. As a result, the combined algorithm provides an important solution in quality improvement comparable to the level of computation complexity in mentioned earlier metaheuristics.