Ant colony optimization for unrelated parallel machine scheduling

作者：Lin Chi Wei; Lin Yang Kuei^*; Hsieh Han Ting

来源：International Journal of Advanced Manufacturing Technology, 2013, 67(1-4): 35-45.

DOI：10.1007/s00170-013-4766-7

• Ant colony optimization
• Unrelated parallel machines
• Total weighted tardiness

Meeting due dates is a major issue in most manufacturing systems, and one effective measure for due dates is total weighted tardiness. In this research, we consider an ant colony optimization (ACO) algorithm incorporating a number of new ideas (heuristic initial solution, machine reselection step, and local search procedure) to solve the problem of scheduling unrelated parallel machines to minimize total weighted tardiness. The problem is NP-hard in the strong sense, because the single machine case is already NP-hard in the strong sense. Computational results show that the proposed ACO algorithm outperforms other existing algorithms in terms of total weighted tardiness.

• 出版日期2013-7