Minimizing the Makespan in Open-Shop Scheduling Problems with a Convex Resource Consumption Function

摘要

We consider open-shop scheduling problems where operation-processing times are a convex decreasing function of a common limited nonrenewable resource. The scheduler's objective is to determine the optimal job sequence on each machine and the optimal resource allocation for each operation in order to minimize the makespan. We prove that this problem is NP-hard, but for the special case of the two-machine problem we provide an efficient optimization algorithm. We also provide a fully polynomial approximation scheme for solving the preemptive case.