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