Time/cost trade-offs in machine scheduling

by

Sinan Gürel
Bilkent University

In the scheduling literature, controllable processing time concept has received limited attention, however duration controllability is possible for most of the activities that we can see in practice. Making appropriate processing time decisions is very critical for scheduling problems since the regular scheduling performance measures are very sensitive to processing time data. Similarly, processing time decisions also affect the processing costs since decreasing the processing times usually requires using additional resources. In this study, we consider the tradeoff analysis between total weighted completion time and total machining cost on a single CNC turning machine for a given set of jobs. We propose an efficient formulation for the minimization problem of total machining cost subject to a total weighted completion time constraint. We deduce some optimality properties for this problem and use these properties to develop an effective algorithm which generates an approximate efficient solution set. Our computational results indicate that the deviation of the proposed algorithm from a solution found by the commercial solver MINOS is about 0.02% while the average computational times is only 0.07% of the time required by MINOS.