Ant Colony Algorithms For Solving Order Acceptance And Parallel Machine Scheduling Problems

Order accepting and Scheduling (OAS) is very essential in the daily producing of a manufacturing enterprise. In common, Order accepting and Scheduling are in the charge of market department and manufacturing department respectively. However, the two departments always conflict with each other as a result of the information asymmetry. The market tends to accept orders as many as possible, while given the following restrictive factors such as Deliver Promise, off-take potential the manufacturing can not produce them all. In order to reduce the order delay, promote the level of order accepting and delivery and improve the customer satisfaction, we must select the orders reasonably. From the view of supply chain, the company should coordinate the order accepting in market department and scheduling in manufacturing department to lead to the maximum revenue.Order accepting and Scheduling (OAS) combined problems are NP-hard in general. It is difficult to acquire satisfied solutions to adopt the traditional optimization algorithms. As a kind of swarm intelligence algorithms, Ant colony algorithms can be well applied to the other combinational optimization problem. We see the maximum revenue as optimization object. Firstly, this paper adapts the ant colony algorithms to make it well be applied for the OAS in the circumstance of the definite setup-time parallel model. The modification of probability selection function contributes to the choosing the orders with greater benefits and urgent date of delivery The maximum-minimum ants pheromone update method can well balance the solution quality and time quality. Secondly, due to the drawbacks such as a slow rate of convergence, local optimal solution, hybrid optimization strategy of ant colony-genetic algorithm was proposed to solve the model. This hybrid algorithm effectively takes the advantages of ant colony and genetic algorithm. The quick global search speed of genetic algorithm provide Initial pheromone matrix and meanwhile the positive feedback of ant colony algorithm can search the maximum solution with the matrix.Above all, Lots of simulation n experiments were done to test the validity of the above algorithm. The simulation results shows that improved ant colony algorithm can be well applied to the solving of parallel machine model.