-

 

 

 




Optimization Online





 

Scheduling a sequence of tasks with general completion costs

Francis Sourd (Francis.Sourd***at***lip6.fr)

Abstract: 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 in 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 to exceed a maximum fixed cost.

Keywords: Scheduling, Just-in-time, Dynamic Programming

Category 1: Applications -- OR and Management Sciences

Category 2: Applications -- OR and Management Sciences (Scheduling )

Citation: European Journal of Operational Research 165, p.82-96. http://dx.doi.org/10.1016/j.ejor.2004.01.025

Download:

Entry Submitted: 10/03/2002
Entry Accepted: 10/03/2002
Entry Last Modified: 04/21/2005

Modify/Update this entry


  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository

 

Submit
Update
Policies
Coordinator's Board
Classification Scheme
Credits
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society