Coupled task scheduling with convex resource consumption functions

We study a single machine scheduling problem with coupled tasks under limited resource availability. Each job comprises of two tasks which are separated by an exact amount of delay. We assume that the processing time of the initial task and the duration of the delay period are equal and the same for all jobs. The processing time of the completion task, however, is job-dependent and modelled as a convex function of the amount of resource the job is allocated. The scheduling objective consists of minimizing the makespan, subject to an upper-bound on the resource availability. We provide several properties of an optimal solution and develop an O(n(2)) time algorithm for the problem. Crown Copyright (C) 2021 Published by Elsevier B.V. All rights reserved.

Automated summary

In this study, we investigated a single machine scheduling problem with coupled tasks and limited resources. Each job consists of two tasks with a specific delay between them. While the processing times for initial tasks and delay periods are identical for all jobs, the completion task processing time is dependent on the job and modeled as a convex function of the allocated resources. The objective of the scheduling is to minimize the makespan, with a constraint on the resource availability. We provided properties of an optimal solution and an O(n^2) time algorithm for this problem.