Modeling And Solving The Parallel Machine And Flow Shop Scheduling Problem Based On Dual Agents

The scheduling problem has always been a hot topic in the academic and industrial circles.The problem of multi-agent scheduling is a new sort of sorting problem in the past ten years.In the process of production,each agent has its own needs,and they jointly use the production and processing resources.This problem is in line with the actual production status of multi orders and multi orders in the manufacturing industry.It is of practical significance,so it is widely concerned by scholars.In order to solve the problem of production scheduling,there are many methods,such as accurate algorithm dynamic programming,intelligent algorithm and approximate algorithm.In this paper,the representative two-agent scheduling problem of multi-agent scheduling problem is analyzed and solved.The main works are as follows:(1)For the scheduling problem of two-agent parallel machines with due time window constraints: Firstly,set up the problem model.Secondly,we define the problem solution state expression based on the due time window constraint,and combine with the sorting rule of the processing time from big to small,we design the dynamic programming method to solve this problem,and further prove that the algorithm is pseudo polynomial time algorithm.Then,the time validity of the proposed method is verified by the computation time simulation on the small scale problem.(2)For the scheduling problem of two-agent parallel machines with arrival time: Firstly,set up the problem model and prove the problem is a NP-Hard problem.Secondly,we define the problem based on the completion time problem solution state expression,and combine the proposed sorting rules of arrival time from large to small,design the dynamic programming method to solve the problem,and further prove that the algorithm is pseudo polynomial time algorithm.The validity of the proposed polynomial time algorithm is verified by comparison with the multi-objective genetic algorithm in the important international periodicals.Then,the static interval division method is used to cut the state of the problem solution space,and then a fully polynomial-time approximation scheme is obtained.(3)For the two-agent flexible flow shop scheduling problem whose optimization objective is to minimize the maximum completion time: Firstly,set up the problem model.Secondly,a modified teaching–learning-based optimization algorithm is proposed to solve the problem.In the proposed algorithm,we use LOV encoding algorithm in individual real vector will be converted to an integer scheduling,making the teaching–learning-based optimization algorithm can be used to solve the scheduling problem;and by adding adaptive teaching factors and roulette selection strategy,and further enhance the global searching performance of the algorithm and design;the local search based on Insert and Inverse neighborhood,improve the local search ability of the algorithm.Then,the effectiveness of the proposed algorithm is verified by simulation comparison on different scale problems.