Scheduling parallel CNC machines with time/cost trade-off considerations

Gürel, Sinan
Akturk, M. Selim
When the processing times of jobs are controllable, selected processing times affect both the manufacturing cost and the scheduling performance. A well-known example for such a case that this paper specifically deals with is the turning operation on a CNC machine. Manufacturing cost of a turning operation is a nonlinear convex function of its processing time. We also know that scheduling decisions are quite sensitive to the processing times. Therefore, this paper considers minimizing total manufacturing cost (F-1) and total completion time (F-2) objectives simultaneously on identical parallel CNC turning machines. Since decreasing processing time of a job increases its manufacturing cost, we cannot minimize both objectives at the same time, so the problem is to generate non-dominated solutions. We consider the problem of minimizing F-1 subject to a given F2 level and give an effective formulation for the problem. For this problem, we prove some optimality properties which facilitated designing an efficient heuristic algorithm to generate approximate non-dominated solutions. Computational results show that proposed algorithm performs almost equal with the GAMS/MINOS commercial solver although it spends much less computation time.

Citation Formats
S. Gürel and M. S. Akturk, “Scheduling parallel CNC machines with time/cost trade-off considerations,” COMPUTERS & OPERATIONS RESEARCH, vol. 34, no. 9, pp. 2774–2789, 2007, Accessed: 00, 2020. [Online]. Available: