A Neural Reinforcement Learning Approach to Learn Local Dispatching Policies in Production Scheduling

1 Introduction

Production scheduling is the allocation of lim­ ited resources to tasks over time, while one or more objectives have to be optimized. Many variants of the basic problem formulation ex­ ist and most of them are NP-hard to solve [Pinedo, 1994], meaning that exact solution al­ gorithms suffer from a non-polynomial increase of computation time. This constitutes a prob­ lem not only if the problem to solve surmounts a certain size, but also in moderately complex domains, where the occurrence of new or un­ expected events - the arrival of new jobs or the breakdown of machines - makes frequent replanning necessary. Even more, technolog­ ical changes like semiconductor fabrication or thin film production are posing additional chal­ lenges, since new problem structures - like con­ ditional loops in the production process- occur, for which conventional optimization techniques may not be applicable.

An alternative and far less time-consuming way is the application of simple heuristic dispatch- Martin Riedmiller Computer Science Department (ILKD) University of Karlsruhe D-76128 Karlsruhe riedml@ira. uka.de ing rules that select the job to process next on an idle resource depending on the current situa­ tion. However, these dispatching rules only re­ flect heuristic knowledge and do not guarantee to lead to the optimal behaviour of the overall system. Even for experienced human experts it may become arbitrarily difficult to decide whic.h dispatching rule to apply and how to tune 1t in a certain scenario, since the effects on the dynamics of the overall system can hardly be predicted.

1.1 General Idea

Here we propose an alternative way that allows to combine the desire for (nearly) optimal so­ lutions with a time-efficient computation, pro­ vided by resource-coupled dispatching rules. The idea is to have learning agents, that are as­ sociated to each resource and determine the lo­ cal dispatching policy. This policy is not fixed, but instead is autonomously learned by getting feedback of the overall dynamic behaviour of the production system. In contrast to common dispatching rules which typically only consider few characteristic features of the current situa­ tion to make the decision, a learning agent can deal with more state information and therefore figure out more sophisticated policies, which are better tailored to the process. The appear­ ance of the proposed training method does not depend on the optimization goal or constraints posed by the production process. Therefore, it is applicable to a wide range of problem in­ stances. As an example, in this article we focus on job shop scheduling problems with the goal to reduce the summed tardiness. The follow­ ing summarizes the main characteristics of the proposed approach:

• autonomous acquisition of (approximately) optimal dispatching poli­ cies (including the adaptation to the plant structure and the inherent consideration of constraints)

• reusability of acquired knowledge
• fast situation dependent decision making, ability to do reactive scheduling

1.2 Related Work

Recently, several reinforcement learning ap­ proaches have been proposed to solve certain aspects of scheduling problems. They vary in the type and their view of the scheduling prob­ lem and - as a consequence - the type of con­ trol decisions. Zhang and Dietterich [Dietterich and Zhang, 1995] propose an RL approach that learns a neural value-function to guide a repair­ based scheduler. An action in this approach is the decision for a certain repair operation. Schneider, Boyan and Moore [Schneider et al., 1998] present a value-function-based approach for the problem of demand based scheduling. The learning scheduler decides over a set of possible factory configurations to maximize ex­ pected production profit in the presence of varying demand curves. In contrast to these global approaches, a local multi-agent view of a production scheduling problem is taken in [Brauer and Weiss, 1998]. Each machine does make a local decision which job to process next based on the estimated completion time of the candidate jobs. The learning rule is based on the propagation of these estimates along the production line of a job, similar to the Q­ Routing algorithm [Boyan and Littman, 1994]. An application of average-reward RL is pre­ sented by Mahadevan and Theocharous [Ma­ hadevan and Theocharous, 1998] for the control of a transfer-line.

Our approach follows the idea of local decision making. The neural network based agent con­ siders the current situation, represented by a set of relevant (local) features, to make its de­ cision which job to process next. It learns a local decision policy (similar to heuristic dis­ patching rules) with the ability to adapt to the user-defined optimization goal. This is done autonomously, meaning that the policy is self­ improved by repeating a certain number of typ­ ical training cases.

1.3 Task description

The task considered in the following is to pro­ cess a set of m jobs on the n resources of a fac­ tory. Each job j E 1 . . . m, consists of a certain number of li basic operations Oj,I, ... Oj,l;. A basic operation must be performed on a certain resource k E 1 ... n and has a certain process­ ing time. A job is finished after completion of its last operation. If the completion time Ci of job j is larger than a certain due-date dj , then the job is said to be tardy. The tardiness Tj of a job is zero, if it is finished before or at its due­ date; otherwise it is Tj = Cj - dj. In general scheduling objectives to be optimized all relate to the completion time of the jobs. Various variants of the basic optimization problem ex­ ist which can be classified within a complexity hierarchy [Pinedo, 1994] . In the following, we look at the problem of minimizing the summed tardiness over all jobs, T = L::j Tj. Solving this deterministic problem subsumizes also the total completion time problem as well as the max­ imum lateness or maximum makespan prob­ lems. Being NP-hard, it is not possible to solve this problem with a polynomial time algorithm.

2 Description of the solution approach

2.1 Optimization problem and decision making

The global production scheduling problem can be described as a Markov Decision Process (MDP): the system's state s(t) is described by the current situation of the n resources and the processing state of the m jobs, a decision a(t) describes which job is processed next on a wait­ ing resource. The goal of scheduling is to find an optimal policy 7r* such that production costs R(s, a, t) accumulated over time are minimized

where tf denotes the time after which the last job is finished. Costs R(s, a, t) may depend both on the current situation and on the se­ lected decision and express the desired opti­ mization goal. For example, costs may arise due to the tardiness of a job, due to a resource waiting idle, or due to costs caused by the need to change a tool before continuing processing, and so on.

In our approach, the global decision a(t) is a vector of single decisions ak(t) made by dis­ tributed agents each associated with one of the n resources. If a resource is ready to process a new operation, then its agent chooses one job out of a set Ak of jobs, where Ak is the set of jobs for which the next operation Oji must be processed on resource k. The resource is then occupied for the duration of Oji· After this time, a new decision is made.

2.2 Learning Algorithm

Each agent makes its decision based on a local view sk(t) = sk(s, t) of the global plant situ­ ation at time t. Sk represents the local view of the agent. It can be thought of compress­ ing the huge amount of global state informa­ tion into features that are relevant for making the local decision at resource k. Learning here means iteratively improving the decision policy with respect to the optimization of the global costs (1). This is done by a Q-learning related learning-rule adapted to the local decision pro­ cess:

The learning rule relates the local decision pro­ cess as experienced by agent k to the global op­ timization goal by considering the global direct costs R(.) . Since the time between the decisions varies depending on the duration of the cur­ rently processed operation, the 'reinforcement term' R(s, a, t, .6.t) accumulates the global costs between t and t + .6.t:

Accordingly, if Q k converges, then the opti­ mal local value function QA, predicts the esti­ mated accumulated global costs, if in situation sk the job denoted by ak would be processed next. A policy greedy with respect to QA,, thus will choose that job next, that will lead to an optimization of the performance of the overall plant. The policy of the agent is determined by greedily exploiting the value function,

During learning, a random exploration strategy is performed that deviates from time to time from the current policy.

The agent's learning rule varies from the Q­ learning assumptions in two important issues: a) no central global decision is made, but in­ stead, the global decision is composed by indi­ vidual decisions of time-varying policies. Un­ less all policies are stable, this makes the pro­ cess seen by the local agent non-stationary (in contrast, a single Q-learning agent assumes to experience a stationary environment). b) an agent does only use compressed information of the complete state. With an agent's lo­ cal state information, the observed system be­ haviour may become stochastic or even unpre­ dictable. However, there is empirical evidence that Q-learning works in this scenario [Barto and Crites, 1996]. In the experiments in sec­ tion 3 the problems mentioned in a) are cir­ cumvented, since in this paper only situations with a single local learning agent are examined.

2.3 Choice of R(.)

Since it is our objective to mm1m1ze the summed tardiness of all jobs, we have to choose R(.) such, that the minimization of (1) is equiv­ alent to the minimization of the tardiness T. First, R(.) is the sum of the costs r 1 (.) associ­ ated with the jobs

Two formulations of ri are possible. The first is to compute the tardiness after the job is fin­ ished

(2)

The second possibility is to have costs in each time step during processing, if the job is cur­ rently too late but not ready yet:

(3)

Although both formulations are equivalent with respect to the general problem formulation, the latter choice has the advantage, that the cost function directly reflects the tardiness when it actually occurs, which may help the learning system. Therefore it is used in the experiments in section 3.

2.4 Learning System

We choose a multilayer-perceptron neural net­ work for representing the value function Q(.) for two reasons: a) the state space is continuous and therefore no finite scheme (like a lookup­ table) can represent all states. b) we want to exploit the generalization ability of the neural network to find general policies, i.e. the Q func­ tion should generalize to unknown situations. Input for the function approximator is an ade­ quate description of the current decision situa­ tion by a feature vector. The features have to comply with the following requirements: They should relate to the future expected costs and should be characteristic for the present situa­ tion. Features should represent characteristics of typical problem classes rather than of indi­ vidual instances, such that the acquired knowl­ edge can be generalized to new problem in­ stances. For this reason, few attributes are considered, mainly describing the local situa­ tion at the machine. With respect to practi­ cal applicability, features should be computable out of data available from common commercial PPC-systems. In order to keep the network input small, redundant information should be avoided. Dealing with a time-dependent prob­ lem, besides static properties dynamic features should be concerned. They are not only de­ pendent on the job or resource properties (e.g. processing time) but also on time progress (e.g. slack). Input to the neural network are lo­ cal state features sk(t) plus features coding the available decision a E Ak(t). Possible features are:

state features sk(t):

• describing general characteristics of the problem: 'tightness' T (1) and 'distribu­ tion' R (2) of the jobs with respect to their due-dates [Pinedo, 1994]
• describing the current situation: estimated tardiness, estimated makespan C (3), av­ erage slack

decision features/ job characteristics:

• describing characteristics of job j with re­ spect to the present situation in Ak: e.g. due date index (EDD) (4), relative slack, slack index (MS)(5), relative waiting time (FIFO) (6), relative processing time, pro­ cessing time index (SPT, LPT)
• describing the immediate consequences, i.e. the properties of the remaining oper­ ations if job j was selected: e.g. average remaining slack
• describing the relationship job/ operation, i.e. the significance of operation Oij for job j: e.g. relative work in process, relative buffer

3 Empirical Evaluation

3.1 Research objectives

The following experiments show the behaviour of the proposed learning approach in compari­ son to heuristic dispatching rules. In detail, we examine the following issues:

• how does the choice of input features in­ fluence the optimality of the policy found by the learning system?
• is the learned policy general, i.e. does the policy show good performance when ap­ plied to untrained situations?
• does the proposed learning scheme work, i.e. is it possible to improve the decision policy of the local learning agent with re­ spect to the global goal autonomously?
• how does the learned policy perform com­ pared to heuristic dispatching rules?

3.2 Description of the experiments

We examine two cases: a single resource case, as a demonstration for the principle working and performance capabilities, and a multi re­ source case, to show the capability of the agent to work within a multi-agent scenario. In both cases, 10 different production scenarios are used during the training phase. Each production scenario has a random number of jobs (5 to 8) with different processing times and differ­ ent due-dates. Experiments were based on a random generation of problems with different problem characteristics (number of jobs, loads, tightness of jobs, due-date-range, ... ). In the single resource case, each job has one operation, whereas in the multi-resource case, each job has a random number of basic operations. Each operation has a random duration and must be processed on a certain resource. In the multi­ resource case we also allow circles - i.e. a job may have to visit one resource multiple times - which constitutes an additional difficulty for conventional solution algorithms. The mean process duration and the mean due-date were chosen such that 'interesting' scenarios are cre­ ated, i.e. that arbitrary policies are not likely to produce acceptable solutions. As mentioned above, the production objective considered here is to reduce the overall tardiness of all the jobs. To test the generalization ability, 10 test sce­ narios were generated, which vary from the ones considered in the learning phase.

For learning, we used a multi-layer perceptron with up to 6 inputs, 10 hidden neurons and one output neuron. The learning rate was set to 0.1 (since it was not our goal to optimize the learn­ ing speed, not much effort was done to find an optimal parameter here). During learning, the jobs are selected randomly (exploration factor = 1). The performance is reported in terms of the average tardiness of the jobs when act­ ing greedily with respect to the current value function.

3.3 The one resource case

Table 1 shows the performance of some typi­ cal heuristic dispatching rules. The LPT-policy chooses the job with the longest processing time first, the minimum-slack (MS)-policy chooses the job with the minimum time between the ex­ pected termination and the due-date, and the EDD-policy chooses the job with the most ur­ gent due-date. The average tardiness per job varies considerably on the 10 training scenar­ ios. LPT performs worst with an average tar­ diness of 18.9, even worse than a random policy (12.9). MS works considerably better showing an average tardiness of 7.5, and EDD perfoms To test the learning capability of the neural dispatching agent, several combinations of in­ put features were tested (the feature numbers in table 2 correspond to the numbering in sec­ tion 2.4). In general, with a sensitive choice of input features the performance of the learning system did improve considerably with the num­ ber of production runs (remember that the av­ erage tardiness of a random policy is 12.9). Not surprisingly, the final performance depends cru­ cially on the provided input information. We observed that the performance of the system with features that are also considered by the EDD-rule has the same final performance as the EDD-rule (column 1). This means, that the learning system was able to extract this rule automatically out of the experience it made. Analogously, the same was true for the MS­ rule (column 2). When we gave the combina­ tion of both features to the learning system, it was able to find a new policy, that is better than both EDD and MS (column 3). Actually, this is the effect we are expecting the learning agent to exploit: considering a combination of features that are of different importance in dif­ ferent situations and acquiring a new (probably very complicated) policy based on the input. However, adding more features not always im­ proves the performance here (column 4).

Figure 1 gives an impression of the learning pro­ cess. The bold line shows the performance on the training set. After about 500 production runs, the system has a performance of 5.3 and thus already beats the EDD-policy (5.7). In course of learning, the performance is further improved.

3.4 Generalization ability

Besides the principle learning and optimization capabilities, one major effect we expect to ob­ serve is the generalization ability of the learning system. To test it, the trained neural agent is applied to situations not included in the train­ ing set. The results are shown in table 3.

Again, the neural agent shows the best perfor­ mance 5.2 and beats the best heuristic rule con­ siderably, which is the SPT-rule here with 6.5. This shows, that the learning agent is not only able to optimize its performance on a certain set of training cases, but also is able to gen­ eralize this knowledge to new, previously un­ known cases without retraining. It may also be derived, that the selected features fulfill the re­ quirement of problem independency.

3.5 The multi-resource case

In the multi-resource benchmark we consider a plant consisting of 3 resources. Here we exam­ ine the ability of one learning agent to adapt to the behaviour of a complex process. This behaviour is determined by the job profile and the structure of the plant, but in contrast to the previous scenario, also dispatching policies for the other resources play an important role. While we are examining the case of one learn­ ing agent and the other policies being fixed, in future experiments we will examine situations of multiple agents learning simultaneously.

In the training scenario, for example, when two fixed agents are acting according to the FIFO (First-in-First-Out) rule, than the performance of the third agent can be improved from 12.2 (the case of also acting according to the FIFO

principle) to 7.5 (when a learning policy is ap­ plied). In order to get an optimal behaviour, the learning agent has to consider the future processing policy of a candidate job, too. As an additional difficulty, since circles may occur during the lifetime of a job, the current decision now also determines the future development of the candidate set. As can be seen in table 4, the learning agent is capable to deal with the described difficulties. In all training cases (left side) and all test cases (right side) the learn­ ing policy outperformed the fixed policy. The agent has autonomously acquired a local policy based on few relevant decision features, that is able to perform well in a complex environment with complex dynamics.

4 Conclusions

The paper describes a neural network based lo­ cal learning approach to job shop scheduling problems. It is based on local learning agents, associated to a resource. The agent has a re­ stricted view on the complete factory's state, representing the most important features that are needed for the local decision. The learning rule relates a local value function with costs depending on the overall performance of the global plant. Doing so, the acquired local de­ cision policy is coordinated with the global op­ timization goal. The experiments on a one­ resource and a three-resource production plant show the capability to learn local policies to op­ timize global behaviour from experience. Fur­ thermore, the agent's policy can be general­ ized to unknown situations without retrain­ ing. Therefore, the learned policies are more tailored to the actual task than comparable heuristic dispatching rules, but still are general enough to be valid in a wide range of untrained situations. In case of major changes in the or­ ganizational structure the proposed learning ar­ chitecture allows an easy reconfiguration of the reactive scheduling policy.

5 Acknowledgments

A major part of this work was carried out dur­ ing a research visit at the Robotics Institute at Carnegie Mellon University, Pittsburgh, PA. The authors gratefully thank Stephen Smith, Andrew Moore and Jeff Schneider for valuable discussions. Special thanks to Dieter Spath, Hartmut Weule, Juergen Schmidt and Wolfram Menzel for giving us the opportunity and the support for this stay.