Minimizing total weighted late work with step-learning on a single machine
Abstract
We study single-machine scheduling problems with step-learning to minimize the total weighted late work. Step-learning is a mechanism that allows jobs to be completed more efficiently if started after a job-dependent learning-date. We show that this problem is strongly NP -hard when both learning-dates and due-dates are arbitrary, but when at least one is assumed to be the same for all jobs, the problem is NP -hard in the ordinary sense, and we provide pseudo-polynomial algorithms for these cases.
Fields of Study & Subjects
Scheduling and Optimization Algorithms
Machine Learning and Algorithms
Parallel Computing and Optimization Techniques
Publication details
- Journal / source
- Discrete Applied Mathematics
- Publisher
- Elsevier BV
- Volume
- 391
- Pages
- 277–293
- Publication date
- 19 May 2026
- Language
- EN