【作者】 程八一；

【导师】 陈华平；

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

【摘要】 差异工件的单机批调度问题,具有古典调度和批调度的双重性质,在实际生产中有着广泛的应用;在计算复杂性方面,单机的制造跨度最小化问题为强NP-hard,加权完工时间最小化问题为NP-hard,单机问题的高复杂性对优化算法提出了挑战。因此对差异工件单机批调度问题的研究具有重要的现实意义和理论价值。本文首先对确定性单机问题进行求解,针对单机问题复杂度高、可行解数量大的特点,设计了有效的优化算法。然后将单机问题扩展到更接近现实情形的模糊环境中,建立模糊调度模型,并设计了求解模糊问题的优化算法。本文的主要工作和创新点如下:(1)研究了蚁群算法(Ant Colony Optimization,ACO)在差异工件单机批调度问题中的应用。设计了高效的编码和解码方法;为了解决蚁群算法易陷入局部最优的问题,本文引入了Metropolis准则的概率选择机制作为路径激励策略,避免了由于路径重复而造成的局部最优;仿真实验验证了改进算法的有效性。另一方面,本文采用了混沌优化算子,将混沌优化的全局性能嵌入蚁群算法中,有效改进了解的质量。(2)研究了微粒群算法(Particle Swarm Optimization,PSO)在差异工件单机批调度问题中的应用。首先设计了微粒的编码方法;然后采用了基于优先值向量的排序方法对微粒进行解码,有效的利用了微粒群算法在离散优化中的优势;最后利用批调度策略进行分批处理,获得优秀的可行解。(3)研究了DNA进化算法(DNA Evolution Algorithm,DEA)在差异工件单机批调度问题中的应用。引入了分裂、水平选择、变异、垂直选择四种算子,对垂直选择算子进行了重新设计。充分利用了DNA进化算法实现简单、时间性能好的优势;同时,设计了随机选择机制对变异个体进行选择,使得求解过程能够跳出局部极值,实现全局优化。仿真实验的结果表明改进的DNA进化算法是有效的。(4)研究了在模糊环境下的差异工件单机批调度问题。在现实生产过程中,加工信息的不确定性存在于两个方面:工件在批中的加工时间和批的间隔时间。因此本文将NSBM问题从上述研究的理想环境拓展到更接近现实情况的模糊环境中,建立了基于模糊数的制造跨度模型。在此基础上,设计了基于微粒群算法和差异演化的混合优化算法,获得了满意的实验结果。更多还原

【Abstract】 The scheduling of a single batch-processing machine with non-identical job sizes is widely used in the real manufacturing and the problems of this kind are integrated with the characteristics of the classical scheduling and the batch scheduling.The problems of minimizing the makespan and the weighted completion time of a single machine are respectively strongly NP-hard and NP-hard.The optimization of a single batch-processing machine with non-identical job sizes has an influence on the industry and theoretical research.In this paper,intelligent algorithms are applied to solve the problems on a single batch-processing machine with non-identical job sizes and then,the deterministic problems are extended to fuzzy environment and algorithms are designed for the optimization of the fuzzy problems.The main innovations of this paper are listed as follows.(1) The ant colony optimization(ACO) method is studied and designed for a single batch-processing machine with non-identical job sizes(NSBM).The coding and decoding mechanism of ACO is improved and in order to conquer the local optimum of ACO,the Metropolis criterion is adopted as the selection method of the paths to solve the problem.The simulation results demonstrate the efficiency of the algorithm.Additionally,the chaotic optimizer is introduced to improve the quality of ACO.(2) The particle swarm optimization method(PSO) is applied to NSBM.Firstly the coding approach is designed and then the particles are sequenced using the priority value vectors which make PSO appropriate for the discrete optimization problem.In the decoding section,the feasible solutions are produced with batch scheduling mechanism.(3) DNA evolutionary algorithm(DEA) is applied to the problem.The operators of division,level selection,mutation and vertical selection are introduced.DEA has a simple implementation and an outstanding time performance.Additionally,the vertical selection operator is improved by integrating a random selection method. An effective global optimization is achieved by jumping from the local optimum. The numerical results demonstrate the efficiency of DEA.(4) The NSBM in fuzzy manufacturing system is studied in this paper.In the real industry,the uncertainty lies in two factors which consist of the processing time of the batches and the intemals between the batches.The NSBM is extended from the current ideal environment to fuzzy environment and the fuzzy model of minimizing the makespan is established.A hybrid algorithm based on different evolution(DE) and PSO is proposed for the optimization.The simulation results show the good performance of the method.更多还原