.png){kind=icon}
.png){kind=icon}
Return
Single-machine scheduling with learning dates
.png){kind=icon}
PRE
AI
DOI：10.1016/j.ejor.2026.08.033.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
•
We consider a single-machine scheduling problem with learning dates to minimize the makespan.
•
We develop an O(nlogn)-time solution algorithm for the preemptive case.
•
We show that the non-preemptive case of the problem is NP-hard.
•
We provide an O(nlogn)-time approximation algorithm for the non-preemptive case.
Abstract
This paper studies a single-machine scheduling problem with learning dates to minimize the makespan. Each job has a distinct learning date, and its processing time differs before and after the learning date. All jobs have the same learning ratio, i.e., the ratio of the processing time after learning to that before learning is ρ(0<ρ<1) for each job. We consider two variants of the problem according to whether the jobs are preemptible, namely the preemptive model and the non-preemptive model. For the preemptive case, we develop an O(nlogn)-time solution algorithm with at most one preemption. For the non-preemptive case, we show that the problem is NP-hard and design an approximation algorithm whose worst-case ratio is no greater than 1+ρ1+ρ2, with a time complexity of O(nlogn).
Keywords:
Learning date
Polynomial-time algorithm
Approximation algorithm
Makespan
Journal
IF:
6
Papers:
2.2W
Citations:
6.4W