Research On Production Scheduling Problem Based On Ant Colony Algorithm

Scheduling is one of the most pivotal part in manufacturing systems. It influence the efficiency of production directly. Under this background, this thesis has deeply studied on Job Shop Scheduling Problem (JSSP), which is one of the most famous production scheduling problem, using ant colony algorithm. It consists of three parts as follow.The first part of this thesis proposes a machine-based decomposition method for JSSP based on ant colony algorithm to decrease the large computation of the ant colony algorithm when solving JSSP. The ant just gives the partial solution on one machine each time and the partial solution combining with the last solution on other machines construct the scheduling result this time. This method improves the efficiency of ant colony algorithm to JSSP. A new state transition probability rule and the method of giving the ant start point are also presented. Compared with the original algorithm, the proposed algorithm is simulated for Benchmark instances and it illustrates that the improved algorithm shows much better and more efficient results.The second part proposes a time-based decomposition method, ant-rolling algorithm, which benefit from rolling window optimization in predictive control theory, to solve certain parameter JSSP. According to the operation's arrival time, it divides the operations that waiting for processing into two sets. One is operations which are waiting for processing and another is operations that could not process at once. The algorithm put the operation satisfied the choosing regulation, which are waiting for processing, in the rolling window operation set. And it applies the improved ant colony algorithm to optimize the sequence of the operation in rolling window operation set. The computational results show the ant-rolling algorithm with continuous rolling strategy or period rolling strategy is effective and outperform dispatching rules.In the third part, it applied ant-rolling algorithm with period combined event-driven strategy to solving JSSP in the uncertainty manufacturing environment which simulated by the rolling scheduling simulation model based on event-driven. Three dynamic events, machine breakdown & reparation, new job arrive and old job cancellation, are considered. The simulation results show this algorithm adapt to the complex manufacturing environment.