差异工件机器批调度若干问题研究
发布时间：2018-03-12 21:52
本文选题：调度 切入点：批处理机 出处：《中国科学技术大学》2016年博士论文 论文类型：学位论文
【摘要】：不同于传统加工机器,批处理机器一次能够加工一批多个工件(或作业)。批处理机在生产企业中具有广泛的应用,包括电子芯片厂、钢铁企业、航空工业等。合理地调度批处理机的加工任务,能够有效地提高企业的生产效率,降低生产成本。因此,研究批处理机调度(简称批调度)问题不但具有重要的理论价值,还具有迫切的现实意义。不同尺寸的工件(简称差异工件)是一个常见于制造车间的现实约束。而早期的研究大都假设上件具有相同的尺寸(即单位尺寸)。本论文研究不同尺-寸工件机器批调度问题。相比相同尺寸的情形,本文问题是更一般也更为复杂的调度问题,它兼具排序问题和装箱问题的双重性质。本文的主要研究上作和创新点如下：(1)研究了工件具有不同尺寸和任意到达时间的单机批调度问题。问题的目标函数为最小化制造跨度。该问题属于NP-hard问题。首先,我们提出了本问题的两个下界,并证明了下界的有效性。其次,我们从一种新的角度提出了若干种启发式构造型算法。在制定分批的决策中,工件的加工时间和到达时间常常是两个相互矛盾的因素。这也正是研究本问题的一个难点。因此,现有的算法在分批过程中往往只考虑了某一个因素的影响。然而,我们提出的算法在分批时试图兼顾加工时间和到达时间两个因素的作用。第一,我们提出了距离矩阵的概念：第二,我们设计了若干种基于距离矩阵的构造型算法,用于将工件分批；然后,我们采用已有的批排序算法ERT规则,用于安排批在机器上的加工。大量的仿真实验比较了我们的算法和现有的求解方法。实验结果证明了本文下界以及启发式算法的有效性。(2)研究了一类两阶段流水车间批调度问题,考虑不同的工件尺寸、任意到达时间、以及阻塞约束。优化目标为最小化制造跨度。首先,我们对这一问题建立了混合整数规划模型。然后,提出了一种混合的离散差分进化算法。在提出的算法中,个体采用离散的工件序列编码。然后,基于该编码方式,设计新颖的变异和交叉算子。接着,我们使用first-fit规则将工件分批；并提出一种新的最小闲置/阻塞时间算法,用来安排批在车间里的加工次序。为了进一步改进求解质量,一种局部搜索算法被集成到差分进化算法当中。仿真实验证实了所提出算法在解质量、鲁棒性以及计算时间方面的优异性。(3)考察了差异工件两类批处理机的流水车间调度问题。两阶段各包含一台批处理机。第一台机器为并行批处理机,第二台为串行批处理机。优化口标为最小化制造跨度。我们对该问题建立了混合整数规划模型。然后,我们提出了一种基于种群的进化算法-分布估计算法。在该分布估计算法中,个体被编码成工件序列。接着,构造一种概率模型以抽样产生新个体,并提出一种增量学习型方法以更新概率模型。我们采用best-fit规则对工件分批,并提出一种最小闲置/等待时间算法,以排列批的加工次序。为了进一步改进算法的求解质量,两种局部搜索算法被嵌入到该分布估计算法当中。计算机实验表明了该分布估计算法在解质量与鲁棒性方面的有效性。
[Abstract]:Different from the traditional processing machine, a batch machine can process a batch of jobs (or operation). Batch processor is widely used in the production of enterprises, including electronic chip factory, iron and steel enterprises, aviation industry and other processing tasks reasonably. Scheduling of batch processing, can effectively improve the production efficiency of enterprises and reduce the production cost. Therefore, study on batch scheduling (the batch scheduling problem) not only has important theoretical value, but also has the realistic meaning. The workpieces with different sizes (the different workpiece) is a common in cars between real constraints. The early studies on a hypothesis with the same dimensions (the unit size). This paper studies the different scale - Inch workpiece machine batch scheduling problem. Compared with the same size of the case, the problem is more general and more complex scheduling problems, and it has sorting and packing The dual nature of the problem. This paper mainly studies on the work and innovation are as follows: (1) study the workpiece with different size and arrival time of any single batch scheduling problem. The objective function of the problem is to minimize the make span. The problem is a NP-hard problem. First, we present two lower bounds for this problem, and prove the validity of the lower bound. Secondly, we put forward some constructive heuristic algorithm from a new angle. In the formulation of batch decision-making, the processing time and arrival time are two contradictory factors. This is also a difficult problem in this research. Therefore, the existing the algorithm in batch process often only consider the influence of one factor. However, our proposed algorithm attempts to balance the processing time and arrival time of the two factors in batch. First, we propose a distance matrix 姒傚康锛氱浜，
本文编号：1603442
本文链接：https://www.wllwen.com/shoufeilunwen/xxkjbs/1603442.html
