Maximal feasible job set,
or 1||ΣUj

We are given n jobs. Each job j has a processing time pj and a duedate dj. We wish to find a schedule for a single machine, which minimizes the number of jobs which complete after their due-date. In fact we search for a maximal feasible job set.

Algorithm by Hogdson: We initialise S to be the empty job set. We processe jobs j in order of increasing due-dates. We add j to S, and if it becomes infeasible, we remove the job i with the greatest processing time (which might be j itself). To check feasibility of S, we simply keep track of the total processing time and compare it with the due-date of job j.

Input

processing times/due dates
output the schedule with one job per row
(otherwise all jobs in a same row)
zoom x2

Output