This research, which is conducted in the area of production planning and scheduling problems of batch processing in Iron & Steel industry, focuses on the optimal properties and solution procedures with regard to some particular theoretical problems and a few typical scheduling problems. It is believed that such kind of research is theoretically and practically significant, and in conformity with the trend of the research and development in this area. Main works and contributions included in this dissertation are: 1. Study of the algorithms for the optimal order planning. In the first place, the NP- hardness of the single-machine order planning to minimize the earliness and tardiness under the just-in-time production strategy is proved. Afterwards the optimal properties of adjacent groups in optimal order planning are discussed by extending Peng's research result concerning the single-machine earliness and tardiness problems. And then an optimal property-based filtered beam search algorithm is proposed with the computational complexity of the algorithm investigated under the worst case analysis. Second, the optimal solution to the problem of the maximum absolute lateness of orders with common due date is proposed and testified. The computational complexity of such optimal algorithm is O(b log b). Finally, two models of minimizing the order's maximum lateness, namely the 0-1 mixed integer-programming model and the constraint programming model, are proposed. The simulation results indicate higher efficiency of the optimal solution of constraint programming. Some good results have been obtained from their application to middle-small size problems. 2. Batch processing scheduling problem with major and minor setup times. In the real manufacturing process, there usually exists a trade-off between achieving the batch size efficiency and meeting customers' due date. In view of this, batch processing problem with major and minor setup times to minimize the job's maximum lateness is brought under detailed consideration. By applying the concept of composite job, some formulae for the due date of the composite job and the family due date are presented. A set of necessary conditions for group sequencing under the group assumption has been identified. In the end, a property-based tabu search algorithm is proposed and simulated. 3. Research on the GA-based hybrid optimal strategy. With a profound analysis of the genetic algorithm's convergence, the research discusses the important role of improved coding technology and improved crossing and mutation operators in promoting the convergence of the GA. On account of limitations of the GA and TS, a hybrid algorithm incorporating the two heuristics is recommended in dealing with the multi-product scheduling problem with batch and capacity constraint. This algorithm adopts the real number coding method and generates the initial population by means of the TS, which is expected to enha
修改评论