Scheduling chain-structured tasks to minimize makespan and mean flow time
From MaRDI portal
Publication:1814098
DOI10.1016/0890-5401(91)90009-QzbMath0754.90029OpenAlexW2025235423MaRDI QIDQ1814098
Gilbert H. Young, Joseph Y.-T. Leung, Jian-Zhong Du
Publication date: 25 June 1992
Published in: Information and Computation (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0890-5401(91)90009-q
Abstract computational complexity for mathematical programming problems (90C60) Deterministic scheduling theory in operations research (90B35)
Related Items (29)
A survey on how the structure of precedence constraints may change the complexity class of scheduling problems ⋮ A fixed-parameter algorithm for scheduling unit dependent tasks on parallel machines with time windows ⋮ Scheduling chains to minimize mean flow time ⋮ An exact method for \(Pm/sds, r_{i}/ \sum^{n}_{i=1} C_{i}\) problem ⋮ `Strong'-`weak' precedence in scheduling: extensions to series-parallel orders ⋮ Is a unit-job shop not easier than identical parallel machines? ⋮ Identical parallel machines vs. unit-time shops and preemptions vs. chains in scheduling complexity ⋮ Integer preemptive scheduling on parallel machines ⋮ How useful are preemptive schedules? ⋮ Scheduling of uniform parallel machines with s-precedence constraints ⋮ Precedence constrained scheduling to minimize sum of weighted completion times on a single machine ⋮ Scheduling results applicable to decision-theoretic troubleshooting ⋮ A metric approach for scheduling problems with minimizing the maximum penalty ⋮ Scheduling of parallel machines to minimize total completion time subject to s-precedence constraints ⋮ An EPTAS for scheduling fork-join graphs with communication delay ⋮ The complexity of machine scheduling for stability with a single disrupted job ⋮ On preemption redundancy in scheduling unit processing time jobs on two parallel machines ⋮ APPROXIMATION SCHEMES FOR SCHEDULING JOBS WITH CHAIN PRECEDENCE CONSTRAINTS ⋮ A best possible online algorithm for scheduling equal-length jobs on two machines with chain precedence constraints ⋮ Online scheduling with chain precedence constraints of equal-length jobs on parallel machines to minimize makespan ⋮ Ideal schedules in parallel machine settings ⋮ b9000A 1/4 approximate algorithm for P2/tree/Cmax ⋮ Polynomial time approximation algorithms for machine scheduling: Ten open problems ⋮ Scheduling of resource tasks ⋮ Makespan minimization with OR-precedence constraints ⋮ Integrality Property in Preemptive Parallel Machine Scheduling ⋮ Scheduling three chains on two parallel machines ⋮ Heuristics for unrelated machine scheduling with precedence constraints ⋮ How small are shifts required in optimal preemptive schedules?
Cites Work
- Scheduling with Deadlines and Loss Functions
- Sequencing Jobs to Minimize Total Weighted Completion Time Subject to Precedence Constraints
- On the Complexity of Mean Flow Time Scheduling
- Scheduling independent tasks to reduce mean finishing time
- Preemptive Scheduling of Real-Time Tasks on Multiprocessor Systems
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Scheduling chain-structured tasks to minimize makespan and mean flow time
