Abstract: The job shop scheduling problem with unrelated parallel machines is investigated. Multiple objectives such as production cost and on time delivery rate for manufacturing system are taken into account in the proposed scheduling model. Considering the superiority of ant colony algorithm in solving the complex optimization problem, the mapping relationship between scheduling problem and ant colony parallel search is structured. The schedule process consists of two stages: tasks assignment and task sequencing. For each stage, the ant colony optimization is designed respectively so that a two-stage ant colony system(TSACS) with inheritance relationship is proposed. It can compress the solution space and improve the solving speed. Key parameters of TSACS are identified through the uniform experiment and statistical analysis. Computational experiments of 8 examples with different sizes are conducted. The results indicate that the proposed TSACA significantly outperforms the improved genetic algorithm in both optimization results and computational efficiency. The implementation of TSACS in real-life case also demonstrates that the waiting time between operations can be reduced and the product delivery cycle can be shortened.

Key words: Ant colony algorithm, Job shop scheduling problem, Multi-objective optimization, Unrelated parallel machines