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.

Input

processing times for every job

Output

The diagram below shows the schedule produced by the greedy algorithm, which is guaranteed to be at most 1.5 times the optimal makespan.

"; ?>

[src]