具有释放时间的单机半连续型批处理机调度问题

发布时间：2018-06-17 13:31

本文选题：加热炉 + 半连续型批处理机　；参考：《沈阳师范大学》2012年硕士论文

【摘要】：半连续型批处理机调度问题是从钢铁工业加热炉对管坯加热的过程中提炼的，它的主要特征是工件按批加工，，工件必须按周期的进入和离开处理机，只有一批工件全部加工完才可以加工下一批的工件，同一批中工件的加工时间为此批工件中的最大加工时间。由于批中的工件是连续进、连续出的，所以批的容量即批的大小可以是无限的。又因为工件具有释放时间，所以在加工同批工件的过程中，存在有空位和无空位两种情况。本文从这两方面进行了研究，具体内容概括如下： 1.当同批工件加工过程中无空位产生，即工件按周期一个紧挨着一个进入和离开处理机时，本文主要从两个方面进行了理论研究：（1）为了提高机器的利用率，即对于目标函数是最大完工时间的调度问题，当工件的释放时间和加工时间同序时，分析其问题的最优解性质，给出一个计算复杂性为O ( n 2)的动态规划算法，证明了算法的最优性，并用数值例子进一步说明此算法。（2）当工件带权时，对于工件的加工时间相等的特殊情况，给出了目标函数是最大完工时间的调度问题的最优解性质；当工件的释放时间和权值逆序时，为了降低在制品的库存量，即目标函数是加权总完工时间的调度问题，分析了此问题的最优解性质，给出一个启发式算法，并用数值例子进一步解释此算法。 2.当工件加工过程中有空位产生时，工件有可利用性，机器也有可用性。对于目标函数是最大完工时间的问题，当工件的释放时间和加工时间同序时，讨论了其最优解性质，给出了一个启发式算法，并通过数值例子进一步说明此算法及有效性。
[Abstract]:The scheduling problem of semi-continuous batch processor is extracted from the heating process of tube billet in the heating furnace of iron and steel industry. Its main characteristic is that the workpiece is processed according to batch, and the workpiece must enter and leave the processor periodically. Only when one batch of jobs is finished can the next batch of jobs be machined. The processing time of the same batch of workpieces is the maximum processing time of the batch of workpieces. Because the workpiece in the batch is continuously in and out, the batch capacity, that is, the batch size, can be infinite. Because of the release time of the workpiece, there are two kinds of vacancy and no vacancy in the process of processing the same batch workpiece. This article has carried on the research from these two aspects, the concrete content summarized as follows: 1. When there is no vacancy in the machining process of the same batch of workpieces, that is, the workpieces enter and leave the processor one by one according to the cycle, this paper mainly carries out the theoretical research from two aspects: (1) in order to improve the utilization rate of the machine, That is, for the scheduling problem where the objective function is the maximum completion time, when the release time and the processing time of the workpiece are in the same order, the properties of the optimal solution of the problem are analyzed, and a dynamic programming algorithm with computational complexity O (N2) is given. The optimality of the algorithm is proved, and a numerical example is used to illustrate the algorithm. 2) when the workpiece is weighted, the processing time of the workpiece is equal. In this paper, we give the optimal solution of scheduling problem where the objective function is the maximum completion time, when the release time and weight value of the workpiece are reversed, in order to reduce the inventory of the WIP, that is, the objective function is the scheduling problem of the weighted total completion time. In this paper, the properties of the optimal solution of the problem are analyzed, and a heuristic algorithm is given, and a numerical example is given to explain the algorithm. When there is a vacancy in the machining process, the workpiece is available and the machine has availability. For the problem that the objective function is the maximum completion time, when the release time and the processing time of the workpiece are in the same order, the properties of the optimal solution are discussed, and a heuristic algorithm is given, and a numerical example is given to further illustrate the algorithm and its effectiveness.
【学位授予单位】：沈阳师范大学
【学位级别】：硕士
【学位授予年份】：2012
【分类号】：TH186

【参考文献】