| 工件带安装时间平行机排序问题的列生成算法 |
| |
| 引用本文： | 樊保强,唐国春. 工件带安装时间平行机排序问题的列生成算法[J]. 同济大学学报(自然科学版), 2006, 34(5): 680-683,693 |
| |
| 作者姓名： | 樊保强 唐国春 |
| |
| 作者单位： | 1. 同济大学,应用数学系,上海,200092
2. 同济大学,应用数学系,上海,200092;上海第二工业大学,管理工程研究所,上海,201209 |
| |
| 基金项目： | 中国科学院资助项目;国家自然科学基金;上海市教委资助项目 |
| |
| 摘 要： | 研究了工件带与加工次序有关的安装时间的平行机排序问题，给出它的整数规划模型，并结合动态规划和分支定界方法，给出它的列生成算法．通过试验表明：算法对中等规模的问题是有效的，它可以计算到10台机器和60个工件甚至含有更多大工件的大规模问题．
|
| 关 键 词： | 平行机排序 列生成 动态规划 分支定界 |
| 文章编号： | 0253-374X（2006）05-0680-04 |
| 收稿时间： | 2005-03-30 |
| 修稿时间： | 2005-03-30 |
A Column Generation for a Parallel Machine Scheduling with Sequence-Dependent Setup Times |
| |
| FAN Baoqiang,TANG Guochun. A Column Generation for a Parallel Machine Scheduling with Sequence-Dependent Setup Times[J]. Journal of Tongji University(Natural Science), 2006, 34(5): 680-683,693 |
| |
| Authors: | FAN Baoqiang TANG Guochun |
| |
| Affiliation: | 1. Department of Applied Mathematics, Tongji University, Shanghai 200092, China; 2. Institute of Management Engineering, Shanghai Second Polytechnic University, Shanghai 201209, China |
| |
| Abstract: | In this paper we address the problem of scheduling jobs on identical parallel machines with sequence- dependent setup times to minimize the total weighted completion times. This problem is complicated to such an extent that it is NP-hard in some special cases. We formulate the problem as an integer program, and a column generation algorithm is given then. Our computational results show that this column generation algorithm is capable of solving problems with up to 10 machines and 60 jobs in reasonable computational time. |
| |
| Keywords: | parallel machines scheduling column generation dynamic programming branch and bound |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
