A Class Of Production Scheduling Problems Under Deterioration And Transportation Consideration In The Steel And Iron Industry

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.