具有分段恶化效应生产过程的智能优化调度研究

发布时间：2018-07-17 15:02

【摘要】：调度问题旨在将有限的资源分配给各项不同的任务,同时满足特定的需求和约束,其广泛存在于各类生产制造系统中。生产调度是制造系统中关键的决策过程之一,对其进行优化是车间管理的主要研究内容。采用合理的调度方案安排生产是提高制造系统作业效率的有效手段。在传统的生产调度问题中,通常认为工件的加工时间固定不变。然而在某些实际制造和服务过程中,工件的加工时间会因其开工时刻、加工位置的不同而发生变化,与传统调度问题相比生产过程具有恶化效应,由此产生了一类新的调度问题。该类问题中工件的加工时问由开工时刻、加工位置等因素的函数描述。若工件的加工时间由其开工时刻的分段线性函数和阶梯函数刻画,则称其具有分段恶化效应。此类问题较之传统调度问题更加复杂,绝大多数是NP-hard的,通常无法在合理的时间内求得最优解,对这类调度问题设计有效的调度优化方法具有重要的理论和现实意义。本文研究了分段线性恶化和阶梯恶化这两类效应作用下的四个生产调度问题,给出了它们的复杂性分析。由于这些问题均是NP-hard的,难以在多项式时间内获得最优解,为此基于最优调度方案的结构特征和性质分析,设计了启发式调度优化算法。论文的主要研究内容有：(1)研究了分段线性恶化效应作用下以最大完工时间最小化为目标的单机调度问题。此问题是强NP-hard的,无法通过多项式算法求解。在最优解的结构特征分析的基础上,提出了基于SPT排序规则的启发式算法DSPT-PI,同时引入了遗传算法以获得更高质量的解。该遗传算法使用DSPT和随机序列相结合的方式产生初始种群,采用线性顺序交叉算子和交换变异算子,并融入了成对互换搜索。基于随机数值算例的仿真结果表明,启发式算法DSPT-PI总体求解性能明显好于已有的启发式算法,遗传算法的求解精度优于模拟退火算法。(2)对于具有阶梯恶化效应的单机调度问题,研究了总延误及总加权延误两种目标函数。针对该问题,建立了混合整数规划模型,证明了总延误最小化问题为NP-hard的,分析了最优解的性质,设计了基于修正交货期的启发式算法IMDD和简单加权搜索算法SWSP。同时还证明了总加权延误最小化问题为强NP-hard的,提出了通用变邻域搜索算法GVNS进行求解。利用随机算例对算法的性能进行了评估,分析发现GVNS能够有效地求解该问题,当求解大规模问题时给出的解的相对百分偏差为0.78%,相对平均偏差为0.81%。(3)研究了具有阶梯恶化效应的并行机调度问题,构建了以总完工时间最小化为目标函数的混合整数规划模型,研究了不同建模方式下优化模型的求解效率。针对该问题,提出了改进加权组合搜索算法MWCSA,并设计了基于工件序列编码的变邻域搜索算法VNS。同时为了提高搜索速度,利用MWCSA为VNS产生初始解以形成改进算法VNS+MWCSA。基于随机算例的大量仿真结果表明,混合整数规划模型的求解效率依赖于恶化工期的取值区间,VNS+MWCSA算法的性能优于其他算法。(4)研究了带调整时间和阶梯恶化效应的并行机调度问题,以最小化总延误为目标函数,建立了混合整数规划模型。针对该问题,提出了一种混合离散布谷鸟搜索(HDCS)算法。该算法采用基于工件排列的离散编码解码方案,在种群初始化过程中融合了启发式算法MBHG,在搜索过程中将种群划分为普通解集和精英解集,对普通解实施基于CS的离散搜索,对精英解实施基于变邻域下降的局部搜索。为了保持种群的多样性,对部分个体采用了Restarting策略。算例求解结果表明混合算法HDCS是十分有效的,其求解效率受恶化工期取值的影响极小。本文针对分段恶化效应作用下的生产过程,以单机和同速并行机为加工环境,考虑了最大完工时间、总延误和总完工时间为优化指标的调度模型,并提出了相应的求解方法。本文的研究丰富了具有恶化效应调度问题的研究内容,拓宽了此类问题的求解途径,有助于推动生产调度理论的发展,具有重要的理论意义和积极的实际意义。
[Abstract]:Scheduling problem is designed to allocate limited resources to different tasks and meet specific requirements and constraints. It is widely used in all kinds of manufacturing systems. Production scheduling is one of the key decision-making processes in the manufacturing system. Optimization is the main research content of workshop management. Production is an effective means to improve the efficiency of the manufacturing system. In the traditional production scheduling problem, the processing time of the workpiece is usually fixed. However, in some actual manufacturing and service processes, the processing time of the work piece will vary with the start time and the processing position, and the production process is compared with the traditional scheduling problem. A new kind of scheduling problem is produced. In this kind of problem, the processing time of the workpiece is described by the function description of the factors such as the start time and the machining position. If the processing time of the workpiece is depicted by the piecewise linear function and the ladder function at the start time of the work piece, it is called the piecewise deterioration effect. This kind of problem is compared with the traditional scheduling problem. The problem is more complex, most of which are NP-hard, usually can not obtain the optimal solution in a reasonable time. It is of great theoretical and practical significance to design an effective scheduling optimization method for this kind of scheduling problem. This paper studies four production scheduling problems under the action of piecewise linear deterioration and ladder deterioration, and gives it. Because these problems are all NP-hard, it is difficult to obtain the optimal solution in polynomial time. Therefore, based on the structural characteristics and properties of the optimal scheduling scheme, a heuristic scheduling optimization algorithm is designed. The main contents of this paper are as follows: (1) the maximum completion time under the effect of piecewise linear deterioration is studied. A single machine scheduling problem is minimized as a target. This problem is strong NP-hard and can not be solved by polynomial algorithm. Based on the analysis of the structural features of the optimal solution, a heuristic algorithm DSPT-PI based on the SPT ordering rule is proposed, and the genetic algorithm is introduced to obtain a higher qualitative solution. The genetic algorithm uses DSPT and random sequence. The initial population is generated by the combination of the linear sequence crossover operator and the exchange mutation operator. The simulation results based on the random numerical example show that the overall solution performance of the heuristic algorithm DSPT-PI is better than the existing heuristic algorithm, and the accuracy of the legacy algorithm is better than that of the simulated annealing algorithm (2). For the single machine scheduling problem with staircase degradation, two objective functions of total delay and total weighted delay are studied. A mixed integer programming model is established for this problem. It is proved that the problem of minimizing the total delay is NP-hard. The properties of the optimal solution are analyzed, and the heuristic algorithm IMDD and simple weighting for the base Yu Xiuzheng delivery period are designed. The search algorithm SWSP. also proves that the total weighted delay minimization problem is strong NP-hard. A general variable neighborhood search algorithm GVNS is proposed to solve the problem. The performance of the algorithm is evaluated by a random example. It is found that the GVNS can solve the problem effectively. The relative percentile deviation of the solution is 0. when the problem of the large norm model is solved. 78%, the relative average deviation is 0.81%. (3), the parallel machine scheduling problem with staircase degradation is studied. A mixed integer programming model is built to minimize the total completion time as the objective function. The efficiency of the optimization model is studied under different modeling methods. An improved weighted combination search algorithm (MWCSA) is proposed and the design of the improved weighted combination search algorithm is proposed. In order to improve the search speed based on the sequence coding of the work piece, VNS., in order to improve the search speed, produces an initial solution for VNS by MWCSA to form an improved algorithm, which is based on a large number of simulation results based on random examples. The efficiency of the mixed integer programming model is dependent on the value interval of the deteriorating period, and the performance of the VNS+MWCSA algorithm is excellent. In other algorithms (4) the parallel machine scheduling problem with adjustment time and staircase degradation is studied. In order to minimize the total delay as the objective function, a mixed integer programming model is established. A hybrid discrete cuckoo search (HDCS) algorithm is proposed for this problem. In the process of group initialization, the heuristic algorithm MBHG is fused. In the search process, the population is divided into common solution set and elite solution set. CS based discrete search is applied to ordinary solutions, and local search based on variable neighborhood descent is implemented for the elite solution. In order to maintain the diversity of the population, some individuals are used in Restarting strategy. The results show that the hybrid algorithm HDCS is very effective and its efficiency is very little affected by the time of the deteriorating work. In this paper, a scheduling model with the maximum completion time, the total delay and the total completion time is considered, and the corresponding scheduling model is taken into consideration in the production process under the effect of piecewise deterioration effect. The research in this paper enriches the research content of the problem of deteriorating effect scheduling, broadens the way to solve such problems, and helps to promote the development of production scheduling theory, which has important theoretical significance and positive practical significance.
【学位授予单位】：西南交通大学
【学位级别】：博士
【学位授予年份】：2014
【分类号】：TB497

【参考文献】