Production And Transportation Coordinated Scheduling Problems In The Process Industry

Production and transportation are considered separately in classical scheduling in which production is always primary while transportation is secondary. Transportation scheduling is usually arranged according to the optimal strategy of production scheduling. However, in practical situation, the delivery of jobs (raw materials and semi-finished products and finished products) between different operations is restricted by the number and capacity of transporters. Thus, those optimal production schedules without transportation consideration are usually excuted inefficiently when no sufficient transporters are available. A natural and reasonable idea is to coordinate production and transportation scheduling. Coordinated scheduling can link up production and transportation accuratly which will be helpful to improve the efficiency of transporters greatly so as to reduce the total cost of production and logistics obviously.There are various transportations between the adjacent operations in process industry. We refer to steel industry which is a typical process industry as an example, in which torpedo cars are needed to transport molten iron between the productions of blast furnace and converter, hoists and trolleys are needed to transport between steelmaking and continuous casting, and cars are required to convey hot slab before hot rolling and steel roll before cool rolling. Since jobs delivered'in process industry are in high temperature, expensive unit price, and rigorous delivering time between continuous working procedures, it is helpful to coordinate production and transportation effectively so as to reduce comsumption of energy, improve efficiency of production equipment and transporters, satisfy requirement of real-time and guarantee logisctics of production smoothly. In recent years, more and more international researchers focus on the coordinated scheduling between production and transportation.By taking the background of steel industry into account, we study the coordinated scheduling problems from the following three aspects:inbound transportation, semi-finished jobs transportation and finished jobs transportation. The content is summarized as follows.1) Coordinated scheduling problem with inbound transportation(1) A single machine scheduling problem with inbound transportation consideration from the processing of color coated is abstracted. Limited capacity of transporters and waiting time of jobs before processed are taken into account respectively which make the problem different from those classical scheduling problems. The objective function is to minimize the conventional scheduling function plus conveyance cost. For different objective functions, the strongly NP-hard proofs for problems with limited waiting time before single machine are proved. As to the solvable cases that the capacity of transporters is limited, some polynomial time algorithms are given for different objective functions.(2) A single machine scheduling problem with inbound transportation mode choice is abstracted from the practical situation of raw materials inbound transportation in steel plant. At the same time, waiting time limitation is considered. So the two characteristics of the choice of conveyance mode and waiting time limitation make the problem different from others. The objective is to minimize the conventional scheduling function plus transporter setup cost. Strongly NP-hard proof is provided for different objective functions. A tabu search algorithm for the problem with minimizing the sum of makespan and transporters setup cost is proposed, and computational results are provided.(3) A single machine coordinated scheduling problem with hot jobs from the practical situation of hot slabs transportation is abstracted. The processing times of those heat lost jobs depend on waiting times which make the problem different from those with uncertain processing times. The objective is to minimize the maximum completion time. For the problem with release time, we provide strongly NP-hard proof. For those problems with various numbers of transporter and capacities, we provide the strongly NP-hard proof respectively. An approximate algorithm for problem with one transporter is given, and computational experiments are provided to show the efficiency of the algorithm.(4) A new type of two-machine flowshop scheduling problem arising from steel tube production process is studied in which jobs transported from upstream are disintegrated in the first machine one by one. Complexity analysises of the new type of two-machine flowshop problems with transportation and without transportation are studied. For the problem without transportation to minimize makespan, we provide an optimal algorithm. For the problem with buffer capacity limitation consideration and inbound transportation to minimize makespan, we give the strongly NP-hard proof. For the problem with excessive penalties to minimize makespan, we prove that the problem is NP-hard and propose a pseudo-polynomial algorithm for the problem. We show that the optimal algorithm for the first problem can provide an algorithm with worst case ratio of 2 for those relative NP-hard problems, and provide the computational results.2) Coordinated scheduling problem with semi-finished jobs transportation(1) A two-stage production scheduling problem arising from steelmaking and refining operations in steel plant with semi-finished jobs transportation consideration is studied. The effects brought by transportation times and waiting time limitation to production are considered. For a special case, we provide an approximate algorithm with worst case ratio of 2 and show the computational results. Some relative solvable cases are considered as well. For a more practical situation, we develop a tabu search algorithm in which the approximate algorith for the special case is used, and then worst case analysis and computational results are given to show the efficiency of the tabu search algorithm.(2) The coordinated scheduling problems with two tandem transporters consideration arising from steelmaking-refining operations are studied. The coordinated tandem transporters make the problem differ from others. For the first special case in which one processor and two tandem transporters are involved, we provide a polynomial time optimal algorithm when minimizing the maximum completion time is the objective. For the coordinated problem in detail production fact consideration, we provide a tabu search algorithm in which optimal algorithm for the first special case is applied. Worst case analysis and computational tests are evaluated to show the efficiency brought by the tabu search algorithm.(3) The coordinated scheduling problem arising from steelmaking and multi-refining operations is considered which is closer to practical situation. Transportation with two tandom transporters is also considered. For this problem, we develop a tabu search algorithm. Worst case analysis and computational tests are evaluated to show the efficiency brought by the tabu search algorithm. 3) Coordinated scheduling problem with finished jobs transportation(1) A single machine scheduling problem arising from hot slab transportation in steel plant with batch delivery of hot jobs consideration is studied. When waiting to be delivered after processing, the tempreture of those hot jobs drop. Energy lost is measured by temperature dropping function which adds continuous function to the objective of deterministic scheduling problem. For the problem to minimize the sum of conventional scheduling function and energy lost, the strongly NP-hard proof is provided. Some solvable special cases are also considered. For steelmaking-refining scheduling problem with energy lost consideration, we provide a tabu search algorithm, and evaluate the worst case analysis and report the computational experiments.