An Improved Tabu Search Algorithm For Flow-shop Scheduling Problem

Scheduling is one of the important decisions that managers need to make in the business process.It can involve various production scenarios such as manufacturing,transportation,and distribution.An effective scheduling strategy can not only make full use of production resources,but also improve user satisfaction degree.The present studies the scheduling problem of minimizing late work in the flow-shop environment,and designs an improved tabu search algorithm to solve it.Flow-shop machine environment means that n tasks stay on m machines for processing according to a certain processing order.Each task has its own processing time and due date.Correspondingly,the part completed after the task due date is called the loss of late time of the task.In the case of a large number of machines or a large task scale,the accurate algorithm can no longer be solved in effective time,so this present research uses an improved tabu search algorithm to deal with this problem.The specific process of the algorithm includes generating a neighborhood solution set according to a given solution or a random solution and according to the corresponding neighborhood rules,and gradually finding the optimal solution;During the iteration process,a short-term table is set to record the solutions accessed in a short period of time to reduce unnecessary repeated searches.Set up a long-term table to record the local optimal solution for comparison with the global optimal solution,which is used to judge the specific operation process of special criteria;Combined with the scheduling problem in this paper,the neighborhood solution set,tabu list and search strategy in the tabu search algorithm are redefined.The size of the neighborhood solution set is set in proportion to the amount of tasks;When judging whether the special criterion is satisfied,according to whether the global optimal solution is updated,the number of neighborhood solution sets of the current solution is also set corresponding change rules;Two criteria are set in the algorithm end criterion to judge at the same time,one is the number of times that the global optimal solution has not been updated,and the other is the maximum number of iterations of the overall algorithm.If one of them is met,the algorithm operation is terminated and the result is output.During the test experiment,the algorithm is evaluated using a standard test set.Compared with the original tabu search algorithm,the quality of the solution obtained by the improved tabu search algorithm is improved,and the processing time is greatly shortened.In general,the improved tabu search algorithm can be used as a feasible solution to the problem of flow-shop scheduling.