基于分枝界限法的开放车间调度问题的研究

发布时间：2018-06-21 21:32

本文选题：调度 + 开放车间　；参考：《沈阳工业大学》2012年硕士论文

【摘要】：车间调度问题作为制造系统优化的核心问题之一,一直受到人们的广泛关注。开放车间调度问题是生产调度问题中一个非常重要的课题,是学术上熟知的困难度极高的组合最优化问题。因而,在应用领域也受到人们的广泛关注。在实际的工业环境中,加工一个工作之前往往要做一些准备。通常,所做准备的时间长短取决于两个连续工作之间的顺序。这种情况下,所做的准备叫做顺序决定的准备。本文是利用分枝界限法以最小化制造期为优化目标,求解顺序决定准备时间的开放车间调度问题。调度问题在求最优解时,往往利用分枝界限法作为求解方法。但是求最优解时,因为求解过程非常复杂而且耗时多,所以在实际中的应用并不十分广泛,特别是当前,各类智能优化算法几乎成为调度算法的主流。然而,由于多数智能优化算法为随机优化算法,不能总是保证算法在每一次运行中解的质量,而且,算法运行过程中对于各类参数的选择、算法结束的条件等问题也难以得到一般化的规律。因此,研究分枝界限法等传统最优化方法依然有其重要的意义和价值。在分枝界限法中,设计良好的上限值和下限值是获得最优解的关键。因为上限值和下限值的品质越好,就可以删除很多无用的分枝节点,进而加快求解的速度。本文提出几个上下限值算法,可得到相当优的解,但尚无一个良好的删除法则,故而仍然要浪费很多时间在无用的分枝节点上。通过实例验证比较了几个上限值算法的优劣,但实际应用中主要依赖于数据。最后,给出了未来的几点研究方向。
[Abstract]:As one of the core problems of manufacturing system optimization, job shop scheduling problem has been paid more and more attention. Open job shop scheduling problem is a very important problem in production scheduling problem, and it is also an extremely difficult combinatorial optimization problem. Therefore, in the application field also receives the widespread concern. In a practical industrial environment, some preparation is often required before processing a job. Usually, the length of preparation depends on the order between the two consecutive tasks. In this case, preparation is called sequential preparation. In this paper, the branch and bound method is used to solve the open job shop scheduling problem with the aim of minimizing the manufacturing period and determining the preparation time in order. In order to find the optimal solution, the branching and bound method is often used to solve the scheduling problem. However, because the process of solving the optimal solution is very complex and time-consuming, it is not widely used in practice, especially at present, all kinds of intelligent optimization algorithms almost become the mainstream of scheduling algorithms. However, because most of the intelligent optimization algorithms are random optimization algorithms, the quality of the solution can not always be guaranteed in each operation. Moreover, the selection of various parameters during the operation of the algorithm can not always be guaranteed. It is also difficult to obtain a general rule for the condition of the end of the algorithm. Therefore, the study of traditional optimization methods such as branching and bound method still has important significance and value. In the branching and bound method, well designed upper and lower limit values are the key to obtain the optimal solution. Because the better the quality of upper limit and lower limit, many useless branch nodes can be deleted, and the speed of solution can be accelerated. In this paper, several upper and lower limit algorithms are proposed, which can obtain a fairly good solution, but there is not a good deletion rule, so we still have to waste a lot of time on the useless branch nodes. The advantages and disadvantages of several upper bound value algorithms are verified and compared by an example, but the actual application mainly depends on the data. Finally, some research directions in the future are given.
【学位授予单位】：沈阳工业大学
【学位级别】：硕士
【学位授予年份】：2012
【分类号】：TH186

【参考文献】