A new dynamic programming algorithm for the parallel machines total weighted completion time problem

DOI10.1016/0167-6377(92)90035-2zbMath0760.90057OpenAlexW2019636973MaRDI QIDQ1197881

Chung-Yee Lee, Reha Uzsoy

Publication date: 16 January 1993

Published in: Operations Research Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0167-6377(92)90035-2

zbMATH Keywords

total weighted completion timeparallel identical machinespseudopolynomial complexity

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Dynamic programming (90C39)

Related Items

An exact extended formulation for the unrelated parallel machine total weighted completion time problem ⋮ Unrelated parallel machine scheduling with new criteria: complexity and models ⋮ Decorous combinatorial lower bounds for row layout problems ⋮ On the complexity of scheduling problems with a fixed number of parallel identical machines ⋮ Infinite split scheduling: a new lower bound of total weighted completion time on parallel machines with job release dates and unavailability periods ⋮ Lagrangian relaxation and column generation-based lower bounds for the \(\text{Pm},h_{j1}\parallel \sum w_iC_i\) scheduling problem ⋮ A Branch-and-Price Algorithm for Parallel Machine Scheduling Using ZDDs and Generic Branching ⋮ A branch-and-bound algorithm to minimize total weighted completion time on identical parallel machines with job release dates ⋮ Dynamic programming algorithms for scheduling parallel machines with family setup times ⋮ Non-identical parallel-machine scheduling research with minimizing total weighted completion times: models, relaxations and algorithms ⋮ A comparison of branch-and-bound algorithms for a family scheduling problem with identical parallel machines ⋮ Scheduling batch processing machines with incompatible job families ⋮ Heuristic methods for the identical parallel machine flowtime problem with set-up times ⋮ A new Lagrangian relaxation algorithm for hybrid flowshop scheduling to minimize total weighted completion time ⋮ On the minimization of total weighted flow time with identical and uniform parallel machines ⋮ Optimal solutions for unrelated parallel machines scheduling problems using convex quadratic reformulations ⋮ Machine scheduling with a rate-modifying activity

Cites Work

• Unnamed Item
• Unnamed Item
• Worst Case Bound of an LRF Schedule for the Mean Weighted Flow-Time Problem
• An improved branching scheme for the branch and bound procedure of schedulingnjobs onmparallel machines to minimize total weighted flowtime
• Algorithms for Scheduling Independent Tasks
• Scheduling independent tasks to reduce mean finishing time
• A Functional Equation and its Application to Resource Allocation and Sequencing Problems

This page was built for publication: A new dynamic programming algorithm for the parallel machines total weighted completion time problem