Scheduling identical parallel machines to minimize total weighted completion time
type: Item
instance of: scholarly article
title: Scheduling identical parallel machines to minimize total weighted completion time
zbMATH Open document ID: 0809.90073
DOI: 10.1016/0166-218X(92)00176-M
published in: Discrete Applied Mathematics
publication date: 1994-03-24T00:00:00Z
review text: A branch-and-bound algorithm is proposed for the problem of scheduling \(n\) jobs with known integer processing times and weights on \(m\) identical parallel machines with the objective to minimize total weighted completion time. The algorithm is based on a new lower bound which is derived by Lagrangean relaxation of the machine capacity constraints. Instead of determining the optimal parameter for the Lagrangean problem that gives the best lower bound a heuristic method is used. This allows to compute the lower bound efficiently. It is shown that the heuristic yields a lower bound that is exact when there is a single machine or when all jobs have unit processing times. To eliminates nodes from the search tree the authors present a new dominance rule. They give computational results which compare their branch-and-bound algorithm to previous ones and indicate the value of the new dominance rule.
Mathematics Subject Classification ID: 90B35
zbMATH DE Number: 527426
zbMATH Keywords: branch-and-bound
zbMATH Keywords: identical parallel machines
zbMATH Keywords: total weighted completion time
zbMATH Keywords: Lagrangean relaxation
zbMATH Keywords: heuristic
author: Hocine Belouadah
author: Chris N. Potts
reviewed by: Martin Middendorf
MaRDI profile type: Publication
cites work: Scheduling with parallel processors and linear delay costs
cites work: Scheduling independent tasks to reduce mean finishing time
cites work: Project scheduling with resource constraints: A branch and bound approach. Note by Frederik Kaefer
cites work: Q4658190
cites work: A dual algorithm for the one-machine scheduling problem
cites work: The Lagrangian Relaxation Method for Solving Integer Programming Problems
cites work: Q4178782
cites work: An algorithm for single machine sequencing with release dates to minimize total weighted completion time
cites work: Validation of subgradient optimization
cites work: Worst Case Bound of an LRF Schedule for the Mean Weighted Flow-Time Problem
cites work: Sequencing Jobs to Minimize Total Weighted Completion Time Subject to Precedence Constraints
cites work: A Lagrangean Based Branch and Bound Algorithm for Single Machine Sequencing with Precedence Constraints to Minimize Total Weighted Completion Time
cites work: An algorithm for single machine sequencing with deadlines to minimize total weighted completion time
cites work: A Branch and Bound Algorithm for the Total Weighted Tardiness Problem
cites work: Algorithms for Scheduling Independent Tasks
cites work: An improved branching scheme for the branch and bound procedure of schedulingnjobs onmparallel machines to minimize total weighted flowtime
full work available at URL: 0166-218x(92)00176-m
OpenAlex ID: W1976831727
description: scientific article; zbMATH DE number 527426