New Scheduling Heuristic for the Permutation Flowshop Problem
-
摘要: 在生产调度中经常遇到工件排序问题,这类问题大多属于NP类问题.对此,目前无论在理论上还是在实际应用中,都尚未找到令人满意的一般求解方法.针对NP类问题中的一类——同顺序Flowshop排序问题,进行了广泛而深入的调查和比较研究,在此基础上,提出了一种新的启发式算法(简称为WSH法),并通过大量的数据实验将该算法与目前已知较好的几种算法进行了比较.结果表明,WSH法结构简单,计算效率高,是求解中、小规模问题的较好算法.
-
关键词:
- 排序 /
- 启发式算法 /
- 调度程序 /
- 同顺序Flowshop问题
Abstract: The permutation flowshop problem,which is a class of NP problems that are often encountered in scheduling of manufacturing systems,has not been completely solved either in theory or in application. A new heuristic method,named WSH,is proposed in this paper to solve the permutation flowshop problem. This heuristic aims to minimize the total process time of all jobs. The comparison between this method and others reported in literature until now,is presented on the basis of results from many numerical examples. The results show that WSH,simple in structure and excellent in computational efficiency,is a good method to solve small-size and medium-size problems.-
Key words:
- sequencing /
- heuristic approach /
- scheduler /
- permutation flowshop problem
-
1. 陈荣秋.排序的理论与方法.武汉:华中理工大学出版社,1987 2. Sarin S,Lefoka M.Scheduling heuristic for the n job m machine flowshop.Omega,1993,21(2):229-234 3. Germain R,Sriskan D C.A heuristic for job shop scheduling.IFAC Proceeding Series,1985 4. Palmer D S.Sequencing jobs through a multi stage process in the minimum total time——a quick method of obtaining a near optimum.Ops Res Q,1965,16:101~107 5. Dannenbring D G.An evaluation of flowshop sequencing heuristics.Mgmt Sci,1977,23:1174~1182 6. Campbell H G,Dudek R A,Smith M L.A heuristics algorithm for the n-job m-machine flowshop sequencing problem.Mgmt Sci,1970,16:B630~B637 7. 沈英俊.同顺序Flowshop排序问题的启发式算法研究:[学位论文].北京:北京航空航天大学管理学院,1996 -
点击查看大图
计量
- 文章访问数: 2967
- HTML全文浏览量: 37
- PDF下载量: 958
- 被引次数: 0
下载:
