Scheduling equal-length jobs on identical parallel machines

DOI10.1016/S0166-218X(99)00238-3zbMath0971.90027WikidataQ127124572 ScholiaQ127124572MaRDI QIDQ1570817

Publication date: 11 July 2000

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0166-218x(99)00238-3

zbMATH Keywords

dynamic programming; parallel machine scheduling; total tardiness; weighted sum of completion times

Mathematics Subject Classification ID

90B35: Deterministic scheduling theory in operations research

90C39: Dynamic programming

Related Items

On the Integration of Theoretical Single-Objective Scheduling Results for Multi-objective Problems, On scheduling a single machine to minimize a piecewise linear objective function: A compact MIP formulation, Inverse chromatic number problems in interval and permutation graphs, Aircraft landing problems with aircraft classes, Optimization of inland shipping. A polynomial time algorithm for the single-ship single-lock optimization problem, Properties of optimal schedules for the minimization total weighted completion time in preemptive equal-length job with release dates scheduling problem on a single machine, Preemptive scheduling of equal-length jobs in polynomial time, Dominance rules for the parallel machine total weighted tardiness scheduling problem with release dates, Minimizing total weighted tardiness on a single machine with release dates and equal-length jobs, Fast LP models and algorithms for identical jobs on uniform parallel machines, Two-agent scheduling on uniform parallel machines with min-max criteria, Minimizing total weighted tardiness for scheduling equal-length jobs on a single machine, Scheduling jobs with equal processing times and time windows on identical parallel machines, An \(O( n^2)\) algorithm for scheduling equal-length preemptive jobs on a single machine to minimize total tardiness, A branch-and-bound algorithm to minimize total weighted completion time on identical parallel machines with job release dates, On single-machine scheduling without intermediate delays, A decomposition scheme for single stage scheduling problems, On a parallel machine scheduling problem with equal processing times, On minimizing the weighted number of late jobs in unit execution time open-shops., Identical parallel machines vs. unit-time shops and preemptions vs. chains in scheduling complexity, A note on scheduling multiprocessor tasks with identical processing times., Complexity results for flow-shop problems with a single server, Complexity results for parallel machine problems with a single server, Matching supply and demand in a sharing economy: classification, computational complexity, and application, Single-machine scheduling with release times, deadlines, setup times, and rejection, Metric approach for finding approximate solutions of scheduling problems, An exact algorithm for the preemptive single machine scheduling of equal-length jobs, Primal-dual analysis for online interval scheduling problems, A metric for total tardiness minimization, Infinite split scheduling: a new lower bound of total weighted completion time on parallel machines with job release dates and unavailability periods, Parallel machine problems with equal processing times: a survey, Scheduling two agents on uniform parallel machines with~makespan and cost functions, Unnamed Item, Lower and Upper Bounds for the Preemptive Single Machine Scheduling Problem with Equal Processing Times, On the Complexity of Speed Scaling

Cites Work