Constructive algorithms for the scheduling problem on~two processors with the maximum time offset criterion taking into account parallelization and energy consumption

Y. V. Zakharova ; A. O. Evtina

Prikladnaâ diskretnaâ matematika, no. 1 (2025), pp. 118-128

Résumé

We provide theoretical and experimental analysis of the computational complexity of one scheduling problem arising in computer systems and applications. The feature of the statement is the parallelization of operations and resource-dependent durations of operations. Here the processor speed affects the duration of operations and power consumption. For each operation the number of required processors is given. The criterion is the minimization of the maximum lateness under the given energy budget. We prove that the problem is NP-hard using the polynomial reduction from the well-known 3-Partition problem and constructing non-idle instances. An approximate algorithm with polynomial running time is proposed. The algorithm consists of reducing the two-processor problem to the single-processor one. A convex program is proposed for solving the single-processor problem. We investigate the block properties of the solutions generated by the algorithm and show that their objective value is at most doubled optimum maximum lateness plus the maximal due date. The experimental results show the applicability of the proposed algorithm. We construct a series of instances in which the relative deviation from the lower bound is less than 15 %. We also experimentally identify a tendency in decreasing the relative deviation when the number of fully parallelizable operations increases. The theoretical analysis guarantees that the problem is polynomially solvable when all operations are fully parallelizable.

Détail

Keywords: schedule, resource, algorithm, NP-hardness.