Optimal timing of a sequence of tasks with general completion costs

Scheduling a sequence of tasks––in the acceptation of finding the execution times––is not a trivial problem when the optimization criterion is irregular as for instance in earliness–tardiness problems. This paper presents an efficient dynamic programming algorithm to solve the problem with general c...

Full description

Saved in:
Bibliographic Details
Published in:European journal of operational research 2005-08, Vol.165 (1), p.82-96
Main Author: Sourd, Francis
Format: Article
Language:English
Subjects:
Algorithms
Applied sciences
Computer Science
Costs
Dynamic programming
Earliness–tardiness costs
Exact sciences and technology
Idle time penalties
Mathematical programming
Operational research and scientific management
Operational research. Management science
Optimization
Piecewise linear cost functions
Scheduling
Studies
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Scheduling a sequence of tasks––in the acceptation of finding the execution times––is not a trivial problem when the optimization criterion is irregular as for instance in earliness–tardiness problems. This paper presents an efficient dynamic programming algorithm to solve the problem with general cost functions depending on the end time of the tasks, idle time costs and variable durations also depending on the execution time of the tasks. The algorithm is also valid when the precedence graph is a tree and it can be adapted to determine the possible execution windows for each task not exceeding a maximum fixed cost.
ISSN:0377-2217
1872-6860
DOI:10.1016/j.ejor.2004.01.025