Research On Single Machine Scheduling Considering Maintenance And Dynamic Flexible Job Shop Scheduling Algorithm

The rapid development of the manufacturing industry has intensified the global marketization competition,and customer demands have become increasingly personalized and diversified,which makes the discrete production mode of multiple varieties and small and medium-sized batches gradually rise and occupy the mainstream of the market,this changeable market environment brings higher challenges to the manufacturing industry.If manufacturing enterprises want to improve their survival and competitiveness,they must control costs in the shortest possible time and produce different products of high quality to respond to the market.The shop scheduling is an optimization problem that utilizes the existing resources reasonably and effectively to complete the assigned tasks to meet the specific performance objectives.Many dynamic events such as machine breakdown often occur in the actual production process,and sometimes it is necessary to arrange preventive maintenance for the machine.Therefore,on the basis of theoretical analysis and optimization improvement of the algorithm,this paper carries out a specific research on the corresponding shop production scheduling problem.The primary details of the thesis are indicated below:(1)A new single machine scheduling problem considering preventive maintenance and worker breaks is proposed,in which the scheduling of job sequence,maintenance activities and worker breaks are considered simultaneously.For the problem,two types of mixed binary integer programming models are constructed.The classic LPT heuristic algorithm is applied to this problem,of which the worst-case ratio is first proved to be 3/2.This thesis also demonstrated that unless P = NP is satisfied,there exists no polynomial time approximation algorithm,of which the worst-case ratio is lower than 3/2,and this indicates that the LPT is likely to be the optimal polynomial time approximation algorithm for solving the proposed problem.These two mathematical models are solved by the CPLEX and the LPT algorithm based on the constructed 20 test instances,and experimental results show the high performance of the LPT algorithm both on solution quality and computational efficiency.(2)A dynamic flexible job shop scheduling problem(DFJSP)considering four kinds of dynamic events which are machine breakdown,new order arrival,jobs cancellation and change in the processing time of operations is studied.A rescheduling method which based on Monte Carlo Tree Search(MCTS)algorithm is designed for the problem with an optimization objective of minimizing the makespan.Several optimization techniques such as rapid action value estimates heuristic and prior knowledge are adopted to enhance the performance of the MCTS-based rescheduling method.To greatly reduce the response time to dynamic events,when dynamic events occur,multiple continuous specified time windows with fixed length are designed for the proposed method,according to which the corresponding subsequent partial schedule for the remaining unprocessed operations is progressively generated.(3)In order to evaluate the effectiveness of the improved MCTS algorithm and the designed rescheduling method,two sets of simulation experiments are implemented.Based on the MK series static benchmark instances,the first set of experiments verifies the effectiveness of the four optimization techniques used to improve the MCTS algorithm.In the second set of experiments,18 DFJSP test instances are constructed firstly,then the proposed rescheduling method based on the improved MCTS algorithm is compared with some commonly used completely reactive rescheduling methods and the GA-based rescheduling method.The experiment results indicate that the rescheduling method proposed in this paper is an efficient and promising method for dynamic scheduling both on solution quality and computation efficiency.