| Manufacturing systems are becoming more and more complicated, due to the large number of machines, diverse products and various processing methods. The shop scheduling problem has developed to dynamic scheduling problems, which is the hot research topic in recent years. Many researchers focus on centralized approaches, where some disadvantages exist in solving practical shop scheduling problems. This work believes that due to the facts, distributed scheduling is needed to solve this problem. In addition, distributed approach has its advantage to deal with dynamic problems.This work conducted research on the application of distributed scheduling for shop scheduling problem, where the framework is pure distributed. Moreover, this work adopted minimized earliness-tardiness penalties as the scheduling objective. This work brought standard mathematical programming tools, such as 0-1 integer programming, Lagrangian relaxation and subgradient algorithm into auction mechanism, which was used as the interaction mechanism among Agents in this distributed scheduling algorithm. This methodology provided mathematical tool for distributed shop scheduling problem solving. The distributed scheduling algorithm was used to solve single-machine scheduling problem, job shop scheduling problem, and shop dynamic scheduling problem respectively. The results indicated that this algorithm is effective and has good solution quality. Meanwhile, the successful solving for job shop scheduling problem and job shop dynamic scheduling problem means that this algorithm has the ability to solve other common shop scheduling problems.Firstly, this distributed scheduling algorithm was used for single machine scheduling problem solving. The computational experiments indicated that the distributed scheduling algorithm is effective and has good solution quality.Secondly, this distributed scheduling algorithm was used for job shop scheduling problems solving. Computational experiments proved its effectivity and good solution quality. Finally, this distributed scheduling algorithm was used for dynamic scheduling problems solving. This work researched on new job arrival and machine breakdown respectively. The computational experiments showed that the distributed scheduling algorithm is effective in solving dynamic shop scheduling problems, and it has the potential to solve the real scheduling problem in the shop floor.This work apply this algorithm to solve some classical shop scheduling problems and to solve dynamical shop scheduling problem successfully, which provide a effective algorithm for exploring the real dynamical shop scheduling problems solving. |
