A unified approach for single machine scheduling with position‑dependent workloads and positional penalties

摘要

In this paper, we provide unified methods for solving scheduling problems with convex resource allocation, concentratingon objective functions that can be expressed as a scalar product of the actual processing times vector and ajob-independent and position-dependent penalties vector. We assume general position-dependent workloads, i.e., theworkloads are not restricted to be either monotone functions of the job positions or to specific functions. The first unifiedmethod focuses on minimizing a scheduling measure subject to a constraint on the resource consumption, whereasthe second addresses the complementary problem of minimizing the consumed resource given an upper bound on thescheduling measure. For each unified approach, we provide a methodical analysis and consequently provide a O（n~3）solution algorithm. Furthermore, to demonstrate the unified schemes, we solve several scheduling measures that involveearliness and tardiness penalties.