On Preemptive Scheduling of Unrelated Parallel Processors by Linear Programming

DOI10.1145/322092.322101MaRDI QIDQ4170215zbMATH OpenOpenAlexFDO

Authors Eugene L. Lawler, Jacques Labetoulle

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)

Cited in

(80)

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

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

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