【作者】 宫华；

【导师】 唐立新；

【作者基本信息】 东北大学 ， 系统工程， 2009， 博士

【摘要】 钢铁工业是国民经济的重要支柱产业之一。近年来,随着建筑业、汽车制造业、造船业和家电业的大力发展,对钢材的需求数量和质量提出了更高的要求。由于钢铁生产具有多阶段、物件带有高温连续运作、物流呈交叉网状结构等特点,这就决定了物件在工序上的生产调度、连接工序之间的运输物流调度以及生产和物流调度的衔接都有严格的要求。合理进行生产和物流调度,有利于钢铁工业工序之间的物料紧凑衔接、减少中间等待时间,从而降低能耗、提高大型装置的设备利用率,达到降低生产和物流的综合成本、提高产品质量、提高钢铁工业竞争力的目的。本文以钢铁企业的高能耗的炼钢和初轧为背景,分别从这两个工序中提炼出具有热链物流特征的生产和运输调度问题,进行理论研究。基于复杂性分析、算法最坏情况分析、多项式时间算法、近似策略、动态规划等多种技术手段,主要研究三个方面的问题：具有恶化特征的生产调度问题、生产和运输协调调度问题、考虑恶化特征的生产运输协调调度问题。具体内容概括如下：1)具有恶化特征的生产调度问题研究(1)从钢锭在均热炉中加热的过程中提炼出工件带有释放时间和恶化特征的批处理机调度问题,其中工件在批处理机上的加工时间是工件在批处理机前的等待时间的一个分段函数,目标函数为最大完成时间的最小化。证明了该问题是NP-难问题。分别从相同的释放时间、批处理机能力无限以及工件具有优先次序三个方面,研究了三种特殊情况的多项式时间算法。(2)从模铸到均热的生产过程提炼出了并行机和批处理机两阶段生产的恶化调度问题,其中工件的恶化是指工件在批处理机上的加工时间与工件在两阶段之间的等待时间有关。目标函数既考虑了两阶段生产的机器利用率,又考虑了批处理机的空载惩罚,即为最大完成时间和批处理机空余的惩罚费用之和的最小化。对于这个问题,证明了强NP-难性,提出了一个启发式算法,理论上分析了算法的最坏情况性能,并通过数值仿真实验,验证了算法性能的有效性。2)生产和运输协调调度问题研究(1)从钢锭的运输以及均热的过程受到启发,提炼出了多个台车生产前运输与批处理机生产的协调调度问题。目标函数为工件总完成时间与批处理机启动费用之和的最小化。首先利用划分问题证明了该问题是NP-难的,通过动态规划提出的伪多项式时间算法证明了该问题是一般意义NP-难问题。最后提出了解决问题的全多项式时间近似策略。而当工件在台车上的分配给定时,通过动态规划给出了多项式时间的最优算法。(2)从模铸到均热的生产和运输中提炼出了二机之间带有运输考虑的二机流水调度问题,其中在运输的过程中考虑工件是否占有不同的物理空间两种情况。目标函数为最大完成时间的最小化。对于工件体积相同的情况,给出了最坏情况性能比为2的启发式算法。对于工件体积不相同的情况,给出了最坏情况性能比为7/3的启发式算法。(3)从均热到初轧的生产过程提炼出了带有阻滞和运输时间考虑的两阶段生产调度问题,工件先在第一阶段批处理机上进行生产,当第二阶段的单机有空闲时才可以运输到第二阶段进行生产,如果单机不可利用,则批处理机上形成了阻滞。目标函数既考虑了工件的最大完成时间,又考虑了工件在批处理机上的总阻滞时间。对于总的阻滞时间的最小化问题,给出了多项式时间的最优算法。对于最大完成时间最小化问题,给出了强NP-难的证明,提出最坏情况性能比为2的启发式算法,实验结果证明了算法的有效性。对于最大完成时间和总阻滞时间的线性组合最小化问题,提出了混合整数规划模型,给出了强NP-难的证明,提出了启发式算法,并且从理论分析与实验结果两个方面验证了算法的有效性。(4)从初轧生产到成品运输的过程提炼出了并行机生产与成品运输的协调调度问题。目标函数为工件总完成时间与运输费用之和的最小化。根据问题所满足的性质,通过过程划分及动态规划给出了解决问题的伪多项式时间算法,并且证明该问题是一般意义NP-难问题。对于工件在并行机上的分配给定的特殊情况,提出了多项式时间的最优算法。(5)从钢锭在均热炉加热的前后生产过程提炼出了批处理机上生产与生产前后两阶段运输的协调调度问题。目标函数为工件的最大完成时间与批处理机启动费用之和的最小化。提出了问题的混合整数规划模型,给出了强NP-难证明。并且提出了最坏情况性能比为2的启发式算法,实验结果证明了算法的有效性。对于工件的加工次序确定的情况,给出了多项式时间的最优算法。3)考虑恶化特征的生产运输协调调度问题研究从均热车间中提炼出了工件生产前的运输以及批处理机生产的协调调度问题,其中也考虑了工件在批处理机的生产的恶化特征,这里的恶化是指工件在批处理机上的加工时间是关于工件的暴露时间的分段函数。目标函数为最大完成时间和批处理机的启动费用之和的最小化。证明了问题的一般情况以及批的数量受限的情况都是强NP-难问题,给出了启发式算法,并且进行了最坏情况性能比分析,实验结果也验证的算法的有效性。对于工件的完成时间受限的情况,证明了该问题也是强NP-难问题。对于工件的加工顺序给定的情况,给出了多项式时间最优算法。更多还原

【Abstract】 The iron and steel industry is one of the mainstay industries of the national economy. In recent years, along with the rapid develop of building industry, motor industry, shipbuilding and home appliance industry, there will be higher requirements for the quantity and quality of the steel. In the steel production, there are some main features, such as the multi-stage operations, high temperature and continuous operations of jobs, and the logistics with intersection and network structure. These features determine that there are firmly reqirement about the production schedule on the operations, the transportation schedule between the operations, and the coordination schedule of production and transportation. A reseasonable schedule for production and logistics can be propitious to tightly connect with each operation in iron and steel industry so as to reduce the unnesserary waiting times. Accordingly, a reseasonable schedule can contribute to descrease the energy consumption and raise the equipment utilization rate such that it may reduce the production and transportation cost, improve the quality of the products, and boosting steel industry competitiveness.In this paper, we are motivated by the background of the steel making and rolling with high emergy consumption. From the two operations, we refine the production and transportation scheduling problems with hot chain logistics feature. Adolpting variety technology, such as complexity analysis, worst-case performance ratio analysis, polynomial-time algorithm, approximation scheme and dynamic programming, we investigate the scheduling problems with deterioration and transportation consideration from the following three aspects:scheduling problems with deterioration consideration, coordinated scheduling problem with production and transportation, and coordinated production-transportation scheduling problems with deterioration consideration. The content is summarized as follows.1) Scheduling problems with deterioration consideration(1) Motivated by the soaking process of ingots, we consider a single-batching-machine problem of scheduling deteriorating jobs with release times, where the processing time of a job is dependent on its waiting time, i.e., the time required between the release of the job and the start of the job on the machine. The objective is to minimize the makespan. First, we prove the problem is NP-hard by a reduction from Equal-size partition problem. For three special cases, we present polynomial-time algorithms respectively..(2) Motivated by two operations of teeming and soaking in the ingot system, we study a scheduling problem under considering deterioration on a two-stage flexible flowshop of particular structure (parallel machines in the first stage and a single batching machine in the second stage). The deterioration of a job means that its processing time on the batching machine is dependent on its waiting time, i.e., the time between the completion of the job in the first stage and the start of the job in the second stage. The objective is to minimize the makespan plus the total penalty cost of machine utilization ratio. First, we prove the problem is strongly NP-hard. An efficient heuristic algorithm for the general problem is constructed and its worst-case bound is analyzed. Computational experiments show that the heuristic algorithm performs well on randomly generated problem instances.2) Coordinated scheduling problem with production and transportation(1) Motivated by the transportation before soaking and soaking process, we study a coordinated scheduling problem of production and transportation in which each job is transported to a single batching machine for further processing. There are m vehicles that transport jobs from the holding area to the batching machine. Each vehicle can transport only one job at a time. The batching machine can process a batch of jobs simultaneously. Each batch to be processed occur a fixed processing cost. The problem is to find a feasible joint schedule of production and transportation such that the sum of the total completion time and the total processing cost is optimized. We p^ove that the problem is NP-hard and present a pseudo-polynomial time algorithm to solve the problem. A fully polynomial time approximation scheme is obtained by converting an especially designed pseudo-polynomial dynamic programming algorithm. We also provide a polynomial time algorithm to solve a special case where the job assignment to the vehicles is predetermined.(2) Motivated by production and transportation from teeming operation to soaking operation, we refine two coordinated scheduling problems of two-machine flowshop and transportation. The objective is to minimize makespan. For the first problem. we present an efficient heuristic algorithm with tight worst-case ratio of 2. The second problem is an extended version of the Lee’s type-1 problem in which jobs require different amounts of storage space during transportation. For the extended problem, a heuristic algorithm is constructed and its absolute worst-case ratio of 7/3 and asymptotic worst-case ratio of 20/9 are derived.(3) Motivated by the two operations from soaking to slab mill, we consider a two-stage flowshop scheduling problem with blocking and transportation time lag consideration where a single batching machine is followed by a single machine. In the flowshop, the single batching machine processes several jobs as a batch while the single machine processes jobs one by one. A batch completed on the batching machine is transported immediately to the single machine when the single machine is available; otherwise the batch must stay there and incurs blocking. Transportation time lag occurs if a batch is transported from the batching machine to the single machine. For the objective to minimize the total blocking time of all jobs, the problem is solved in polynomial time trivially. For the objective to minimize the makespan, we prove strongly NP-hardness result and present a heuristic algorithm along with worst-case ratio. For the objective to minimize a linear combination of the makespan and the total blocking time, a mixed integer programming is presented. We also prove that the last problem is NP-hard in the strong sense and propose a heuristic algorithm along with worst-case ratio. Furthermore, we develop a polynomial time algorithm to solve the case with given job sequence. To evaluate the effectiveness of the algorithms, the experimental investigation results are also presented.(4) Arising from slab mill and finished-jobs transportation, we consider a two-identical-parallel-machine scheduling problem with batch delivery. All jobs delivered together in one shipment are defined as a delivery batch. A batch delivery occur a delivery cost. The objective is to minimize the sum of total completion time and total delivery cost. Although NP-hardness of this problem has been already proved by Hall and Potts, but they did not give the pseudo-polynomial-time algorithm for the problem. We prove the problem is NP-hard in the ordinary sense by constructing a pseudo-polynomial- time algorithm for the problem. We also give a polynomial-time algorithm to solve the case when the job assignment is given. (5) We study the coordinated scheduling problem of hybrid batch production on a single batching machine and two-stage transportation connecting the production arising from soaking process in ingot system, where there is a crane available in the first-stage transportation that transports jobs from the warehouse to the machine and there is a vehicle with unit capacity available in the second-stage transportation to deliver jobs from the machine to the customer. The batching machine processes a batch of jobs simultaneously. Each batch occur a setup cost. The objective is to minimize the sum of the makespan and the total setup cost. We prove that this problem is strongly NP-hard. A polynomial time algorithm is proposed for a case where the job transportation times are identical on the crane or the vehicle. An efficient heuristic algorithm for the general problem is constructed and its tight worst-case bound is analyzed. In order to further verify the performance of the proposed heuristics, we develop a lower bound on the optimal objective function. Computational experiments show that the heuristic algorithm performs well on randomly generated problem instances.3) Coordinated production-transportation scheduling problem with deterioration considerationBased on the feature of soaking process, we study a single batching machine scheduling problem that combines transportation and deterioration. There is a vehicle available that transports jobs from a holding area to a single batching machine for further processing. The deterioration of a job means that its processing time is dependent on its exposed time, i.e., the time between the departure of the job from the holding area and the start of the job on the batching machine. Each batch to be processed on the batching machine incurs a setup cost. The problem is to find a joint schedule of production and transportation that optimizes an objective function involving makespan and total setup cost. We prove that the general problem and two restricted problems (with limited number of batches and with a given upper bound on makespan) are strongly NP-hard. A polynomial time algorithm is proposed for the general problem with given job sequence. An efficient heuristic algorithm for the general problem is constructed and its worst-case bound is analyzed. This algorithm is also extended to the first restricted problem. Computational experiments show that the heuristic algorithm performs well on randomly generated problem instances.更多还原