On the two-phase method for preemptive scheduling
type: Item
instance of: scholarly article
title: On the two-phase method for preemptive scheduling
zbMATH Open document ID: 0652.90064
DOI: 10.1016/0377-2217(88)90332-3
author: Dominique De Werra
published in: European Journal of Operational Research
publication date: 1988-01-01T00:00:00Z
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.
Mathematics Subject Classification ID: 90B35
Mathematics Subject Classification ID: 90B30
Mathematics Subject Classification ID: 90B10
Mathematics Subject Classification ID: 90C90
Mathematics Subject Classification ID: 90C05
zbMATH DE Number: 4064758
zbMATH Keywords: total unimodularity
zbMATH Keywords: flexible manufacturing systems
zbMATH Keywords: Preemptive scheduling
zbMATH Keywords: parallel processors
zbMATH Keywords: two-phase method
zbMATH Keywords: minimum total completion time
MaRDI profile type: Publication
full work available at URL: 0377-2217(88)90332-3
OpenAlex ID: W1988424649
cites work: Q5615282
cites work: Q3821925
cites work: Preemptive scheduling with staircase and piecewise linear resource availability
cites work: Q3328583
cites work: Q3911382
cites work: Preemptive Scheduling, Linear Programming and Network Flows
cites work: A decomposition property of polyhedra
cites work: Variations on the integral decomposition property
Recommended article: On preemptive scheduling: A general setting for the two-phase method
Recommended article: Preemptive scheduling with two minimax criteria
Recommended article: Optimal Preemptive Scheduling of Two Unrelated Processors
Recommended article: Ideal preemptive schedules on two processors
Recommended article: TWO PRECEDENCE-RELATED TASK-SCHEDULING ALGORITHMS
Recommended article: Preemptive on-line scheduling for two uniform processors
Recommended article: An Approximation Algorithm for Preemptive Scheduling on Parallel-Task Systems
Recommended article: Preemptive scheduling of two uniform parallel machines to minimize total tardiness
Recommended article: A Tight 2-Approximation for Preemptive Stochastic Scheduling
Recommended article: Preemptive and non-preemptive scheduling on two unrelated parallel machines
description: scientific article; zbMATH DE number 4064758