Jackson's Semi-Preemptive Scheduling on a Single Machine

Journal Article

Gharbi, Anis . 2010

• رابط المنشور على الويب: Jackson's Semi-Preemptive Scheduling on a Single Machine
• الوسوم: Semi-preemptive scheduling, Single machine, Release dates, Delivery times, Makespan, Lower bound
• المجلة \ الصحيفة: Computers and Operations Research
• رقم العدد: 12
• رقم الإصدار السنوي: 37
• الصفحات: 2082–2088

مستخلص المنشور

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.