Research On Algorithm For Integrated Scheduling Of Production And Transportation On Parallei Machines With Non-Identical Capacities

As a kind of complex combinatorial optimization problems,production scheduling problem widely exists in application fields,such as metal industry,pharmaceutical industry,and so on.The main concern of solving this problem lies in how to integrate and allocate the limited resources reasonably in order to obtain better solution,which is able to elevate the competitiveness of the enterprise.The research on production scheduling problem has gradually extended from classical scheduling problem to batch scheduling problem(BSP).Nowadays,the enterprise can closely combine the production and transportation of products from the perspective of gaining long-term benefits,which can further improve the customer service level,and thus promote the study on the integrated scheduling problem(ISP)of production and transportation.The integrated scheduling problem of production and transportation considers both the production and transportation of products simultaneously,and further expands the BSP,which is referred to as the ISP.This thesis studies the ISP on parallel batch processing machines with non-identical capacities to minimize the total weighted delivery time of jobs.The BSP on single machine is proved to be NP-hard.Moreover,the two-stage ISP is more complicated than the BSP.Therefore,the studied ISP in this thesis is also NP-hard,and its study has important significance in directing production management and decision-makings for manufacturing enterprises.Firstly,this thesis introduces the research background and the significance of the ISP,as well as the current researches on the BSP and the ISP.Then,besides the basic concepts and classifications of the BSP,the methods to solve the BSP are summarized,including exact algorithm and approximation algorithm.Next,the studied ISP on parallel batch processing machines with non-identical capacities in this thesis is described.The algorithm LB is given to calculate the lower bound of the st-udied problem,which is used to evaluate the performance of other algorithms.Two heuristic algorithms,H1 and H2,are proposed according to the non-identical capacities of machines.Moreover,an integrated scheduling algorithm based on ant colony optimization(ISACO)is proposed to address the problem.In algorithm ISACO,three candidate lists are constructed to reduce the search space.And the heuristic information based on the change of the normalized weight of batch is designed to effectively control the search direction of the ant.In addition,a local optimization strategy is applied to improve the solution quality.Then,the performance of the proposed algorithms is verified according to a series of simulation experiments.Based on the lower bound obtained by algorithm LB,the algorithms,H1,H2 and ISACO,are compared with a state-of-the-art algorithm PSO in terms of solution quality and run time.The results show that the performance of the ISACO algorithm is superior to the other algorithms.Finally,the integrated scheduling problem studied in this thesis and the proposed algorithms are summarized,and the future research directions are prospected.