Abstract:
We consider a problem of scheduling jobs performed on a single machine. Precedence relations between jobs are established, as well as subsets of jobs that require additional external resources, for which a fee is charged. For each external resource, the extreme (first and last) job to be executed using that resource is uniquely determined. It is necessary to order the jobs without violating the precedence relations and minimizing total rent payments. We have proved that this problem is NP-hard in the strong sense, even if the processing times of all jobs are the same and the prices of all external resources are equal. Based on the properties of the objective function, lower bounds and the branch-and-bound method are proposed to solve the problem. In this method, enumeration is performed according to feasible permutations of extreme jobs using external resources. The computational experiment showed the efficiency of the proposed lower bounds of the objective function, which make it possible to cut off unpromising branches in the search tree. We also determined the type of input data for which the developed method is more successful than another known variant of exact methods that enumerate all jobs. In particular, for large-dimensional problems with fewer than 20 external resources, this method proves to be more efficient than CP Optimizer solver which is based on constraint programming.
Keywords:discrete optimization, scheduling, branch-and-bound method, algorithms, minimizing the use of external resources.
UDC:519.854.2 BBK:
22.18
Received: May 7, 2025 Published: September 30, 2025
Fulltext:
PDF file (366 kB)