Algorithm to Minimize Total Spanding Time on Parallel machine
-
摘要: 讨论了将多个零件分派给并行加工系统加工的排序问题.假设同一零件分配给不同的设备,其加工时间不同,分析了使所有零件的总花费时间(加工时间与等待时间之和)最小的排序方法.首先建立了该类问题的数学模型,然后将其转化为指派问题,通过匈牙利算法可以得到最优解.所得算法的时间复杂性是多项式界的.最后给出了一个数值例子说明求解过程.Abstract: The problem of scheduling of a set of jobs on parallel machines is discussed.An algorithm to minimize the total spanding time (processing time plus waiting time) is described,in which processing time of a job can be different on different machines.The mathematical model of this problem is set up.The scheduling problem can be transformed into assignment problem,and the optimization solution can be obtained by Hungarian algorithm.The time complexity of the presented method is a polynomial bound scheduling algorithm.In the end a numerical example is given to explain the solution process.
-
Key words:
- parallel processing /
- sequencing /
- optimization algorithms /
- assignment problem
-
1. 常庆龙.排序问题浅谈.数学通报,1979(3):22~25 2. 常庆龙.一类排序问题的最优解.数学的实践与认识,1987(3):28~33 3. 菲利普斯著.运筹学的理论与实践.刘泉,方敏译.北京:中国商业出版社,1987 -
点击查看大图
计量
- 文章访问数: 2867
- HTML全文浏览量: 39
- PDF下载量: 1082
- 被引次数: 0
下载:
