Steel Production In The Batch Machine Scheduling Problem Algorithm Study

The batching machine scheduling problems based on the processing in iron and steel industry are proposed in this research. Iron and steel industry plays a very important role in our country, of which the manufacturing system is very complicated, so the scheduling problems in iron and steel industry are full of challenge. This research is based on the project named Scheduling in Wide and Thick Plate Manufacturing Factory of Baosteel, where several classes of batching machine scheduling problems with family jobs derived from the processing in heating furnace and heat-treating furnace are addressed. A series of algorithms are generated to solve these batching machine scheduling problems.This paper is divided into 6 chapters. Chapter 1 introduces the background and value of this research, while Chapter 2 gives the basic knowledge of scheduling and literature review. From the literature review we can see that the existing research on the batching machine scheduling problems with family jobs is not enough, most of which are not yet studied, including the problems addressed in this paper. Hence, this research is valuable, not only in sense of theory but also of application.Chapter 3 derives an unbounded batching machine scheduling problem from the processing in heating furnace, which is 1|p- batch, family—jobs, s_fg|f. This paper studies this problem, giving the structural properties of this problem and 3 types of dynamic programming algorithms to solve this problem, which are generic pseudo-polynomial forward dynamic programming algorithm for arbitrary regular objective function, generic polynomial backward dynamic programming algorithm for two types of objective functions and polynomial forward dynamic programming algorithm minimizing the number of tardy jobs. In addition, Chapter 3 proposed a series of heuristic algorithms to minimize the total weighted completion time.Chapter 4 addresses the bounded model of the problem in Chapter 3. For minimizing the total weighted completion time, a branch and bound algorithm and a number of heuristic algorithms are proposed, including a hybrid genetic algorithm and a novel scheduling algorithm which is named bidding algorithm.Chapter 5 derives a batching machine scheduling problem with family jobs and re-entrance from the processing in heat-treating furnace, which is transformed into a batching machine scheduling problem with family jobs and chains precedence constraints, 1|p - batch, family - jobs, chains|∑_i=1^m∑_j=1^n_iw_ijC_ij. branch and bound algorithm and several heuristic algorithms are presented to solve this problem. Chapter 6 summarizes the works and contributions, as well as the shortcomings, of this paper, and gives the suggestions for the coming research.This research makes full use of the mathematical programming method, heuristics and the theory of computer science. Integer programming models, as well as the algorithms which are tested by simulations, for all of the proposed scheduling problems are generated. This research enriches the study of the batching machine scheduling problems with family jobs and benefits the production planning in iron and steel industry.