Jackson's semi-preemptive scheduling on a single machine

DOI10.1016/j.cor.2010.02.008zbMath1231.90193OpenAlexW2071356367MaRDI QIDQ991363

Anis Gharbi, Mohamed Khalil Labidi

Publication date: 7 September 2010

Published in: Computers \& Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.cor.2010.02.008

zbMATH Keywords

branch-and-boundsingle machinemakespanlower boundrelease datesdelivery timesadjustment proceduressemi-preemptive scheduling

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35)

Related Items

Theoretical expectation versus practical performance of Jackson's heuristic ⋮ An Improved Branch-and-Bound Algorithm for the One-Machine Scheduling Problem with Delayed Precedence Constraints ⋮ Unnamed Item ⋮ Scheduling a single machine with primary and secondary objectives

Cites Work

• Unnamed Item
• Single-machine scheduling with release times and tails
• Hybrid decomposition heuristics for solving large-scale scheduling problems in semiconductor wafer fabrication
• A practical use of Jackson's preemptive schedule for solving the job shop problem
• Search tree based approaches for parallel machine scheduling
• A block approach for single-machine scheduling with release dates and due dates
• The one-machine sequencing problem
• An approximation algorithm for a single-machine scheduling problem with release times and delivery times
• A branch and bound algorithm for the job-shop scheduling problem
• Adjustment of heads and tails for the job-shop problem
• Scheduling unit-time tasks with integer release times and deadlines
• An improved max-flow-based lower bound for minimizing maximum lateness on identical parallel machines
• Scheduling jobs with release dates and tails on two unrelated parallel machines to minimize the makespan
• Efficient approximation schemes for scheduling problems with release dates and delivery times
• Branch-and-bound algorithms for solving hard instances of the one-machine sequencing problem
• The Shifting Bottleneck Procedure for Job Shop Scheduling
• An Algorithm for Solving the Job-Shop Problem
• PERFORMANCE ANALYSIS OF SIX APPROXIMATION ALGORITHMS FOR THE ONE-MACHINE MAXIMUM LATENESS SCHEDULING PROBLEM WITH READY TIMES
• Technical Note—Analysis of a Heuristic for One Machine Sequencing with Release Dates and Delivery Times
• Scheduling Unit–Time Tasks with Arbitrary Release Times and Deadlines
• Ordonnancements. La notion de «parties obligatoires» et son application aux problèmes cumulatifs
• Jackson's Rule for Single-Machine Scheduling: Making a Good Heuristic Better
• On Scheduling with Ready Times and Due Dates to Minimize Maximum Lateness
• Minimizing maximum lateness on one machine: computational experience and some applications
• Some simple scheduling algorithms
• Sequencing with due-dates and early start times to minimize maximum tardiness
• Minimizing Maximum Promptness and Maximum Lateness on a Single Machine
• An efficient ILP formulation for the single machine scheduling problem
• Solving open benchmark instances for the job-shop problem by parallel head-tail adjustments