| Production scheduling, aims at reaching the optimization of the selected production targets under all kinds of restrictions such as limited resource, strict delivery date, unchangeable processing sequence etc., plays a key role in production management. Good scheduling will bring about more efficient employ of resource, improved product quality, reduced cost, shorter delivering period and so on, which significantly contribute to raising the enterprise competitiveness in market economy.The Hot Strip Mill Production Scheduling Problem, which arises in the steel industry when scheduling steel coil production, is studied in the thesis. The production process is firstly specified. It can be modeled as a generalization of the Multiple Traveling Salesman Problem. Roll plan type, the largest length of warm strips and staple strips, width, thickness and rigidity of hot strip are considered in the MTSP model, with the objective to minimize the punishment value of width, thickness and rigidity of adjacent hot rolling strip and make sure optimal process order of hot rolling strips on the finish rolling mill. An integration approach based on heuristic strategies and Branch-Bound algorithm is proposed for solving MTSP. In this method, associated with each node of the branch-decision tree, a parametric solution of the relaxed assignment problem and a feasible solution obtained by patching algorithm are used to tighten the lower and upper bound; A hueristic strategy that mix threshold constraint based depth-first-search and weighted random breadth-search is adopted to seek the optimal solution. Therefore a feasible solution very closed to the optimal solution can be found in a comparatively short time. Computational results on production data from Bao are presented and analyzed. Comparison with Tabu Search indicates that the proposed method can produce significantly better schedules when the slabs of similar width are very much.The proposed methods can be employed to solve any Asymmetric TSP efficiently, which was proved by the computational results on data in the TSPLIB. Since many scheduling or optimalize problem can be modeled as a generaliztion of TSP, the proposed algorithm is of a good prospect of being widely used. |
