On the two-phase method for preemptive scheduling

DOI10.1016/0377-2217(88)90332-3MaRDI QIDQ1107434zbMATH OpenOpenAlexFDO

Authors Dominique De Werra

Publication date 1988

Published in European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0377-2217(88)90332-3

zbMATH Keywords

flexible manufacturing systemsminimum total completion timeparallel processorsPreemptive schedulingtotal unimodularitytwo-phase method

Mathematics Subject Classification ID

Deterministic network models in operations research (90B10) Production models (90B30) Deterministic scheduling theory in operations research (90B35) Linear programming (90C05) Applications of mathematical programming (90C90)

Review text

Preemptive scheduling problems on parallel processors may in some cases be solved by a two-phase method: first solve an LP problem which will give the minimum total completion time T and the processing times of the jobs on the various processors; second construct a feasible schedule using T time units. Some extensions of this procedure are discussed. A general model for preemptive scheduling is described with a two-phase method for solving problems of this type.

Recommendations

• On preemptive scheduling: A general setting for the two-phase method
• Preemptive scheduling with two minimax criteria
• Optimal Preemptive Scheduling of Two Unrelated Processors
• Ideal preemptive schedules on two processors
• TWO PRECEDENCE-RELATED TASK-SCHEDULING ALGORITHMS
• Preemptive on-line scheduling for two uniform processors
• An Approximation Algorithm for Preemptive Scheduling on Parallel-Task Systems
• Preemptive scheduling of two uniform parallel machines to minimize total tardiness
• A tight 2-approximation for preemptive stochastic scheduling
• Preemptive and non-preemptive scheduling on two unrelated parallel machines

Cites work

• A decomposition property of polyhedra
• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 4095196 (Why is no real title available?)
• scientific article; zbMATH DE number 3722085 (Why is no real title available?)
• scientific article; zbMATH DE number 3338381 (Why is no real title available?)
• Preemptive scheduling with staircase and piecewise linear resource availability
• Preemptive Scheduling, Linear Programming and Network Flows
• Variations on the integral decomposition property

Cited in

(11)

• Preemptive scheduling in a two-stage multiprocessor flow shop is NP-hard
• Mathematical models for preemptive shop scheduling problems
• On preemptive scheduling: A general setting for the two-phase method
• Complexity and approximation of open shop scheduling to minimize the makespan: a review of models and approaches
• A heuristic for scheduling in a two-stage hybrid flowshop with renewable resources shared among the stages
• Preemptive Scheduling, Linear Programming and Network Flows
• A Survey on Approximation Algorithms for Scheduling with Machine Unavailability
• Preemptive scheduling with staircase and piecewise linear resource availability
• A two-stage hardware scheduler combining greedy and optimal scheduling
• Mathematical programming formulations for machine scheduling: A survey
• Almost nonpreemptive schedules

This page was built for publication: On the two-phase method for preemptive scheduling

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1107434)