Highly efficient scheduling algorithms for identical parallel machines with sufficient conditions for optimality of the solutions

Abstract

This paper aims to develop new highly efficient PSC-algorithms (algorithms that contain a polynomial-time sub-algorithm with sufficient conditions for the optimality of the solutions obtained) for several interrelated problems involving identical parallel machine scheduling. These problems share common basic theoretical positions and common principles of their solving. Two main intractable scheduling problems are considered: (“Minimization of the total tardiness of jobs on parallel machines with machine release times and a common due date” (TTPR) and “Minimising the total tardiness of parallel machines completion times with respect to the common due date with machine release times” (TTCR)) and an auxiliary one (“Minimising the difference between the maximal and the minimal completion times of the machines” (MDMM)). The latter is used to efficiently solve the first two ones. For the TTPR problem and its generalisation in the case when there are machines with release times that extend past the common due date (TTPRE problem), new theoretical properties are given, which were obtained on the basis of the previously published ones. Based on the new theoretical results and computational experiments the PSC-algorithm solving these two problems is modified (sub-algorithms A1, A2). Then the auxiliary problem MDMM is considered and Algorithm A0 is proposed for its solving. Based on the analysis of computational experiments, A0 is included in the PSC-algorithm for solving the problems TTPR, TTPRE as its polynomial component for constructing a schedule with zero tardiness of jobs if such a schedule exists (a new third sufficient condition of optimality). Next, the second intractable combinatorial optimization problem TTCR is considered, deducing its sufficient conditions of optimality, and it is shown that Algorithm A0 is also an efficient polynomial component of the PSC-algorithm solving the TTCR problem. Next, the case of a schedule structure is analysed (partially tardy), in which the functionals of the TTPR and TTCR problems become identical. This facilitates the use of Algorithm A1 for the TTPR problem in this case of the TTCR problem. For Algorithm A1, in addition to the possibility of obtaining a better solution, there exists a theoretically proven estimate of the deviation of the solution from the optimum. Thus, the second PSC-algorithm solving the TTCR problem finds an exact solution or an approximate solution with a strict upper bound for its deviation from the optimum. The practicability of solving the problems under consideration is substantiated.

Keywords

• scheduling
• intractable problems of discrete optimisation
• sufficient conditions for optimality
• parallel machines
• common due date