In scheduling with early work, jobs are assigned to a machine by maximizing the parts of non-preemptive jobs executed before their due dates. This paper considers a weighted early work maximization problem on parallel, identical machines with an antithetical property, which holds that wi≤ wj implies di≥ dj for any two jobs i and j where wj and dj are weight and due date of job j, respectively. We show that the problem is weakly NP-hard. Due to the high complexity of dynamic programming, we develop three solution approaches: mixed-integer programming, heuristics, and a branch-and-bound algorithm. Through numerical experiments, we verify their performance.
|Publication status||Accepted/In press - 2022|
- Branch and bound
- Computational complexity
- Early work