A dynamic programming algorithm for the single-machine scheduling problem with release dates and deteriorating processing times
type: Item
instance of: scholarly article
title: A dynamic programming algorithm for the single-machine scheduling problem with release dates and deteriorating processing times
zbMATH Open document ID: 1167.90005
author: Alberto Bosio
author: Giovanni Righini
published in: Mathematical Methods of Operations Research
publication date: 2009-04-27T00:00:00Z
review text: The problem of minimizing the makespan on one machine is considered. Each job has a release date. The processing time of each job depends on the starting time linearly. For this strongly NP-hard problem an exact optimization algorithm with exponential worst-case complexity is presented. Polynomial solvable subproblems and upper and lower bounds to the makespan are described. Two different sets of experiments are performed. The first set of experiments is aimed at studying how the time consumption of the algorithm depends on the data. The second set of experiments compares different search policies.
reviewed by: Svetlana A. Kravchenko
Mathematics Subject Classification ID: 90B35
Mathematics Subject Classification ID: 90C27
Mathematics Subject Classification ID: 90C39
zbMATH DE Number: 5547525
zbMATH Keywords: combinatorial optimization
zbMATH Keywords: dynamic programming
zbMATH Keywords: scheduling
MaRDI profile type: Publication
full work available at URL: s00186-008-0258-1
OpenAlex ID: W2035495488
cites work: A dynamic programming algorithm for the single-machine scheduling problem with deteriorating processing times
cites work: Scheduling Deteriorating Jobs on a Single Processor
cites work: The complexity of scheduling starting time dependent tasks with release times
cites work: A concise survey of scheduling with time-dependent processing times
DOI: 10.1007/S00186-008-0258-1
description: scientific article; zbMATH DE number 5547525