钢铁企业一类考虑恶化和运输的新型生产调度问题的理论研究
|
摘要
钢铁工业是国民经济的重要支柱产业之一。近年来,随着建筑业、汽车制造业、造船业和家电业的大力发展,对钢材的需求数量和质量提出了更高的要求。由于钢铁生产具有多阶段、物件带有高温连续运作、物流呈交叉网状结构等特点,这就决定了物件在工序上的生产调度、连接工序之间的运输物流调度以及生产和物流调度的衔接都有严格的要求。合理进行生产和物流调度,有利于钢铁工业工序之间的物料紧凑衔接、减少中间等待时间,从而降低能耗、提高大型装置的设备利用率,达到降低生产和物流的综合成本、提高产品质量、提高钢铁工业竞争力的目的。
本文以钢铁企业的高能耗的炼钢和初轧为背景,分别从这两个工序中提炼出具有热链物流特征的生产和运输调度问题,进行理论研究。基于复杂性分析、算法最坏情况分析、多项式时间算法、近似策略、动态规划等多种技术手段,主要研究三个方面的问题：具有恶化特征的生产调度问题、生产和运输协调调度问题、考虑恶化特征的生产运输协调调度问题。
具体内容概括如下：
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-难问题。对于工件的加工顺序给定的情况,给出了多项式时间最优算法。
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 consideration
Based 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.
本文以钢铁企业的高能耗的炼钢和初轧为背景,分别从这两个工序中提炼出具有热链物流特征的生产和运输调度问题,进行理论研究。基于复杂性分析、算法最坏情况分析、多项式时间算法、近似策略、动态规划等多种技术手段,主要研究三个方面的问题：具有恶化特征的生产调度问题、生产和运输协调调度问题、考虑恶化特征的生产运输协调调度问题。
具体内容概括如下：
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-难问题。对于工件的加工顺序给定的情况,给出了多项式时间最优算法。
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 consideration
Based 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.
引文
[1]Tang L X, Luh P B, Liu J Y, Fang L. Steel-making process scheduling by Lagrangian relaxation [J]. International Journal of Production Research,2002, 40:55-70.
[2]Tang L X, Wang G. Decision support system for the batching problems of steelmaking and continuous-casting production [J]. Omega,2008,36:976-991.
[3]Tang L X, Liu J Y, Rong A Y, Yang Z H. A review of integrated planning and scheduling systems and methods for integrated steel production [J]. European Journal of Operational Research,2001,133:1-20.
[4]Tang L X, Liu J Y, Rong A Y, Yang Z H. A mathematical programming model for scheduling steelmaking-continuous casting production [J]. European Journal of Operational Research,2000,120(2):423-435.
[5]Tang L X, Liu G L. A mathematical programming model and solution for scheduling production orders in Shanghai Baoshan Iron and Steel Complex [J]. European Journal of Operational Research,2001,182(3):1453-1468.
[6]Tang L X, Huang L. Optimal and near-optimal algorithms to rolling batch scheduling for seamless tube production [J]. International Journal of Production Economics,2007,105(2):357-371.
[7]唐恒永,赵传立.排序引论[M].科学出版社,2002.
[8]唐国春,张峰,罗守成,刘丽丽.现代排序论[M].上海科学普及出版社,2003.
[9]Pinedo M. Scheduling:theory, algorithm and systems[M]. Prentice-Hall: Englewoods Cliffs, NJ,1995.
[10]陈志平,徐宗本.计算机数学---计算复杂性理论与NPC,NP难问题的求解[M].科学出版社,2001.
[11]张立昂.可计算性与计算复杂性导引(第二版)[M].北京大学出版社,2004.
[12]姚恩瑜,何勇,陈仕平.数学规划与组合优化[M].浙江大学出版社,2001.
[13]Hochbaum D S, Approximation algorithms for NP-hard problems[M]. Boston: PWS Publishing Company, An International Thomson Publishing Company, 1995.
[14]Woeginger G J. When does a dynamic programming formulation guarantee the existence of an FPTAS [J]? Report Woe-27,START Project Y43-MAT, Combinatorial approximation algorithms, TU Graz,1998, Austria.
[15]Brucker P, Gladky A, Hoogeveen H, Kovalyov M Y, Potts C N, Tautenhahn T, van de Velde S L. Scheduling a batching machine [J]. Journal of Scheduling, 1998,1(1):31-54.
[16]Potts C N, Kovalyov M Y, Scheduling with batching:A review [J]. European Journal of Operational Research,2000.120:228-249.
[17]Lee CY, Uzsoy R. Minimizing makespan on a single batch processing machine with dynamic job arrivals [J]. International Journal of Production Research 1999,37:219-236.
[18]Potts CN, Van Wassenhove LN. Integrating scheduling with batching and lot-sizing:A review of algorithms and complexity [J]. Journal of the Operational Research Society,1992,43:395-406.
[19]Webster S, Baker K R. Scheduling groups of jobs on a singe machine [J]. Operations Research,1995,43:692-703.
[20]Mathirajan M. Sivakumar A I. A literature review, classification and simple meta-analysis on scheduling of batch processors in semiconductor [J]. International Journal of Advance Manufacturing Technology,2006, Original article.
[21]Chandru V, Lee C Y, Uzoy R. Minimizing total completion time on batch processing machines [J]. International Journal of Production Research,1993, 31:2097-2121.
[22]Chandru V, Lee C Y, Uzoy R. Minimizing total completion time on a batch processing machines with job families [J]. Operation Research Letters 1993,13: 61-65.
[23]Hochbaum D S, Landy D. Scheduling semiconductor burn-in operations to minimize total flowtime [J]. Operations Research,1997,45:874-885.
[24]Sung C S, Choung Y I, Hong J M, Kim Y H. Minimizing makespan on a single burn-in oven with job families and dynamic job arrivals [J]. Computers & Operations Research,2002,29:995-1007.
[25]Uzsoy R, Lee C Y, Martin-Vega L A. A review of production planning and scheduling models in the semiconductor industry[J]. Part Ⅱ:shop floor control. HE Transaction on Scheduling and Logistics.1994,26:44-55.
[26]Lee C Y, Uzsoy R, Martin-Vega L A. Efficient algorithms for scheduling semiconductor burn-in operations [J]. Operations Research 1992,40:764-775.
[27]Poon C K, Zhang P X. Minimizing makespan in batch machine scheduling [J]. Algorithmetica,2004,39:155-174.
[28]Liu Z H, Yu W C. Scheduling one batch processor subject to job release dates [J]. Discrete Applied Mathematics,2000,105:129-136.
[29]Deng X T, Feng H D, Zhang P X, Zhang Y Z, Zhu H. Minimizing mean completion time in a batch processing system[J]. Algorithmica,2004,38:513-528.
[30]Liu Z H, Cheng T C E. Approximation schemes for minimizing total (weighted) completion time with release dated on a batch machine [J]. Theoretical Computer Science,2005,347:288-298.
[31]Deng X T, Poon C K, Zhang Y Z. Approximation algorithm in batch processing [J]. Journal Combinatorial Optimization,2003,7:247-257.
[32]Deng X T, Feng H D, Li G J, Shi B Y. A PTAS for semiconductor burn-in scheduling [J]. Journal of Combinatorial Optimization,2005,9:5-17.
[33]Cai M, Deng X, Feng H, Li G, Liu G. A PTAS for minimizing total completion time of bounded batch scheduling [C]. Lecture Notes in Computer Science 2337 (IPCO'2002), MIT 2002:304-314.
[34]Chen B, Deng X T, Zhang W. On-line scheduling a batch processing system to minimize total weighted job completion time [J]. Journal of Combinatorial Optimization,2004,8:85-95.
[35]Lee C Y, Uzsoy R, Martin-Vega L A. Efficient algorithms for scheduling semiconductor burn-in operations [J]. Operations Research,1992,40:764-775.
[36]Brucker P, Kovalyov M Y. Single machine batch scheduling to minimize the weighted number of late jobs [J]. Mathematical Methods of Operations Research,1996,43:1-8.
[37]Uzsoy R., Scheduling batch processing machines with incompatible job families [J]. International Journal of Production Research,1995,33:2685-2708.
[38]Yuan J J, Liu Z H, Ng C T, Cheng T C E. The unbounded single machine parallel batch scheduling problem with family jobs and release dates to minimize makespan [J]. Theoretical Computer Science,2004,320:199-212.
[39]Deng X, Feng H,.Li G, Liu G. A PTAS for minimizing total completion time of bounded batch scheduling [J]. International Journal of Foundations of Computer Science,2002,13(6):817-827.
[40]Hochbaum D.S, Landy D. Scheduling with batching:minimizing the weighted number of tardy jobs [J]. Operations Research Letters,1994,16:79-86.
[41]Ikura Y, Gimple M. Scheduling algorithms for a single batch processing machine [J]. Operations Research Letters,1986,5:61-65.
[42]Liu Z H, Yuan J J, Cheng T C E. On scheduling an unbounded batch machine [J]. Operations Research Letters,2003,31:42-48.
[43]Ahmadi J H, Ahmadi R H, Dasu S, Tang C S. Batching and scheduling jobs on batch and discrete processors [J]. Operations Research, 1992,39:750-763.
[44]Hoogeveen J A,.van de Velde S L. Scheduling by positional completion times: Analysis of a two-stage flow shop with a batching machine [J]. Mathematical programming,1998,82:273-289.
[45]Sung C S, Kim Y H. Minimizing makespan in a two-machine flowshop with dynamic arrivals allowed [J]. Computers & Operations Research,2002,29: 275-294.
[46]Sung C S, Yoon S H. Minimizing maximum completion time in a two-batch-processing-machine flowshop with dynamic arrivals allowed [J]. Engineering Optimization,1997,28:231-243.
[47]Sung C S, Kim Y H, Yoon S H. A problem reduction and decomposition approach for scheduling for a flowshop of a batch processing machines [J]. European Journal of Operational Research,2000,121:179-192.
[48]Baptiste P. Batching identical jobs [J]. Mathematical Methods of Operations Research,2000,53(3):355-367.
[49]Baptiste P. Polynomial time algorithms for minimizing the weighted number of late jobs on a single machine with equal processing times [J]. Journal of Scheduling,1999,2:245-252.
[50]Uzsoy R. Scheduling a single batch processing machine with non-identical job sizes [J]. International Journal of Production Research,1994,32:1615-1635.
[51]Uzsoy R, Lee C Y, Martin-Vega L A. Scheduling semiconductor test operations: Minimizing maximum lateness and number of tardy jobs on a single machine [J]. Naval Research Logistics,1992,39:369-388.
[52]Mehta S V, Uzsoy R. Minimizing total tardiness on a batch processing machine with incompatible job families [J]. HE Transactions,1998,30:165-178.
[53]Sung C S, JI M. Scheduling in a two-machine fhowshop with batch processing machine(s) for earliness/tardiness measure under a common dua date [J]. European Journal of Operational Research,2001,131:95-106.
[54]Bachman A. Cheng T C E, Janiak A, Ng C T, Scheduling start time dependent jobs to minimize the total weighted completion time [J]. Journal of the Operational Research Society,2002.53(6):688-693.
[55]Ji M, He Y, Cheng TCE. A simple linear time algorithm for scheduling with step-improving processing times [J]. Computers and Operations Research,2007, 34 (8):2396-2402.
[56]Gawiejnowicz S. Brief survey of continuous models of scheduling [J]. Foundations of Computer and Decision Science,1996,21:81-100.
[57]Alidaee B, Womer N K, Scheduling with time dependent processing times: review and extentions [J]. Journal of the Operational Research Society,1999, 50:711-720.
[58]Cheng T C E., Ding Q, Lin B M T. A concise survey of scheduling with time-dependent processing times [J]. European Journal of Operational Research,2004,152:1-13.
[59]Inderfurth K, Janiak A, Kovalyov M Y and Werner F. Batching work and rework processes with limited deterioration of reworkables [J]. Computers and Operations Research,2006,33:1595-1605.
[60]Wu C C. Lee W C, Shiau Y R. Minimizing the total weighted completion time on a single machine under linear deterioration [J]. International Journal of Advance Manufacturing Technology,2007,33:1237-1243.
[61]Yang, D L, Chern, M S. A generalized two-machine flowshop scheduling problem with processing time linearly dependent on job waiting-time [J]. Computers & Industrial Engineering,1999,36:365-378.
[62]Brown S, Yechiali U. Scheduling deteriorating jobs on a single processor [J]. Operations Research,1990,38:495-498.
[63]Gupta, J N D, Gupta S K. Single facility scheduling with nonlinear processing times [J]. Computers and Industrial Engineering,1988,14:387-394.
[64]Mosheiov G. Scheduling Deteriorating Jobs under Simple Linear Deterioration [J]. Computers and Operations Research,1994,21:653-659.
[65]Ng C T. Cheng T C E, Bachman A. Three scheduling problems with deteriorating jobs to minimize the total completion time [J]. Information Processing Letters,2002.81(6):327-333.
[66]Mosheiov G. Multi-machine scheduling with linear deterioration [J]. INFOR, 1998,36:205-214.
[67]Chen Z L. Parallel machine schedulingwith time-dependent processing times [J]. Discrete Applied Mathematics,1996,70:81-93.
[68]Kang L Y, Ng C T. Anote on a fully polynomial-time approximation scheme for parallel-machine scheduling with deteriorating jobs [J]. International Journal of Production Economics,2007,109:180-184.
[69]Shiau Y R, Lee W C, Wu C C, Chang C M. Two-machine flowshop scheduling to minimize mean flow time under simple linear deterioration [J]. International Journal of Advance Manufacturing Technology:2007,34:774-782.
[70]Wang J B, Xia Z Q. Flowshop scheduling with deteriorating jobs under dominating machines [J]. Omega,2006,34:327-336.
[71]Wang J B, Xia Z Q. No-wait or no-idle permutation flowshop scheduling problem with dominating machines [J]. Journal of Applied Mathematics and Computing.2005,17:419-432.
[72]Wang J B, Ng C T D, Cheng T C E, Liu L L. Minimizing total completion time in a two-machine flow shop with deteriorating jobs [J]. Applied Mathematics and Computation,2008,187:1090-1099.
[73]Mosheiov G. Complexity analysis of job-shop scheduling with deteriorating jobs [J]. Discrete Applied Mathematics,2002,117:195-209.
[74]Mosheiov G. Scheduling jobs with step-deterioration:minimizing makespan on a single- and multi-machine [J]. Computers and Industrial Engineering,1995, 28:869-879.
[75]Sundararaghavan P S., Kunnathur A S., Single machine scheduling with start time dependent processing times:Some solvable cases [J]. European Journal of OperationalResearch,\994,78:394-403.
[76]Cheng T C E. Ding Q. Single machine scheduling with step-deteriorating processing times [J]. European Journal of Operational Research,2001,134: 623-630.
[77]Mosheiov G. A note on scheduling deteriorating jobs [J]. Mathematical and Computer Modelling,2005,41:883-886.
[78]Kubiak W, Steef van de Velde. Scheduling deteriorating jobs to minimize makespan [J]. Navel Research Logistics,1998,45:511-523.
[79]Cheng T C E, Ding Q. The complexity of single machine scheduling with release times [J]. Information Processing Letters,1998.65(2):75-79.
[80]Cheng T C E. Ding Q. Scheduling start time dependent tasks with deadlines and identical initial processing times on a single machine [J]. Computers and Operations Research,2003,30(1):51-62.
[81]Ji M., Cheng T C E. An FPTAS for scheduling jobs with piecewise linear decreasing processing times to minimize makespan [J]. Information Processing Letters,2007,102:41-47.
[82]Cheng T C E, Ding Q, Kovalyov M Y, Bachman A, Janiak A. Scheduling jobs with piecewise linear decreasing processing times [J]. Navel Research Logistics, 2003.50(6):531-554.
[83]Sriskandarajah C, Goyal S K. Scheduling of a two-machine flowshop with processing time linearly dependent on job waiting-time [J]. Journal of the Operational Research Society,1989,40(10):907-921.
[84]Leung T T., Ng C T, Cheng T C E. Minimizing sum of completion times for batch scheduling of jobs with deteriorating processing times [J]. European Journal of Operational Research,2008,187:1090-1099.
[85]Al-Anzi F S, Allahverdi A, Kovalyov M Y. Batching deteriorating items with applications in computer communication and reverse logistics [J]. European Journal of Operational Research,2007,182:1002-1011.
[86]Barketau M S, Cheng T C E, Kovalyov M Y. Batch scheduling of deteriorating reworkables [J]. European Journal of Operational Research,2009,189:1317-1326.
[87]Barketau M S, Cheng T C E, Ng C T. Batch scheduling of step deteriorating items [J]. Journal of Scheduling,2008,11:17-28.
[88]Mosheiov, G. V-Shaped policies for scheduling deteriorating jobs [J]. Operations Research,1991,39:979-991.
[89]Bachman A. Janiak A. Scheduling jobs with position-dependent processing times [J]. Journal of the Operational Research Society,2004,55:257-264.
[90]Lee W C, Wu C C, Liu H C. A note on single-machine makespan problem with general deteriorating function [J]. International Journal of Advance Manufacturing Technology, in press.
[91]Maggu P L, Das G. On 2×n sequencing problem with transportation times of jobs [J]. Pure and Applied Mathematika Science,1980,12(1):1-6.
[92]Maggu P L, Das G, Kumar R. On equivalent job-for-job block in 2×n sequencing problem with transportation times [J]. Journal of the Operations Research Society of Japan,1981,24:136-146.
[93]Hurink J, Knust S. Makespan minimization for flowshop problems with transportation times and a single robot [J]. Discrete Applied Mathematics,2001, 112(1-3):199-216.
[94]Kise H, Shioyama T, Ibaraki T. Automated two-machine flowshop scheduling: A solvable case [J]. IIE Transactions,1991,23(1):10-16.
[95]Stern H I, Vitner G. Scheduling parts in a combined production-transportation work cell [J]. Journal of the Operational Research Society,1990,41(7):625-632.
[96]Geismar H N, Lei L, Sriskandarajah C. The integrated production and transportation scheduling problem for a product with a short life span and non-instantaneous transportation time [J]. working paper,2003.
[97]Panwalkar S S. Scheduling of two-machine flowshop with travel time between machines [J]. Journal of the Operational Research Society,1990,41(7):625-632.
[98]Gemmill D D and Stevens J W. Scheduling a two-machine flowshop with travel times to minimize maximum lateness [J]. International Journal of Production Research,1997,35(1):1-15.
[99]Lee C Y. Chen Z L. Machine scheduling with transportation considerations [J]. Journal of Scheduling,2001.4:3-24.
[100]Lee C Y, Strusevich V A. Two-machine shop scheduling with an uncapacited interstage transporter [J]. HE Transactions,2005,37:725-736.
[101]Lee C Y, Leung J Y T and Yu G. Two machine scheduling under disruptions with transportation considerations [J]. Journal of Scheduling,2006,9(1):35-48.
[102]Soukhal A, Oulamara A, Martineau P. Complexity of flow shop scheduling problems with transportation constraints [J]. European Journal of Operational Research,2005,161(1):32-41.
[103]Strusevich V A. A heuristic for the two-machine open-shop scheduling problem with transportation times [J]. Discrete Applied Mathematics,1999.93:287-304.
[104]Rebaine D, Strusevich V A. Two-machine open shop scheduling with special transportation times [J]. Journal of the Operational Research Society,1999,50 (7):756-764.
[105]Brucker P, Knust S, Cheng T C E, Shakhlevich N V. Complexity results for flow-shop and open-shop scheduling problems with transportation delays [J]. Annals of Operations Research,2004.129:81-106.
[106]Potts C N. Analysis of a heuristic for one machine sequencing with release dates and delivery times [J]. Operations Research 1980,28:1436-1441.
[107]Hall L A, Shmoys D B. Jackson's rule for single-machine scheduling:making a good heuristic better [J]. Mathematics of Operations Research 1992,17:22-35.
[108]Woeginger G J. Heuristics for parallel machine scheduling with delivery times [J]. Acta Informatica,1994,31:503-512.
[109]Chang Y C. Lee C Y. Machine scheduling with job delivery coordination [J]. European Journal of Operational Research,2004.158:470-487.
[110]He Y, Zhong W,Gu H. Improved algorithms for two single machine scheduling problems [J]. Theoretical Computer Science,2006,363:257-265.
[111]Zhong W, Dosa G.,Tan Z. On the machine scheduling problem with job delivery coordination [J]. European Journal of Operational Research,2007.182:1057-1072.
[112]Li C L, Vairaktarakis G., Lee C Y. Machine scheduling with transportation considerations [J]. Journal of Scheduling,2005,164:39-51.
[113]Ganesharajah T, Hall N G., Sriskandarajah C. Design and operational issues in AGV-served manufacturing system [J]. Annals of Operations Research,1998, 76:109-154
[114]Herrmann J W, Lee C Y. On scheduling to minimize earliness-tardiness and batch delivery costs with a common due date [J]. European Journal of Operational Research,1993,70:272-288.
[115]Chen Z L. Scheduling and common due date assignment with earliness-tardiness penalties and batch delivery costs [J]. European Journal of Operational Research 1996,93:49-60.
[116]Cheng T C E, Gordon V S, Kovalyov M Y. Single machine scheduling with batch deliveries [J]. European Journal of Operational Research,1996,94(2): 277-283.
[117]Yuan J J. Anote on the complexity of single-machine scheduling with a common due date, earliness-tardiness, and batch delivery costs [J]. European Journal of Operational Research.1996.94:203-205.
[118]Hall N G., Lesaoana M A., Potts C N. Scheduling with fixed delivery dates [J]. Operations Research,2001,49:854-865.
[119]Wang G, Cheng T C E. Parallel machine scheduling with batch delivery costs [J]. International Journal of Production Economics,2000,68:177-183.
[120]Hall N G., Potts C N. Supply chain scheduling:batching and delivery [J]. Operations Research,2003,51:566-584.
[121]Hall N G., Potts C N. The coordination of scheduling and batch deliveries [J]. Annals of Operations Research,2005,135:41-64.
[122]Pundoor G, Chen Z L. Scheduling a production-distribution system to optimize the tradeoff between delivery tardiness and distribution cost [J]. Naval Research Logistics,2005,52:571-589.
[123]Chen Z L, Vairaktarakis G L. Integrated scheduling of production and distribution operations [J]. Management Science,2005,51:614-628.
[124]Cheng T C E., Kahlbacher H G. Scheduling with delivery and earliness penalties [J]. Asia-Pacific Journal of Operational Research,1993,10:145-152.
[125]Cheng T C E., Gordon V S. Batch delivery scheduling on a single machine [J]. Journal of the Operational Research Society,1994,45:1211-1215.
[126]Ji M, He Y, Cheng T C E. Batch delivery scheduling with batch delivery cost on a single machine [J]. European Journal of Operational Research,2007,176(2): 745-755.
[127]Li C L, Ou J. Machine scheduling with pickup and delivery [J]. Naval Research Logistics,2005,52:617-630.
[128]Riane F, Artiba A, Elmaghraby S E. A hybrid three-stage flowshop problem: efficient heuristics to minimize makespan [J]. European Journal of Operational Research,1998,109:321-329.
[129]Soewandi H, Elmaghraby S E. Sequencing three-stage flexible flowshops with identical machines to minimize makespan [J]. HE Transactions,2001,33: 985-993.
[130]Schuurman P, Woeginger G. J. A polynomial time approximation scheme for the two-stage multiprocessor flow shop problem [J]. Theoretical Computer Science,2000,237:105-122
[131]Su L H. A hybrid two-machine flowshop with limited waiting time constraints [J]. Computers & Industrial Engineering,2003,44:409-424.
[132]Yang J. Posner M. Scheduling parallel machines for the customer order problem [J]. Journal of Scheduling,2005,8:49-74.
[133]Garey M R, Johnson D S. Computers and intractability:A guide to the theory of NP-completeness [M]. W. H. Freeman and Company:New York,1979.
[134]Simchi Levi D. New worst-case results for the bin packing problem [J]. Naval Research Logistics,1994,41:579-585.
[135]Yue M. A simple proof of the inequality FFD(L)≤(?)OPT(L)+1, for the FFD bin-packing algorithm [J]. Acta Mathematicae Applicatae Sinica,1991,7:321-331.
[136]Hall N G, Sriskandarajah C. A survey of machine scheduling problems with blocking and no-wait in process [J]. Operations Research,1996,44:510-525.
[137]Pranzo M. Batch scheduling in a two-machine flow shop with limited buffer and sequence independent setup times and removal times [J]. European Journal of Operational Research,2004,153:581-592.
[138]Smutnicki C. A two-machine permutation flow shop scheduling problem with buffers [J]. OR Spektrum,1998,20:229-239.
[139]Cheng T C E, Lin B M T, Toker A. Makespan minimization in the two-machine flowshop batch scheduling problem [J]. Naval Research Logistics,2000, 47,128-144.
[140]Lin B M T, Cheng T C E. Two-machine flowshop batching and scheduling [J]. Annals of Operations Research,2005,133:149-161.
[141]Lin B M T, Cheng T C E. Batch scheduling in the no-wait two-machine flowshop to minimize the makespan [J]. Computers & Operations Research, 2001,28:316-624.
[142]Yang X G. Scheduling with generalized batch delivery dates and earliness penalties [J]. HE Transaction,2000,32:735-741.
[143]Kovalyov M Y., Kubiak W A. A fully polynomial approximation scheme for minimizing makespan of deteriorating jobs [J]. Journal of Heuristics,1998.3: 287-297.
[144]Wang H Y, Lee C Y. Production and transportation logistics scheduling with two transport mode choices [J]. Naval Research Logistics,2005,52(8): 796-809.
[145]Hoogeveen H. Invited review:Multicriteria scheduling [J]. European Journal of Operational Research,2005,167:592-623.
[2]Tang L X, Wang G. Decision support system for the batching problems of steelmaking and continuous-casting production [J]. Omega,2008,36:976-991.
[3]Tang L X, Liu J Y, Rong A Y, Yang Z H. A review of integrated planning and scheduling systems and methods for integrated steel production [J]. European Journal of Operational Research,2001,133:1-20.
[4]Tang L X, Liu J Y, Rong A Y, Yang Z H. A mathematical programming model for scheduling steelmaking-continuous casting production [J]. European Journal of Operational Research,2000,120(2):423-435.
[5]Tang L X, Liu G L. A mathematical programming model and solution for scheduling production orders in Shanghai Baoshan Iron and Steel Complex [J]. European Journal of Operational Research,2001,182(3):1453-1468.
[6]Tang L X, Huang L. Optimal and near-optimal algorithms to rolling batch scheduling for seamless tube production [J]. International Journal of Production Economics,2007,105(2):357-371.
[7]唐恒永,赵传立.排序引论[M].科学出版社,2002.
[8]唐国春,张峰,罗守成,刘丽丽.现代排序论[M].上海科学普及出版社,2003.
[9]Pinedo M. Scheduling:theory, algorithm and systems[M]. Prentice-Hall: Englewoods Cliffs, NJ,1995.
[10]陈志平,徐宗本.计算机数学---计算复杂性理论与NPC,NP难问题的求解[M].科学出版社,2001.
[11]张立昂.可计算性与计算复杂性导引(第二版)[M].北京大学出版社,2004.
[12]姚恩瑜,何勇,陈仕平.数学规划与组合优化[M].浙江大学出版社,2001.
[13]Hochbaum D S, Approximation algorithms for NP-hard problems[M]. Boston: PWS Publishing Company, An International Thomson Publishing Company, 1995.
[14]Woeginger G J. When does a dynamic programming formulation guarantee the existence of an FPTAS [J]? Report Woe-27,START Project Y43-MAT, Combinatorial approximation algorithms, TU Graz,1998, Austria.
[15]Brucker P, Gladky A, Hoogeveen H, Kovalyov M Y, Potts C N, Tautenhahn T, van de Velde S L. Scheduling a batching machine [J]. Journal of Scheduling, 1998,1(1):31-54.
[16]Potts C N, Kovalyov M Y, Scheduling with batching:A review [J]. European Journal of Operational Research,2000.120:228-249.
[17]Lee CY, Uzsoy R. Minimizing makespan on a single batch processing machine with dynamic job arrivals [J]. International Journal of Production Research 1999,37:219-236.
[18]Potts CN, Van Wassenhove LN. Integrating scheduling with batching and lot-sizing:A review of algorithms and complexity [J]. Journal of the Operational Research Society,1992,43:395-406.
[19]Webster S, Baker K R. Scheduling groups of jobs on a singe machine [J]. Operations Research,1995,43:692-703.
[20]Mathirajan M. Sivakumar A I. A literature review, classification and simple meta-analysis on scheduling of batch processors in semiconductor [J]. International Journal of Advance Manufacturing Technology,2006, Original article.
[21]Chandru V, Lee C Y, Uzoy R. Minimizing total completion time on batch processing machines [J]. International Journal of Production Research,1993, 31:2097-2121.
[22]Chandru V, Lee C Y, Uzoy R. Minimizing total completion time on a batch processing machines with job families [J]. Operation Research Letters 1993,13: 61-65.
[23]Hochbaum D S, Landy D. Scheduling semiconductor burn-in operations to minimize total flowtime [J]. Operations Research,1997,45:874-885.
[24]Sung C S, Choung Y I, Hong J M, Kim Y H. Minimizing makespan on a single burn-in oven with job families and dynamic job arrivals [J]. Computers & Operations Research,2002,29:995-1007.
[25]Uzsoy R, Lee C Y, Martin-Vega L A. A review of production planning and scheduling models in the semiconductor industry[J]. Part Ⅱ:shop floor control. HE Transaction on Scheduling and Logistics.1994,26:44-55.
[26]Lee C Y, Uzsoy R, Martin-Vega L A. Efficient algorithms for scheduling semiconductor burn-in operations [J]. Operations Research 1992,40:764-775.
[27]Poon C K, Zhang P X. Minimizing makespan in batch machine scheduling [J]. Algorithmetica,2004,39:155-174.
[28]Liu Z H, Yu W C. Scheduling one batch processor subject to job release dates [J]. Discrete Applied Mathematics,2000,105:129-136.
[29]Deng X T, Feng H D, Zhang P X, Zhang Y Z, Zhu H. Minimizing mean completion time in a batch processing system[J]. Algorithmica,2004,38:513-528.
[30]Liu Z H, Cheng T C E. Approximation schemes for minimizing total (weighted) completion time with release dated on a batch machine [J]. Theoretical Computer Science,2005,347:288-298.
[31]Deng X T, Poon C K, Zhang Y Z. Approximation algorithm in batch processing [J]. Journal Combinatorial Optimization,2003,7:247-257.
[32]Deng X T, Feng H D, Li G J, Shi B Y. A PTAS for semiconductor burn-in scheduling [J]. Journal of Combinatorial Optimization,2005,9:5-17.
[33]Cai M, Deng X, Feng H, Li G, Liu G. A PTAS for minimizing total completion time of bounded batch scheduling [C]. Lecture Notes in Computer Science 2337 (IPCO'2002), MIT 2002:304-314.
[34]Chen B, Deng X T, Zhang W. On-line scheduling a batch processing system to minimize total weighted job completion time [J]. Journal of Combinatorial Optimization,2004,8:85-95.
[35]Lee C Y, Uzsoy R, Martin-Vega L A. Efficient algorithms for scheduling semiconductor burn-in operations [J]. Operations Research,1992,40:764-775.
[36]Brucker P, Kovalyov M Y. Single machine batch scheduling to minimize the weighted number of late jobs [J]. Mathematical Methods of Operations Research,1996,43:1-8.
[37]Uzsoy R., Scheduling batch processing machines with incompatible job families [J]. International Journal of Production Research,1995,33:2685-2708.
[38]Yuan J J, Liu Z H, Ng C T, Cheng T C E. The unbounded single machine parallel batch scheduling problem with family jobs and release dates to minimize makespan [J]. Theoretical Computer Science,2004,320:199-212.
[39]Deng X, Feng H,.Li G, Liu G. A PTAS for minimizing total completion time of bounded batch scheduling [J]. International Journal of Foundations of Computer Science,2002,13(6):817-827.
[40]Hochbaum D.S, Landy D. Scheduling with batching:minimizing the weighted number of tardy jobs [J]. Operations Research Letters,1994,16:79-86.
[41]Ikura Y, Gimple M. Scheduling algorithms for a single batch processing machine [J]. Operations Research Letters,1986,5:61-65.
[42]Liu Z H, Yuan J J, Cheng T C E. On scheduling an unbounded batch machine [J]. Operations Research Letters,2003,31:42-48.
[43]Ahmadi J H, Ahmadi R H, Dasu S, Tang C S. Batching and scheduling jobs on batch and discrete processors [J]. Operations Research, 1992,39:750-763.
[44]Hoogeveen J A,.van de Velde S L. Scheduling by positional completion times: Analysis of a two-stage flow shop with a batching machine [J]. Mathematical programming,1998,82:273-289.
[45]Sung C S, Kim Y H. Minimizing makespan in a two-machine flowshop with dynamic arrivals allowed [J]. Computers & Operations Research,2002,29: 275-294.
[46]Sung C S, Yoon S H. Minimizing maximum completion time in a two-batch-processing-machine flowshop with dynamic arrivals allowed [J]. Engineering Optimization,1997,28:231-243.
[47]Sung C S, Kim Y H, Yoon S H. A problem reduction and decomposition approach for scheduling for a flowshop of a batch processing machines [J]. European Journal of Operational Research,2000,121:179-192.
[48]Baptiste P. Batching identical jobs [J]. Mathematical Methods of Operations Research,2000,53(3):355-367.
[49]Baptiste P. Polynomial time algorithms for minimizing the weighted number of late jobs on a single machine with equal processing times [J]. Journal of Scheduling,1999,2:245-252.
[50]Uzsoy R. Scheduling a single batch processing machine with non-identical job sizes [J]. International Journal of Production Research,1994,32:1615-1635.
[51]Uzsoy R, Lee C Y, Martin-Vega L A. Scheduling semiconductor test operations: Minimizing maximum lateness and number of tardy jobs on a single machine [J]. Naval Research Logistics,1992,39:369-388.
[52]Mehta S V, Uzsoy R. Minimizing total tardiness on a batch processing machine with incompatible job families [J]. HE Transactions,1998,30:165-178.
[53]Sung C S, JI M. Scheduling in a two-machine fhowshop with batch processing machine(s) for earliness/tardiness measure under a common dua date [J]. European Journal of Operational Research,2001,131:95-106.
[54]Bachman A. Cheng T C E, Janiak A, Ng C T, Scheduling start time dependent jobs to minimize the total weighted completion time [J]. Journal of the Operational Research Society,2002.53(6):688-693.
[55]Ji M, He Y, Cheng TCE. A simple linear time algorithm for scheduling with step-improving processing times [J]. Computers and Operations Research,2007, 34 (8):2396-2402.
[56]Gawiejnowicz S. Brief survey of continuous models of scheduling [J]. Foundations of Computer and Decision Science,1996,21:81-100.
[57]Alidaee B, Womer N K, Scheduling with time dependent processing times: review and extentions [J]. Journal of the Operational Research Society,1999, 50:711-720.
[58]Cheng T C E., Ding Q, Lin B M T. A concise survey of scheduling with time-dependent processing times [J]. European Journal of Operational Research,2004,152:1-13.
[59]Inderfurth K, Janiak A, Kovalyov M Y and Werner F. Batching work and rework processes with limited deterioration of reworkables [J]. Computers and Operations Research,2006,33:1595-1605.
[60]Wu C C. Lee W C, Shiau Y R. Minimizing the total weighted completion time on a single machine under linear deterioration [J]. International Journal of Advance Manufacturing Technology,2007,33:1237-1243.
[61]Yang, D L, Chern, M S. A generalized two-machine flowshop scheduling problem with processing time linearly dependent on job waiting-time [J]. Computers & Industrial Engineering,1999,36:365-378.
[62]Brown S, Yechiali U. Scheduling deteriorating jobs on a single processor [J]. Operations Research,1990,38:495-498.
[63]Gupta, J N D, Gupta S K. Single facility scheduling with nonlinear processing times [J]. Computers and Industrial Engineering,1988,14:387-394.
[64]Mosheiov G. Scheduling Deteriorating Jobs under Simple Linear Deterioration [J]. Computers and Operations Research,1994,21:653-659.
[65]Ng C T. Cheng T C E, Bachman A. Three scheduling problems with deteriorating jobs to minimize the total completion time [J]. Information Processing Letters,2002.81(6):327-333.
[66]Mosheiov G. Multi-machine scheduling with linear deterioration [J]. INFOR, 1998,36:205-214.
[67]Chen Z L. Parallel machine schedulingwith time-dependent processing times [J]. Discrete Applied Mathematics,1996,70:81-93.
[68]Kang L Y, Ng C T. Anote on a fully polynomial-time approximation scheme for parallel-machine scheduling with deteriorating jobs [J]. International Journal of Production Economics,2007,109:180-184.
[69]Shiau Y R, Lee W C, Wu C C, Chang C M. Two-machine flowshop scheduling to minimize mean flow time under simple linear deterioration [J]. International Journal of Advance Manufacturing Technology:2007,34:774-782.
[70]Wang J B, Xia Z Q. Flowshop scheduling with deteriorating jobs under dominating machines [J]. Omega,2006,34:327-336.
[71]Wang J B, Xia Z Q. No-wait or no-idle permutation flowshop scheduling problem with dominating machines [J]. Journal of Applied Mathematics and Computing.2005,17:419-432.
[72]Wang J B, Ng C T D, Cheng T C E, Liu L L. Minimizing total completion time in a two-machine flow shop with deteriorating jobs [J]. Applied Mathematics and Computation,2008,187:1090-1099.
[73]Mosheiov G. Complexity analysis of job-shop scheduling with deteriorating jobs [J]. Discrete Applied Mathematics,2002,117:195-209.
[74]Mosheiov G. Scheduling jobs with step-deterioration:minimizing makespan on a single- and multi-machine [J]. Computers and Industrial Engineering,1995, 28:869-879.
[75]Sundararaghavan P S., Kunnathur A S., Single machine scheduling with start time dependent processing times:Some solvable cases [J]. European Journal of OperationalResearch,\994,78:394-403.
[76]Cheng T C E. Ding Q. Single machine scheduling with step-deteriorating processing times [J]. European Journal of Operational Research,2001,134: 623-630.
[77]Mosheiov G. A note on scheduling deteriorating jobs [J]. Mathematical and Computer Modelling,2005,41:883-886.
[78]Kubiak W, Steef van de Velde. Scheduling deteriorating jobs to minimize makespan [J]. Navel Research Logistics,1998,45:511-523.
[79]Cheng T C E, Ding Q. The complexity of single machine scheduling with release times [J]. Information Processing Letters,1998.65(2):75-79.
[80]Cheng T C E. Ding Q. Scheduling start time dependent tasks with deadlines and identical initial processing times on a single machine [J]. Computers and Operations Research,2003,30(1):51-62.
[81]Ji M., Cheng T C E. An FPTAS for scheduling jobs with piecewise linear decreasing processing times to minimize makespan [J]. Information Processing Letters,2007,102:41-47.
[82]Cheng T C E, Ding Q, Kovalyov M Y, Bachman A, Janiak A. Scheduling jobs with piecewise linear decreasing processing times [J]. Navel Research Logistics, 2003.50(6):531-554.
[83]Sriskandarajah C, Goyal S K. Scheduling of a two-machine flowshop with processing time linearly dependent on job waiting-time [J]. Journal of the Operational Research Society,1989,40(10):907-921.
[84]Leung T T., Ng C T, Cheng T C E. Minimizing sum of completion times for batch scheduling of jobs with deteriorating processing times [J]. European Journal of Operational Research,2008,187:1090-1099.
[85]Al-Anzi F S, Allahverdi A, Kovalyov M Y. Batching deteriorating items with applications in computer communication and reverse logistics [J]. European Journal of Operational Research,2007,182:1002-1011.
[86]Barketau M S, Cheng T C E, Kovalyov M Y. Batch scheduling of deteriorating reworkables [J]. European Journal of Operational Research,2009,189:1317-1326.
[87]Barketau M S, Cheng T C E, Ng C T. Batch scheduling of step deteriorating items [J]. Journal of Scheduling,2008,11:17-28.
[88]Mosheiov, G. V-Shaped policies for scheduling deteriorating jobs [J]. Operations Research,1991,39:979-991.
[89]Bachman A. Janiak A. Scheduling jobs with position-dependent processing times [J]. Journal of the Operational Research Society,2004,55:257-264.
[90]Lee W C, Wu C C, Liu H C. A note on single-machine makespan problem with general deteriorating function [J]. International Journal of Advance Manufacturing Technology, in press.
[91]Maggu P L, Das G. On 2×n sequencing problem with transportation times of jobs [J]. Pure and Applied Mathematika Science,1980,12(1):1-6.
[92]Maggu P L, Das G, Kumar R. On equivalent job-for-job block in 2×n sequencing problem with transportation times [J]. Journal of the Operations Research Society of Japan,1981,24:136-146.
[93]Hurink J, Knust S. Makespan minimization for flowshop problems with transportation times and a single robot [J]. Discrete Applied Mathematics,2001, 112(1-3):199-216.
[94]Kise H, Shioyama T, Ibaraki T. Automated two-machine flowshop scheduling: A solvable case [J]. IIE Transactions,1991,23(1):10-16.
[95]Stern H I, Vitner G. Scheduling parts in a combined production-transportation work cell [J]. Journal of the Operational Research Society,1990,41(7):625-632.
[96]Geismar H N, Lei L, Sriskandarajah C. The integrated production and transportation scheduling problem for a product with a short life span and non-instantaneous transportation time [J]. working paper,2003.
[97]Panwalkar S S. Scheduling of two-machine flowshop with travel time between machines [J]. Journal of the Operational Research Society,1990,41(7):625-632.
[98]Gemmill D D and Stevens J W. Scheduling a two-machine flowshop with travel times to minimize maximum lateness [J]. International Journal of Production Research,1997,35(1):1-15.
[99]Lee C Y. Chen Z L. Machine scheduling with transportation considerations [J]. Journal of Scheduling,2001.4:3-24.
[100]Lee C Y, Strusevich V A. Two-machine shop scheduling with an uncapacited interstage transporter [J]. HE Transactions,2005,37:725-736.
[101]Lee C Y, Leung J Y T and Yu G. Two machine scheduling under disruptions with transportation considerations [J]. Journal of Scheduling,2006,9(1):35-48.
[102]Soukhal A, Oulamara A, Martineau P. Complexity of flow shop scheduling problems with transportation constraints [J]. European Journal of Operational Research,2005,161(1):32-41.
[103]Strusevich V A. A heuristic for the two-machine open-shop scheduling problem with transportation times [J]. Discrete Applied Mathematics,1999.93:287-304.
[104]Rebaine D, Strusevich V A. Two-machine open shop scheduling with special transportation times [J]. Journal of the Operational Research Society,1999,50 (7):756-764.
[105]Brucker P, Knust S, Cheng T C E, Shakhlevich N V. Complexity results for flow-shop and open-shop scheduling problems with transportation delays [J]. Annals of Operations Research,2004.129:81-106.
[106]Potts C N. Analysis of a heuristic for one machine sequencing with release dates and delivery times [J]. Operations Research 1980,28:1436-1441.
[107]Hall L A, Shmoys D B. Jackson's rule for single-machine scheduling:making a good heuristic better [J]. Mathematics of Operations Research 1992,17:22-35.
[108]Woeginger G J. Heuristics for parallel machine scheduling with delivery times [J]. Acta Informatica,1994,31:503-512.
[109]Chang Y C. Lee C Y. Machine scheduling with job delivery coordination [J]. European Journal of Operational Research,2004.158:470-487.
[110]He Y, Zhong W,Gu H. Improved algorithms for two single machine scheduling problems [J]. Theoretical Computer Science,2006,363:257-265.
[111]Zhong W, Dosa G.,Tan Z. On the machine scheduling problem with job delivery coordination [J]. European Journal of Operational Research,2007.182:1057-1072.
[112]Li C L, Vairaktarakis G., Lee C Y. Machine scheduling with transportation considerations [J]. Journal of Scheduling,2005,164:39-51.
[113]Ganesharajah T, Hall N G., Sriskandarajah C. Design and operational issues in AGV-served manufacturing system [J]. Annals of Operations Research,1998, 76:109-154
[114]Herrmann J W, Lee C Y. On scheduling to minimize earliness-tardiness and batch delivery costs with a common due date [J]. European Journal of Operational Research,1993,70:272-288.
[115]Chen Z L. Scheduling and common due date assignment with earliness-tardiness penalties and batch delivery costs [J]. European Journal of Operational Research 1996,93:49-60.
[116]Cheng T C E, Gordon V S, Kovalyov M Y. Single machine scheduling with batch deliveries [J]. European Journal of Operational Research,1996,94(2): 277-283.
[117]Yuan J J. Anote on the complexity of single-machine scheduling with a common due date, earliness-tardiness, and batch delivery costs [J]. European Journal of Operational Research.1996.94:203-205.
[118]Hall N G., Lesaoana M A., Potts C N. Scheduling with fixed delivery dates [J]. Operations Research,2001,49:854-865.
[119]Wang G, Cheng T C E. Parallel machine scheduling with batch delivery costs [J]. International Journal of Production Economics,2000,68:177-183.
[120]Hall N G., Potts C N. Supply chain scheduling:batching and delivery [J]. Operations Research,2003,51:566-584.
[121]Hall N G., Potts C N. The coordination of scheduling and batch deliveries [J]. Annals of Operations Research,2005,135:41-64.
[122]Pundoor G, Chen Z L. Scheduling a production-distribution system to optimize the tradeoff between delivery tardiness and distribution cost [J]. Naval Research Logistics,2005,52:571-589.
[123]Chen Z L, Vairaktarakis G L. Integrated scheduling of production and distribution operations [J]. Management Science,2005,51:614-628.
[124]Cheng T C E., Kahlbacher H G. Scheduling with delivery and earliness penalties [J]. Asia-Pacific Journal of Operational Research,1993,10:145-152.
[125]Cheng T C E., Gordon V S. Batch delivery scheduling on a single machine [J]. Journal of the Operational Research Society,1994,45:1211-1215.
[126]Ji M, He Y, Cheng T C E. Batch delivery scheduling with batch delivery cost on a single machine [J]. European Journal of Operational Research,2007,176(2): 745-755.
[127]Li C L, Ou J. Machine scheduling with pickup and delivery [J]. Naval Research Logistics,2005,52:617-630.
[128]Riane F, Artiba A, Elmaghraby S E. A hybrid three-stage flowshop problem: efficient heuristics to minimize makespan [J]. European Journal of Operational Research,1998,109:321-329.
[129]Soewandi H, Elmaghraby S E. Sequencing three-stage flexible flowshops with identical machines to minimize makespan [J]. HE Transactions,2001,33: 985-993.
[130]Schuurman P, Woeginger G. J. A polynomial time approximation scheme for the two-stage multiprocessor flow shop problem [J]. Theoretical Computer Science,2000,237:105-122
[131]Su L H. A hybrid two-machine flowshop with limited waiting time constraints [J]. Computers & Industrial Engineering,2003,44:409-424.
[132]Yang J. Posner M. Scheduling parallel machines for the customer order problem [J]. Journal of Scheduling,2005,8:49-74.
[133]Garey M R, Johnson D S. Computers and intractability:A guide to the theory of NP-completeness [M]. W. H. Freeman and Company:New York,1979.
[134]Simchi Levi D. New worst-case results for the bin packing problem [J]. Naval Research Logistics,1994,41:579-585.
[135]Yue M. A simple proof of the inequality FFD(L)≤(?)OPT(L)+1, for the FFD bin-packing algorithm [J]. Acta Mathematicae Applicatae Sinica,1991,7:321-331.
[136]Hall N G, Sriskandarajah C. A survey of machine scheduling problems with blocking and no-wait in process [J]. Operations Research,1996,44:510-525.
[137]Pranzo M. Batch scheduling in a two-machine flow shop with limited buffer and sequence independent setup times and removal times [J]. European Journal of Operational Research,2004,153:581-592.
[138]Smutnicki C. A two-machine permutation flow shop scheduling problem with buffers [J]. OR Spektrum,1998,20:229-239.
[139]Cheng T C E, Lin B M T, Toker A. Makespan minimization in the two-machine flowshop batch scheduling problem [J]. Naval Research Logistics,2000, 47,128-144.
[140]Lin B M T, Cheng T C E. Two-machine flowshop batching and scheduling [J]. Annals of Operations Research,2005,133:149-161.
[141]Lin B M T, Cheng T C E. Batch scheduling in the no-wait two-machine flowshop to minimize the makespan [J]. Computers & Operations Research, 2001,28:316-624.
[142]Yang X G. Scheduling with generalized batch delivery dates and earliness penalties [J]. HE Transaction,2000,32:735-741.
[143]Kovalyov M Y., Kubiak W A. A fully polynomial approximation scheme for minimizing makespan of deteriorating jobs [J]. Journal of Heuristics,1998.3: 287-297.
[144]Wang H Y, Lee C Y. Production and transportation logistics scheduling with two transport mode choices [J]. Naval Research Logistics,2005,52(8): 796-809.
[145]Hoogeveen H. Invited review:Multicriteria scheduling [J]. European Journal of Operational Research,2005,167:592-623.
© 2004-2018 中国地质图书馆版权所有 京ICP备05064691号 京公网安备11010802017129号 地址：北京市海淀区学院路29号 邮编：100083 电话：办公室：(+86 10)66554848；文献借阅、咨询服务、科技查新：66554700 |