| The steel industry is a kind of typical manufacturing industry with large volume manufacture equipments, high production cost and complex technical procedure. For meeting the requirement of multi-varieties and small-batch, jobs with the similar technical requirement are grouped into batches to be processed. The mass production mode can decrease the production cost as well as increase the utility rate of equipments, thus it has became the main production organization mode in the steel industry. The types of batch include serial-batch, parallel-batch and semi-continuous batch according to the processing mode of machine. In this paper, taking the typical operations in the steel industry as background, the research on a new kind of batching and scheduling problems derived from the practical parallel-processing operations is systematically conducted. This research can extend and improve the existing theory of batching and scheduling problems for parallel-batch, and its application also has a great significance in increasing the throughput of operation, decreasing the production cost as well as improving the quality of products.The key feature to distinguish the parallel-batch processing mode from the serial-batch processing mode, is that several jobs are processed in a single machine simultaneously but not in sequence. Different from the common batching and scheduling problems for parallel-batch in previous literature, the problems in this paper are mainly of the following new characteristics:1) Multiple attributes need to be considered when making batching decision; 2) Not all of jobs need to be assigned to the non-identical parallel batch-processing machines; 3) The processing time is relevant with the waiting time for a certain job. These new characteristics make the theory on the common batching and scheduling problems for parallel-batch cannot be directly adopted. In this paper, taking the soaking operation and the batch annealing operation as background, the research on a family of batching problems for parallel-processing operations, including batching problems in the separate and the central heating modes in the soaking operation, static and dynamic batching problems in the batch annealing operation, is conducted in the way of modeling description, theoretical analysis, solution method designing and application. Furthermore, the scheduling problems for single batch-processing machine and the parallel batch-processing machines with deterioration consideration are derived. And the corresponding large-scale neighborhoods based intelligent optimization algorithms are proposed to approximately solve them within a short time. The main contents of dissertation are summarized as follows:1) Taking the soaking operation in the steel industry as background, a batching problem under discrete heating mode is derived. In this mode, soaking pits belong to the same furnace are heated separately, and hence each soaking pit can be seen as a batch-processing machine. Then, the batching problem under the discrete heating mode is to select ingots to form batches to be soaked in the given soaking pits. The main feature of the problem is that soaking pits have non-identical initial temperature, not all of the ingots must be assigned to soaking pits, and the batching quality is measured by multiple factors such as the rolling temperature difference among ingots and the initial temperature difference between ingot and soaking pit. In this paper, taking improving the utility of each soaking pit as well as decreasing energy consumption as objective, a mathematical programming model is formulated. By reformulating the problem as a set-packing model, a branch-and-price algorithm is designed for solving the problem exactly. In the solution method, column generation algorithm is embedded into the branch and bound frame to provide a tight lower bound for each node in the branch tree. Two branching strategies are proposed to branch the fractional nodes. The computation results on the randomly generated testing instance indicate that the proposed branch-and-price algorithm can solve the middle scale instance in a feasible computational time and two proposed branching strategies are effectual for the problem.2) Taking the soaking operation in the steel industry as background, a batching problem under central heating mode is derived. The significant difference from the batching problem under discrete heating mode is that the soaking pits belong to the same furnace are heated centrally, and hence the capacity constraints of the soaking pits as well as the synchronous heating requirement of the soaking furnace need to be considered simultaneously when making batching decision. Due to the new feature in the batching problem under central heating mode, the batching plans for the soaking pits belonging to the same furnace should be centralized considered, that significantly increases the solving complexity of the batching problem. In this paper, based on the structural feature of the problem, a set-packing model is formulated and a branch-and-price algorithm is proposed to solve it optimally. In the column generation which is used to obtain the lower bound for each node in branch tree, each pricing sub-problem can be seen as a multiple knapsacks problem and hence there isn’t any polynomial optimal solution method to solve it. Therefore, a two-stage iterative method is designed to optimally solve the pricing sub-problem and a set of valid constraints based on ingots aggregation is proposed to overcome the shortcoming that only one infeasible column is eliminated at every iteration. The linear relaxation experiment and the integer programming experiments are conducted on a set of randomly generated testing instance. The computational results demonstrate that the proposed valid constraints are valid to accelerating the solving the processing of pricing sub-problem and the proposed branch-and-price algorithm can obtain the optimal solutions for the middle scale problems in a reasonable CUP time.3) A practical static batching problem arising in the batch annealing operation in a steel industry is investigated. The problem is to select coils from a set of waiting coils to form batches to be annealed in empty batch annealing furnaces and choose a median coil for each furnace. The main characteristics of the problem can be summarized as follows: a median coil should be selected for each batch; multiple attributes difference between the coils, the mismatching between furnace and the coils, and the charging weight are considered as the factors affect the batching quality. In this paper, based on the analysis of the key factors which can affect the production operation level. a mathematical programming model is formulated for the problem with the purposes of increasing the throughput, decreasing the production cost, improving the production quality and satisfying the management requirement. Aiming at overcoming the difficulty in high solving complexity caused by practical constraints, a tabu search heuristic is proposed to solve the problem in a short time. Three simple search neighborhoods combining with a variable neighborhood strategy is proposed to improve the solution. To make the tabu search heuristic more effective, a sophisticated variable depth neighborhood search strategy is developed to strengthen the searching process. Then, for objectively evaluating the performance of tabu search heuristic, a column generation algorithm is adopted to obtain the upper bound of the problem. The experiment results on practical data can show that the tabu search heuristic can generate near-optimal solutions in a reasonable short time, and the proposed variable depth neighborhood for strengthening searching process is effectual. Finally, a computer system that embeds the proposed algorithm is developed and has steadily run in a steel complex in China. The application of the system has overcame such shortcomings of manual planning as poor quality of annealing, low charging weight, time consuming and strong interference of artificial factors, and hence improved the production operation level of the complex.4) Taking the batch annealing operation in the steel industry as background, some static bathing problems under different production conditions are derived. The problems include the static batching problem with coils which are of similar size, the static batching problem with the given median coil, the static batching problem without considering the mismatching between the coils in the same family and the static batching problem under the production mode of large-batch and less-variety. The structure features and the optimal properties for the above four problems are analyzed. Then, based on the dynamic programming or linear programming, the polynomial optimal algorithms are designed for the problems respectively.5) Taking the batch annealing operation in the steel industry as background, a dynamic batching problem is derived. The main difference from the static batching problem in the batch annealing operation is that both of the coils and furnaces are dynamic available. In the dynamic batching problem, waiting the un-available coils may improve the batching quality, but may also reduce the production efficiency. Therefore, the balance between batching quality and production efficiency is considered. Based on the discrete-time modeling strategy, a mathematical programming model is formulated for the problem and Lagrangean relaxation algorithm is proposed to solve it. Furthermore, an improved Lagrangean relaxation algorithm which incorporates the variable splitting method is proposed to tighten lower bound. Computational experiments are carried out to test the performance of the algorithms both on a set of standalone one-horizon problem instances and in a rolling horizon frame. The results show that the both of the classical and improved Lagrangean relaxation algorithm can obtain near solutions in a reasonable time, and the improved Lagrangean relaxation algorithm outperforms the classical one.6) Taking the batch annealing operation in the steel industry as background, a scheduling problem for single batch-processing machine is investigated. The problem is to group the jobs into batches without violating the capacity constraint. The objective is to minimize the makespan. The problem has been proved to be NP-hard. Hence, a tabu search heuristic is proposed to solve it appropriately. In the solution method, two basic neighborhoods are proposed based on the structural feature of the problem. Furthermore, to avoid search process being tapped in local optima, two novel variable depth neighborhoods are proposed. A group of random instances are generated to test the performance of the tabu search heuristic we proposed. The experimental results show that the tabu search heuristic is effectual for solve the problem and the variable depth neighborhoods can significantly help the search process avoid being trapped in local optima.7) Taking the soaking operation in the steel industry as background, a scheduling problem for parallel batching machine with the deterioration consideration is derived. The main feature of the problem is that the processing time deteriorates along with the increment of waiting time for a certain job. The problem is to group all jobs into batches and determine the processing sequence of each batch on the parallel batch-processing machine with the consideration of available time of jobs and the capacity constraints of machine. A linear programming model is formulated. Considering the complexity of the problem, a filter-and-fan based heuristic is proposed. Three neighborhoods based on the characteristics of the problem are designed and used in the filter-and-fan method. A solution selection strategy is proposed to raise the sensitivity of search. To probably avoid the search being trapped in a local optimum, a reconstructive strategy is proposed to strengthen the dispersity of solutions in the search process. The computational results show that for most of instances with small scale the heuristic can obtain optimal solutions. For all instances with large scale, the heuristic significantly outperform the standard commercial solver both on run time and quality of solution. |
PDF Full Text Request