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

Creative Commons License

Gurel S., Akturk M. S.

COMPUTERS & OPERATIONS RESEARCH, vol.34, no.9, pp.2774-2789, 2007 (SCI-Expanded) identifier identifier

  • Publication Type: Article / Article
  • Volume: 34 Issue: 9
  • Publication Date: 2007
  • Doi Number: 10.1016/j.cor.2005.10.018
  • Journal Indexes: Science Citation Index Expanded (SCI-EXPANDED), Scopus
  • Page Numbers: pp.2774-2789
  • Keywords: parallel machine scheduling, controllable processing times, CNC machines, manufacturing cost, total completion time, CONTROLLABLE PROCESSING TIMES, SINGLE-MACHINE, FLOW-TIME, COST
  • Middle East Technical University Affiliated: No


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. (c) 2005 Elsevier Ltd. All rights reserved.