On Preemptive Scheduling of Unrelated Parallel Processors by Linear Programming

DOI10.1145/322092.322101zbMath0388.68027OpenAlexW1965437596MaRDI QIDQ4170215

Jacques Labetoulle, Eugene L. Lawler

Publication date: 1978

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/322092.322101

Mathematics Subject Classification ID

Linear programming (90C05) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Theory of operating systems (68N25)

Related Items (78)

A decomposition property of polyhedra ⋮ On the complexity of preemptive openshop scheduling problems ⋮ A fast preemptive scheduling algorithm with release times and inclusive processing set restrictions ⋮ Scheduling algorithms for procrastinators ⋮ Minimizing the stretch when scheduling flows of divisible requests ⋮ A branch-and-bound method for the single-machine scheduling problem under a non-availability constraint for maximum delivery time minimization ⋮ A network flow-based method to solve performance cost and makespan open-shop scheduling problems with time-windows ⋮ Data transfers in networks ⋮ Complexity and approximation of open shop scheduling to minimize the makespan: a review of models and approaches ⋮ Exact and approximation algorithms for makespan minimization on unrelated parallel machines ⋮ APPROXIMATION ALGORITHMS FOR FLEXIBLE JOB SHOP PROBLEMS ⋮ Preemptive scheduling on uniformly related machines: minimizing the sum of the largest pair of job completion times ⋮ On preemptive scheduling: A general setting for the two-phase method ⋮ Scheduling unit-time jobs on processors with different capabilities ⋮ Optimal Algorithms and a PTAS for Cost-Aware Scheduling ⋮ Schedules with a single preemption on uniform parallel machines ⋮ On the max-weight edge coloring problem ⋮ Project scheduling with finite or infinite number of activity processing modes -- a survey ⋮ Identical parallel machines vs. unit-time shops and preemptions vs. chains in scheduling complexity ⋮ Power of Preemption for Minimizing Total Completion Time on Uniform Parallel Machines ⋮ The battery switching station scheduling problem ⋮ Towards a Robust Scheduling on Unrelated Parallel Machines: A Scenarios Based Approach ⋮ On the complexity of scheduling unrelated parallel machines with limited preemptions ⋮ On the complexity of constructing multiprocessor little-preemptive schedules ⋮ Scheduling periodically occurring tasks on multiple processors ⋮ Parallel machine problems with equal processing times: a survey ⋮ Scheduling problems for parallel dedicated machines under multiple resource constraints. ⋮ Restricted assignment scheduling with resource constraints ⋮ A state-of-the-art review of parallel-machine scheduling research ⋮ Scheduling open shops with parallel machines ⋮ A competitive two-agent scheduling problem on parallel machines with release dates and preemption ⋮ Robust algorithms for preemptive scheduling ⋮ On the complexity of generalized due date scheduling problems ⋮ Mixed integer programming model for scheduling in unrelated parallel processor system with priority consideration ⋮ Makespan minimization in online scheduling with machine eligibility ⋮ On the configuration-LP for scheduling on unrelated machines ⋮ On the geometry, preemptions and complexity of multiprocessor and shop scheduling ⋮ Four decades of research on the open-shop scheduling problem to minimize the makespan ⋮ Approximability of average completion time scheduling on unrelated machines ⋮ Optimal algorithms for scheduling under time-of-use tariffs ⋮ Preemptive Scheduling, Linear Programming and Network Flows ⋮ Preemptive scheduling with staircase and piecewise linear resource availability ⋮ A Benders decomposition-based heuristic for a production and outbound distribution scheduling problem with strict delivery constraints ⋮ SCHEDULING TO MINIMIZE MAX FLOW TIME: OFF-LINE AND ON-LINE ALGORITHMS ⋮ Makespan minimization in online scheduling with machine eligibility ⋮ Stochastic scheduling to minimize expected maximum lateness ⋮ Scheduling with tails and deadlines ⋮ An improved approximation algorithm for the partial Latin square extension problem. ⋮ Two-machine open shop scheduling with an availability constraint ⋮ Minimizing mean weighted execution time loss on identical and uniform processors ⋮ Network flow approaches to pre-emptive open-shop scheduling problems with time-windows ⋮ Solving a bicriteria scheduling problem on unrelated parallel machines occurring in the glass bottle industry ⋮ Ideal schedules in parallel machine settings ⋮ A unified view of parallel machine scheduling with interdependent processing rates ⋮ Algorithms for hierarchical and semi-partitioned parallel scheduling ⋮ Polynomial time approximation algorithms for machine scheduling: Ten open problems ⋮ Minimizing the makespan in open‐shop scheduling problems with a convex resource consumption function ⋮ Preemptive scheduling on uniform machines to minimize mean flow time ⋮ Robust algorithms for preemptive scheduling on uniform machines of non-increasing job sizes ⋮ Integrality Property in Preemptive Parallel Machine Scheduling ⋮ Incorporating the strength of MIP modeling in schedule construction ⋮ A sensitivity analysis to assess the completion time deviation for multi-purpose machines facing demand uncertainty ⋮ Parallel machine scheduling with splitting jobs ⋮ PREEMPTIVE SCHEDULING ALGORITHMS WITH NESTED PROCESSING SET RESTRICTION ⋮ On the optimality of the earliest due date rule in stochastic scheduling and in queueing ⋮ Multicriteria scheduling ⋮ Scheduling Multilayer Divisible Computations ⋮ Effective optimization methods for single-machine scheduling (survey) ⋮ A cutting plane algorithm for the unrelated parallel machine scheduling problem ⋮ Preemptive and non-preemptive scheduling on two unrelated parallel machines ⋮ Preemptive scheduling for approximate computing on heterogeneous machines: tradeoff between weighted accuracy and makespan ⋮ A polynomial feasibility test for preemptive periodic scheduling of unrelated processors ⋮ Approximation algorithms for general parallel task scheduling ⋮ Mathematical programming formulations for machine scheduling: A survey ⋮ Minimizing the number of late jobs on unrelated machines ⋮ Concurrent operations can be parallelized in scheduling multiprocessor job shop ⋮ On-line scheduling to minimize Max flow time: an optimal preemptive algorithm ⋮ New complexity results for parallel identical machine scheduling problems with preemption, release dates and regular criteria

This page was built for publication: On Preemptive Scheduling of Unrelated Parallel Processors by Linear Programming