A bicriterion approach to time/cost trade-offs in scheduling with convex resource-dependent job processing times and release dates

A bicriterion approach to time/cost trade-offs in scheduling with convex resource-dependent job processing times and release dates

0.00 Avg rating0 Votes
Article ID: iaor20072271
Country: United Kingdom
Volume: 33
Issue: 10
Start Page Number: 3015
End Page Number: 3033
Publication Date: Oct 2006
Journal: Computers and Operations Research
Authors: ,
Keywords: programming: multiple criteria, heuristics
Abstract:

This paper presents a bicriterion analysis of time/cost trade-offs for the single-machine scheduling problem where both job processing times and release dates are controllable by the allocation of a continuously nonrenewable resource. Using the bicriterion approach, we distinguish between our sequencing criterion, namely the makespan, and the cost criterion, the total resource consumed, in order to construct an efficient time/cost frontier. Although the computational complexity of the problem of constructing this frontier remains an open question, we show that the optimal job sequence is independent of the total resource being used; thereby we were able to reduce the problem to a sequencing one. We suggest an exact dynamic programming algorithm for solving small to medium sizes of the problem, while for large-scale problems we present some heuristic algorithms that turned out to be very efficient. Five different special cases that are solvable by using polynomial time algorithms are also presented.

Reviews

Required fields are marked *. Your email address will not be published.