Research On Job-shop Scheduling Problem With Operation Sequence Flexibility

Job-shop scheduling problem is a typical NP-hard Problem,which has become a hot topic for current research scholars.With the change of market competition environment,flexible manufacturing systems have been introduced into the production enterprise in order to meet the diversified requirements of the customers and to enhance enterprise’s core competitiveness.As the application of flexible manufacturing system in job-shop,job-shop scheduling problem gradually changed into the Flexible Job-shop Scheduling Problem.Job-shop mainly includes three kind of key flexibility: machine flexibility,routing flexibility and operation sequence flexibility.The FJSP research mainly focused on machine flexibility and routing flexibility,which have achieved good research results.But job-shop scheduling problem with operation sequence flexibility has not got sufficient attention,leading to that the research progress is slow.The main reason is lack of a kind of generic description method.This paper is mainly focused on job-shop scheduling problem with operation sequence flexibility.Firstly,the description methods of operation sequence flexibility are reviewed and analyzed.For the existing problems of present description methods,according to the operation object sequence constraint matrix,a kind of description model with completeness of operation sequence flexibility is proposed.Secondly,according to the new description model,Allowed list algorithm and Tabu list algorithm of a job have been established to minimize the maximum completion time as the optimization goal.The model of job-shop scheduling problem with operation sequence flexibility is set up.Finally,based on the simulated annealing ant colony optimization(SA-ACO),the algorithm of Allowed list and Tabu list for the ant’s path is established,to implement the integrated hybrid scheduling algorithm solving job-shop scheduling problem with operation sequence flexibility.Experiments have been done to verify the validity of the proposed description model and the proposed algorithm.The results show that the proposed description model of operation sequence flexibility is completeness.The proposed simulated annealing ant colony optimization based on the established mathematical scheduling model has certain advantages.The effectiveness and stability of the proposed algorithm has been proved by the experiments.The research results can guide the research of job-shop scheduling with operation sequence flexibility.