Leírás
Given a finite set of jobs and a common resource. Each job has the
same processing time $p$, alongside an individual release date and
deadline, and utilizes either zero or one unit from the resource. A
schedule specifies a star time for each job, and it determines the
resource usage over time.
The objective is to minimize a separable convex function of the
resource usage. Prior to our work, the existing body of research only
tackled the scenario where $p = 1$ and the release dates and deadlines
are integer numbers.
We explore three variations of this fundamental problem, accompanied
by applications drawn from existing literature. In the first variant,
all jobs require one unit of the resource. In the second and third
variants, there are $m$ parallel machines, and at most $m$ jobs may be
processed concurrently at any given moment. Furthermore, in the second
variant, each job has a unit processing time, and may require either
0 or 1 unit of the resource.
In the third case, there are $\nu$ distinct resource types each linked
with a convex function, and each job requires precisely one of these
resources types. The jobs have agreeable release dates and deadlines.
For each of these cases, we introduce novel polynomial-time algorithms
designed to determine optimal solutions.