| An Improved Ant Colony Algorithm for a Single-machine Scheduling Problem with Setup Times |
| |
| 引用本文： | YE Qiang LIU Xinbao LIU Lin YANG Shanglin School of Management,Hefei University of Technology,Hefei 230009,China. An Improved Ant Colony Algorithm for a Single-machine Scheduling Problem with Setup Times[J]. 武汉理工大学学报, 2006, 0(Z3) |
| |
| 作者姓名： | YE Qiang LIU Xinbao LIU Lin YANG Shanglin School of Management Hefei University of Technology Hefei 230009 China |
| |
| 作者单位： | YE Qiang LIU Xinbao LIU Lin YANG Shanglin School of Management，Hefei University of Technology，Hefei 230009，China |
| |
| 摘 要： | Motivated by industrial applications we study a single-machine scheduling problem in which all the jobs are mutu- ally independent and available at time zero.The machine processes the jobs sequentially and it is not idle if there is any job to be pro- cessed.The operation of each job cannot be interrupted.The machine cannot process more than one job at a time.A setup time is needed if the machine switches from one type of job to another.The objective is to find an optimal schedule with the minimal total jobs'completion time.While the sum of jobs'processing time is always a constant,the objective is to minimize the sum of setup times.Ant colony optimization(ACO)is a meta-heuristic that has recently been applied to scheduling problem.In this paper we propose an improved ACO-Branching Ant Colony with Dynamic Perturbation(DPBAC)algorithm for the single-machine schedul- ing problem.DPBAC improves traditional ACO in following aspects:introducing Branching Method to choose starting points;im- proving state transition rules;introducing Mutation Method to shorten tours;improving pheromone updating rules and introduc- ing Conditional Dynamic Perturbation Strategy.Computational results show that DPBAC algorithm is superior to the traditional ACO algorithm.
|
An Improved Ant Colony Algorithm for a Single-machine Scheduling Problem with Setup Times |
| |
| YE Qiang LIU Xinbao LIU Lin YANG Shanglin School of Management,Hefei University of Technology,Hefei ,China. An Improved Ant Colony Algorithm for a Single-machine Scheduling Problem with Setup Times[J]. Journal of Wuhan University of Technology, 2006, 0(Z3) |
| |
| Authors: | YE Qiang LIU Xinbao LIU Lin YANG Shanglin School of Management Hefei University of Technology Hefei China |
| |
| Affiliation: | YE Qiang LIU Xinbao LIU Lin YANG Shanglin School of Management,Hefei University of Technology,Hefei 230009,China |
| |
| Abstract: | Motivated by industrial applications we study a single-machine scheduling problem in which all the jobs are mutu- ally independent and available at time zero.The machine processes the jobs sequentially and it is not idle if there is any job to be pro- cessed.The operation of each job cannot be interrupted.The machine cannot process more than one job at a time.A setup time is needed if the machine switches from one type of job to another.The objective is to find an optimal schedule with the minimal total jobs'completion time.While the sum of jobs'processing time is always a constant,the objective is to minimize the sum of setup times.Ant colony optimization(ACO)is a meta-heuristic that has recently been applied to scheduling problem.In this paper we propose an improved ACO-Branching Ant Colony with Dynamic Perturbation(DPBAC)algorithm for the single-machine schedul- ing problem.DPBAC improves traditional ACO in following aspects:introducing Branching Method to choose starting points;im- proving state transition rules;introducing Mutation Method to shorten tours;improving pheromone updating rules and introduc- ing Conditional Dynamic Perturbation Strategy.Computational results show that DPBAC algorithm is superior to the traditional ACO algorithm. |
| |
| Keywords: | DPBAC algorithm ant colony optimization algorithm single-machine scheduling problem setup time |
| 本文献已被 CNKI 等数据库收录！ |
