摘要
ＪＳＳＰ（ＪｏｂＳｈｏｐＳｃｈｅｄｕｌｉｎｇＰｒｏｂｌｅｍ）问题可分解为２个部分：一部分是求解加工周期；一部分是寻找具有最小加工周期的序．目前关于研究加工车间的作业排序问题ＪＳＳＰ的文献都把注意力集中在如何设计一种算法快速地找到一种排序使得所有工件的总加工周期最小，却很少对求解总加工周期的算法进行讨论．本文给出了几种不同的求解总加工周期的基本算法和数据结构，并较详细地分析了各个算法的时间复杂性及结果的差异性，对于求解较大规模加工车间的作业排序问题有一定的参考价值．
JSSP(Job Shop Scheduling Problem) is a well known NP hard problem. In this paper the JSSP is divided into two parts: one for calculating the makespan, the other for finding a scheduling which has the minimum makespan. Up to now the papers published are all focused on how to find an algorithm for finding the schedule that has minimum makespan quickly. Seldom papers talk about a related topic, that is the algorithm for calculating the makespan.Several algorithms are shown and discussed for that purpose in detail.The experimental result shows that there is a big difference among the speed of these algorithms. The analysis also indicates that the difference realization of algorithms may cause different result, even the wrong result. From the experiment and analysis, it can be seen that the speed of parallel simulation clock advance algorithm is the fastest. It is very useful for some iterative algorithm such as genetic algorithm for finding the schedule that has minimum makespan.
出处
《北京航空航天大学学报》
EI
CAS
CSCD
北大核心
1999年第2期208-211,共4页
Journal of Beijing University of Aeronautics and Astronautics
基金
国家自然科学基金
航空科学基金
关键词
最优化算法
加工车间
作业排序
加工周期
sequencing
optimization algorithms
simulation
job shop scheduling problem
makespan
