Exact And Heuristic Algorithms On Flow-shop Scheduling Problem With Late Work Criterion

The research on flow-shop scheduling problem to minimize total late work.Flow-shop scheduling problem can be described as n jobs need m machines to process.Each job needs the m process,and each process requires a different machine.The N jobs are processed in the same sequencer on m machines.Job's late work is a kind of punishment related to the delivery period,which is proportional to the part of the job that lags behind its delivery.For the different scale of the problem,the branch and bound algorithm is designed to solve small cases,and the genetic algorithm is used to solve the big scale problems.For two machine flow-shop problem,we reanalyzes the branch and bound algorithm which published in 2006.Using counter-examples to point out the error of lower bound in the paper.Then,we design a new lower bound rule,and propose a new branch and bound algorithm.The algorithm's initial solution is gave by generic algorithm.Using upper bound and lower bound trim rules,dominate rules to remove the invalid nodes.Which can remarkably reduce the search scope.Regarding to multiple machines flow-shop problem,we extend the above genetic algorithm.According to the characteristic of the problem,designing the chromosomes coding methods,the rules of crossover and mutation,And the termination condition of the algorithm.For the multiple machines flow-shop model,when the scale of the problem increases slightly,the exact algorithm is very difficult to find the optimal solution in acceptable time.There for,the approximate solution of the problem studied by genetic algorithm,and compared the experiment result with other heuristic algorithms,it proved that the genetic algorithm can be better than other heuristic algorithm to improve the problem's initial solution.The experimental results show that the above two algorithms have good efficiency in dealing with small scale instances and medium-large scale instances.The branch and bound algorithm with the lower bound rule can effectively trim invalid branches in search tree,and the dominate rules can effectively remove invalid nodes,which greatly improves the search efficiency of B&B algorithm.The GA can solve large scale problems in a short period,and the performance is far more than simple heuristic rules.It can be provided a better initial solution for solving large scale problems.