Jackson's Semi-Preemptive Scheduling on a Single Machine

Journal Article

Gharbi, Anis . 2010

• Publication Online URL: Jackson's Semi-Preemptive Scheduling on a Single Machine
• Tags: Semi-preemptive scheduling, Single machine, Release dates, Delivery times, Makespan, Lower bound
• Magazine \ Newspaper: Computers and Operations Research
• Issue Number: 12
• Volume Number: 37
• Pages: 2082–2088

Publication Abstract

We propose an effective improvement of the well-known Jackson's preemptive schedule lower bound for the single machine scheduling problem with heads and tails. The semi-preemptive scheduling concept roughly consists in reducing the preemption impact by constraining some particular job parts to be processed in reduced time intervals. The impact of semi-preemptive scheduling is twofold: it yields a lower bound which dominates the preemptive one, and enables more effective adjustments of the heads and tails. Our experimental study revealed that suitably embedding our procedure within Carlier's algorithm makes feasible to solve all of the hard instances which could not be solved by its original variant.