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

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

Cited in

(83)

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

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)