Theoratical Analysis And Methods For Scheduling Of Batching Machine

It is necessary for steel-making industries to have a batch production because of high cost of equipments operation and initial starting, as well as high similarity and large quantity of products. In order to save energy and use equipments effectively, steel-making industries usually take various batch scheduling in their production, including family scheduling, parallel batching and batch scheduling with delivery, and so forth. Therefore, the research on batch scheduling in steel-making industries is especially significant not only in theory but also in reality, which can generate various scheduling models, enrich research, direct production process effectively, improve producing process and finally raise economic efficiency.This paper studies the batch scheduling models based on the scheduling of bell-type annealing furnaces and soaking pits in the steel making industry. The researches in this paper are as following.(1) An efficient heuristic algorithm and meta-heuristic algorithm are constructed to solve single batching machine scheduling problem with the objective of minimizing the total weighted completion time. The constructive algorithm is designed based on the analysis of the quality of optimal solutions of a problem, and the meta-heuristic algorithm is an iterative algorithm on the basis of cycle transfermation. The experiment based on randomly generated data show that the heuristic algorithm is better than the existing full-batch heuristic algorithm and dynamic programming heuristic algorithm, while the solution quality of meta-heuristic algorithm is better than the heuristic with the expense of spending too much time on calculation.(2) A batching machine scheduling problem with consideration of job size is derived from the heating process of the steel coils in the bell type furnace. Different from traditional ways for batching machines which takes the number of jobs as processing capacity, this paper determines the job (with size) composition of every batch and the batch sequence with height as machine capacity, and minimizing the idle space of the machine and the total completion time of the jobs are taken as the objective. Since the problem belongs to NP-hard, we construct a structive heuristic algorithm based on greedy strategy. At the same time we construct a heuristic algorithm for the case with the objective of minimizing total completion time, which firstly sequences the jobs based on SPT rule, then makes baching decision by dynamic programming based on the characteristic of the problem. The efficiency of the proposed algorithm is verified by the numerical experiments.(3) A novel batch machine scheduling problem where the job have three-step processing times on a machine is derived from the annealing process of the steel coils in the bell type furnace. The process is composed of three parts of operations, that is heating, soaking and cooling, and the processing times corresponding to these three operations cannot be regarded as a whole processing time, which is apparently different from classical batching machines. An nonlinear integer programming is proposed with the objective of minimizing the total weighted completion time, and a heuristic algorithm is developed on the basis of dynamic programming. The worst case performance of the heuristic is proved to be at most 3. If any two steps processing time of all the jobs are the same, the optimal solution can be obtained through the heuristic. If any step processing time of all the jobs is the same, the worst case of heuristic is proved to be at most 2 and the bound is tight. At the same time the worst case of the heuristic for the general case that jobs processing are composed of any step-processing is analyzed.(4) Batch machine scheduling problem with linear deterioration linear processing time and threshold value is derived from the soaking pit, where the soaking time of the steel ingot is deteriorated for the temperature decreasation which is caused by the increasation of the hot ingot’s the waiting time. For the ingot, the soaking time wil be fixed if the waiting time exceeds a given threshold value. With the objective of minimizing total completion time, the characteristics of the optimal solution is analyzed. Based on the characteristics, a constructive heuristic is proposed. The efficiency of the proposed algorithm is verified by the comparison between our proposed heuristic and the whole-batch algorithm.