Research Of Improved Meta-heuristic Algorithms For Scheduling Problems In Nonferrous Industry

The non-ferrous metals industry is an important basic industry for the national economy development.Due to the rising prices of raw material,the high resource/energy consumption,and the low production equipment operating efficiency,most non-ferrous metals manufacturing enterprises in China are facing severe challenges,i.e.meager profits.It is an urgent issue for the enterprises to reduce the production cost,to improve the production efficiency and the utilization rate of large production equipment based on the current processing equipment and production conditions.This dissertation takes the aluminum production as background,and studies the modeling and optimization for non-ferrous metals industry scheduling.New scheduling problems and new formulations are extracted from the practical production to expand and enrich the research of the existing scheduling field.On the other hand,its potential applications could improve the efficiency of the production equipments,reduce the waiting time of materials between the equipments,reduce the energy consumption,and improve the economic benefits and market competitiveness of the enterprises.This dissertation first investigates the improvement and hybrid strategies of meta-heuristic algorithms,such as differential evolution and scatter search for the classical production scheduling problems.Then application research is done with meta-heuristic algorithms based on the proposed mixed integer programming models,which are applied to the practical scheduling problems in aluminum industry,for example,the integrated batch and scheduling problem in the aluminum twin roll casting,the batch scheduling problem of aluminum electrolysis and caster,and the order rescheduling problem.The content is summarized as follows.1)The hybrid scatter search and variable neighborhood search algorithm is proposed for the single machine total weighted tardiness problem with sequence-dependent setup times.The improvement strategies of the proposed algorithm include initial population generating procedure involving both random strategy based heuristics and construction heuristic,a variable neighborhood search as local search to improve the population and the combined solutions,and three combination operators containing a discrete differential evolution operator to combine the solutions in the subsets.A variable-length reference set strategy is also proposed to improve the solving ability of the scatter search.The effective and competitive of the proposed algorithm is tested on benchmark instances comparing with the best known meta-heuristic algorithms.2)Job shop scheduling problem,which is considered as a classic problem in the literature and one of the most difficult combinatorial problems,has been investigated.An ensemble of discrete differential evolution algorithm is presented to solve the problem.The individual representation is based on the operation-based encoding scheme.In order to make use of multiple operators simultaneously,three mutation operators and three crossover operators are proposed that each combination of them is assigned to one of the parallel populations.A variable neighborhood search based local search is adopted to improve the new trail individuals.Computational results on the benchmark instances show that the proposed algorithm performs better than the single populated variants.3)The parallel assembly lines balancing problem has been studied.It is the most common case in industry that two or more lines produce the same product or different types of products at the same time independently.The parallel assembly lines could bring better balances and increased productivity.A scatter search based heuristic approach is proposed for this NP-hard problem.Through the analysis of the structural characteristics of the problem,new population generation method,new improvement method and new solution combination method are developed in the algorithm implementation process.Computational results of the benchmark instances indicate that the proposed method is stable and can find some better upper bound compared with the known best feasible solutions.4)The integrated batch and scheduling problem in the aluminum twin roll casting process has been investigated.The goal of the problem is to determine the assignment of molten aluminum in electrolysis cells to the holding furnace(batch)before the twin roll caster and determine the sequence of batches considering the sequence-dependent setup cost caused by alloy,width,thickness of the orders'requirements.A mixed integer nonlinear programming model and scatter search based heuristics are presented for this problem.Problem-specific diversification generation and combination methods are adopted in these algorithms.Computational experiments show that the proposed methods are efficient while comparing with the GAMS software.5)A novel unit-specific event based continuous-time MILP model and an improved discrete differential evolution algorithm are proposed for the batch scheduling problem of electrolysis and caster in aluminum industry.The ultimate goal of this problem is to determine the assignment and scheduling of orders considering the sequence-dependent setup time caused by production technology and the orders' requirements in electrolysis cells,and determine the batching and scheduling of orders in the following casters.In the model,the event point is stage-specific,and effective bounds are proposed to tighten the model.A new individual representation scheme,an improved hybrid pointer-based mutation and a new point-cross crossover operation are proposed to enhance the performance of the algorithm.Computational experiments show that the proposed method is efficient comparing with CPLEX for both small and large size instances.6)The practical order rescheduling problem has been investigated to adapt various changes that affect the normal production.The problem is formulated as a mixed integer programming model considering the original objective,i.e.the deviation from the initial scheduling and the equilibrium of production capacity.A discrete differential evolution algorithm with new mutation and crossover operators is proposed to obtain near-optimal solutions.The computational experiments are implemented on both randomly generated instances and instances from the real production.Experimental results illustrate that the proposed algorithm could obtain better solutions compared with four standard differential evolution algorithms and the manual method.