【作者】 张亚玲；

【导师】 陈华平；

【作者基本信息】 中国科学技术大学 ， 管理科学与工程， 2010， 硕士

【摘要】 生产调度是一类重要的组合优化问题,在工业生产、制造系统等领域应用广泛。合理的调度方案有助于提高生产效率,减少生产成本,因此对调度问题研究有着重要的现实意义。批调度是调度问题的一个重要分支。不同于经典调度问题,在批调度模型中,一台机器可以同时处理多个工件。差异工件批调度问题(Batch Processing Machines with Non-identical Job Sizes,NSBM)是对传统批调度问题的进一步扩展,即工件尺寸不同,且同一批中工件的总尺寸不能超过批的容量限制。邻域搜索算法是求解组合优化问题的一类重要优化方法,这类算法以进化的方式在解空间中进行寻优,具有简单、适用范围广和鲁棒性强等。本文将一种新的邻域搜索算法——自由搜索算法(Free Search,FS)应用于NSBM问题,主要工作如下:首先,充分利用工件序列这一启发信息求解NSBM问题,即首先采用FS算法寻找一个较优的工件序列,然后将该工件序列按一定的启发式规则进行分批。论文针对生产调度问题的离散性,设计了向量形式的编码方式,并结合改进的Best-Fit启发式分批规则,构造了工件序列编码的自由搜索算法。根据本文的目标函数,对算法模型中的信息素重新定义,并设置三类不同数值的邻域半径,避免算法陷入局部最优。实验表明,FS的求解效果优于现有的启发式算法和智能算法。其次,利用批序列的编码方式求解NSBM问题,即直接构造批,然后用邻域搜索算法对批序列优化。工件序列编码的方法在求解问题时结果会受到所选用的启发式分批规则的影响,若分批规则求解效果不好,则工件序列优化对结果的改进也很有限,且该方法不能在完备的解空间中寻优,不利于找到更好的解。论文提出了一种混合邻域搜索算法(Hybrid Neighborhood Search,HNS),根据FS算法在搜索过程中存在的停滞问题,加入差异演化算法和局部优化策略,并利用尖点灾变理论的精英保留机制进一步提高搜索效率,仿真实验验证了HNS算法的有效性。最后,对全文进行了总结,讨论了进一步的研究方向和设想。更多还原

【Abstract】 Scheduling is one of the most important combinatorial optimization problems. It is very important in industrial production, manufacturing systems and other fields. A reasonable scheduling scheme can improve production efficiency and reduce production costs,so the research on it has important practical significant.Batch scheduling is an important branch of scheduling problems. Different from the classical ones, a number of jobs can be processed simultaneously by a batch machine. Batch scheduling problem with non-identical jobs sizes (NSBM), in which the jobs are non-identical in size and the total size of the jobs in a batch cannot exceed the capacity of the machine, is an extension of batch scheduling problem.Neighborhood search algorithm is significant method of solving combinatorial optimization problems. Running as evolution in the solution space, it is simple, generic and robust. A novel algorithm called Free Search (FS) is firstly applied to solve the scheduling problems on NSBM in this paper. The main work is as follows: First, solving the problem based on the sequence of jobs. FS is used to search a superior jobs’sequence, then batching according to heuristic rules. A coding approach with vectors is designed due to the discrete of scheduling problems. A heuristic was then combined with FS and then an algorithm based on the sequence of jobs is constructed. By the features of NSBM, the pheromone in the model is redefined and three different values of radius are set to avoid premature convergence. Experiments show that FS is better than the previous method.Secondly, solving the problem based on the sequence of batches. Batching directly, and then optimizing the sequence of batches by an algorithm. The results of the method based on the sequence of jobs will be affected by the heuristic algorithms. If the heuristic algorithms perform not well, the improvement of results based on the optimization of the sequence of jobs. Even the space is shrinking by that method and it isn’t conducive to search a better solution. A Hybrid Neighborhood Search is proposed to solve NSBM. In order to avoid stagnation of FS, we apply Differential Evolution and local optimal strategy to modify the algorithm. At last, cusp catastrophe theory is used as elitist reserving mechanism. Computational results are presented to show the better search ability of the algorithm, and testify the validity of HNS. Finally, sum up the thesis, and give some further ideas and future research prospects.更多还原