Deep Reinforcement Learning Solves Job-shop Scheduling Problems

To solve the sparse reward problem of job-shop scheduling by deep reinforcement learning,a deep reinforcement learning framework considering sparse reward problem is proposed.The job shop scheduling problem is transformed into Markov decision process,and six state features are designed to improve the state feature representation by using two-way scheduling method,including four state features that distinguish the optimal action and two state features that are related to the learning goal.An extended variant of graph isomorphic network GIN++is used to encode disjunction graphs to improve the performance and generalization ability of the model.Through iterative greedy algorithm,random strategy is generated as the initial strategy,and the action with the maximum information gain is selected to expand it to optimize the exploration ability of Actor-Critic algorithm.Through validation of the trained policy model on multiple public test data sets and comparison with other advanced DRL methods and scheduling rules,the proposed method reduces the minimum average gap by 3.49%,5.31%and 4.16%,respectively,compared with the priority rule-based method,and 5.34%compared with the learning-based method.11.97%and 5.02%,effectively improving the accuracy of DRL to solve the approximate solution of JSSP minimum completion time.

Configuration Selection for Reconfigurable Manufacturing Systems by Means of Characteristic State Space

The configuration selection for reconfigurable manufacturing systems（RMS） have been tackled in a number of studies by using analytical or simulation models. The simulation models are usually based on fewer assumptions than the analytical models and therefore are more wildly used in modeling complex RMS. But in the absence of an efficient gradient analysis method of the objective function, it is time-consuming in solving large-scale problems by using a simulation model coupled with a meta-heuristics algorithm. In this paper, a new approach by means of characteristic state space is presented to improve the efficiency of the configuration selection for an RMS. First, a characteristic state equation is set up to represent the input and the output resources of each basic activity in an RMS. A production process model in terms of matrix equations is established by iterating the equations of basic activities according to the resource flows. This model introduces the production process into a characteristic state space for further analysis. Second, the properties of the characteristic state space are presented. On the basis of these properties, the configuration selection in an RMS is considered as a path-planning problem, and the gradient of the objective function is computed. Modified simulated annealing（SA） is also presented, in which neighborhood generation is guided by the gradient to accelerate convergence and reduce the run time of the optimization procedure. Finally, several case studies on the configuration selection for some actual reconfigurable assembly job-shops are presented and compared to the classical SA. The comparison shows relatively positive results. This study provides a more efficient configuration selection approach by using the gradient of the objective function and presents the relevant theories on which it is based.