Single machine triangle scheduling
We are given n jobs. Each job has a processing time pj.
We have to place the jobs on the time time, job j schedules from time Sj to Sj+pj. Jobs can overlap but for every i,j we need |Si-Sj| ≥ min(pi,pj).
The goal is to minimize the makespan.
The problem is strongly NP-hard.
The diagram below shows the schedule produced by the greedy algorithm, which is guaranteed to be at most 1.5 times the optimal makespan.