Scheduling jobs to minimize a convex function of resource usage
研究如何安排一组具有相同加工时间的作业，使得资源使用量的凸函数最小，并针对三种变体提出了多项式时间算法。
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. 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 each. 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 ν distinct resource types each linked with a convex function, and each job requires precisely one of these resources types. The jobs have a uniform processing time p and possess agreeable release dates and deadlines. For each of these cases, we introduce novel polynomial-time algorithms designed to determine optimal solutions.