A Functional Description of a Job Shop.

A job shop consists of a number of facilities, each of which is capable of performing a particular kind of work. We call such a facility a machinecenter, or just a machine; it may constitute a group of several machines with similar capabilities, or a group of men with particular skills.

The job shop receives randomly requests for manufacturing various products (jobs). Each job calls for processing at a certain number of machines in a particular order. We identify an operation as being a part of the job's manufacturing process that can be done completely on one machine with no interruption. Ordinarily, the jobs have different structure (relation between operations) and different demands for processing time. However, they may be grouped according to some common properties; and in addition, some subparts may be used in certain types of jobs and are either purchased or produced in batches.

---

*) This work is based on part oi: the author's Doctorate dissertation submitted to the Department of Statistics and Operations Research of the University of Pennsylvania, U. S. A.

**) Lektor, civilingeniør, Ph. D., Driftsteknisk Institut, Danmarks tekniske Højskole, Lyngby.

Upon arrival of an order, a decision whether to accept or reject it is made in light of the load and capacity of the shop and some crude estimate of the processing time of the prospective job at various machines. If accepted, a due date will normally be set. The cusomer's requirements arc given mainly in functional terms and are transformed by the engineering department into a set af structural properties, laid down in product specifications (blue prints, specifications for material, tolerances)¹). Then, in order to find out what has to be produced, the inventory is checked, and it is determined furthermore what to procure from outside the company. For the parts to be produced we now determine the process specifications, which involve identification of the operations, their technological ordering, and the estimated processing time at the capable machines. Then, either a shedule is made, whereby the time for dispatching the job is calculated, or the job enters the job shop immediately after a priority has been assigned to the job or individual operation.

---

1) As an example, let the order be for a water pump. The relationship between the flow and the height of the water is to be lifted will be one of the functional properties of the pump. On the other hand, the dimension of the rotor, the number of blades, and the type of bearings are structural properties of the pump.

It ought to be mentioned that only a part - although the most important one - of what is going on in a job shop has been discussed here. Such functions as the procurement of raw material and finished parts, or the hiring and traning of the labor force do in fact Influence the scheduling. But, as will become apparent later, the part we have described will give rise to so many complex problems that further complications will make significant results even more distant. Figure 1 summarizes the steps that a job will go through before the processing can start.

The Structure of Problems.

An insight into the nature of the problems encountered can be derived from the description just presented. Job shop scheduling is not merely a question of performing a large number of independent functions. They are highly interrelated and vary with respect to their scope and to the skills required to carry them out. Therefore, the interrelationship ought to be studied in the context of an organization. With these thoughts in mind, we shall state some of the most important problems and classify them according to their level in the organizational hierarchy.

Let us briefly introduce the notion of an administrative unit (decision center in an organization. The purpose of such a unit is to control either another administrative unit or a productive unit. As is indicated in Figure 2 the administrative unit receives information about the state and output of

the productive unit that it is supposed to control. In addition to this direct feed-back, the unit will receive indirect information about decisions made in other administrative units or outside the company. A part of this information is transformed into directives or decisions for the productive unit. Another part of the received information may result in an internal decision about revision of the decision model or its parameters.

In a large organization we will find many administrative units, some
of which will form a hierarchy of decision centers. For problems to be
solved in a job shop we may conceive of the following hierarchy:

a) Long Term Problems Scope: More than one year.

Content: 1. Research and development of know-how in designing
and processing certain types of products (jobs).

2. The number and type of machines.

3. The number of permanently employed workers and their
skills.

b) Short Term Problems. Scope: Less than one year.

Content: 1. Identification of operations and their technological ordering.

2. What to buy from the outside, what to produce, and in
what quantities (batch size). Production smoothing.

3. Whether to accept a job, and the setting of due dates.

c) Ultra Short Term Problems. Scope: Less than one or two weeks.

Content: 1. Dispatching of jobs.

2. Assigning priorities to jobs and operations.

3. Allocation of the machines and the work force (within
certain limits).

The relation between the three levels of problems has been conceptualized in Figure 3. The decisions are indicated by a loop, because the decision center (a) may like to discuss with center (b) before final decisions are issued. As we come down the hierarchy, the decisions, as well as the feedback from the productive unit, become more frequent and specific. For the administrative unit (c), the feedback may be received several times a day, while the input to the decision center for the long term decisions may be received only once a month or even more seldom. It may be seen from the figure that the time, which elapses from an order is initiated and until a feedback is received, is very short for (c), while the lenght of a cycle for (b) and (a) is considerably longer. Due to this fact the problems at level (a) must be solved to a large extent by means of indirect information.

The problems associated with job shop scheduling as presented above have been defined in much broader terms than the traditional definition of the job shop problem as that of scheduling N products through M machines in the shortest possible time. In practice this traditional scheduling problemmay not be conceived of as the most essential problem because the environment of the job shop has responded to the way in which the schedulingfunction is carried out. For example, by negotiating with customers, the management may get the delivery dates so far in the future that considerablesmoothing of the work is possible. Thus, the shop will be able to meet almost all due dates. Based on his past experience which includes visits to various manufacturing plants, W. F. Pounds²) concludes: "The

---

2) Pounds, W. F.: The Scheduling Environment, p. 7, Chapter 1 of Industrial Scheduling, J. F. Muth and G. L. Thompson (eds.), Englelood Cliffs, N. J.: Prentice- Hall, 1963.

job-shop problem is not recognized by most factory schedulers because for them, in most cases, no scheduling problem exists. That is there is no scheduling problem for them because the organization which surrounds the schedulers reacts to protect them from strongly interdependent sequencingproblems."

Pounds clearly points out that not only should the problem be defined in a larger context, but also it should be addressed to decision-makers who hold higher positions in the organization than do schedulers. The hierarchy of problems discussed above will indicate the appropriate level of the organization to which the problems should be addressed.

As an example, consider the long term problem of planning the manufacturing facilities (problem a.2). The decision to acquire new machinery cannot without loss be reversed within a short period of time. The management will have the option of influencing either the number and types of jobs that arrive at the shop, or the capability of the machines, or both. Whichever option is adopted, the management is faced with the problem of matching the incoming rate and technology of the jobs arriving at the shop with the capability of the machines. The long term problem should be addressed to the top management because it involves the future struciure of the whole shop.

Another example is the short term problem of determining a due date for incoming jobs. This decision is ordinarily made in the sales department, but must be based in part on the present and future load of the shop. Since the company is committed to deliver the job at (or before) the due date, the sales department has great influence on the amount of difficulty that the production department will encounter in its attempt to meet the due date. "The sales department is protecting the scheduling function from a scheduling problem when the department begins to resist requests for fast service."³) Since the sales department primarily is concerned with accepting as many orders as possible, it will ordinarily be in conflict with the production department which will be interested in minimizing the production costs, and hence keeping the number of rush orders down. This problem, therefore, should be addressed to a managerial level which includes both the sales and production departments. The traditional formulation of the scheduling problem tends to over-emphasize the scheduler's problem of meeting the due dates, and not examine how the due dates should be set in the first place.

The scheme discussed above has been phrased in control theoretical

---

3) [>. 8, op. civ. footnote 2.

terms. It has become apparent that in order to find optimal solutions to the problems at all three levels, or at; least to establish appropriate guidelinesfor the decision to be made, it is necessary to obtain an estimate of the transformation function, that for a given set of decisions transform the input of the productive unit into completed jobs. Thus, we need a suitable measure of the performance of the productive unit for each of the three levels in the hierarchy of problems. The derivation of a method for constructingsuch appropriate descriptions and the analysis of their features will be our main concern in this thesis. We shall return to this problem after a brief review of the literature.

A Survey of the Literature.

The literature on job shop scheduling has mainly been occupied with the problem of finding sequences of operations and jobs so as to optimize a specified objective function, usually the total time for completion of the jobs, or the extent to which due dates were met. The approach has been first to solve the ultra short term problem, (c), with a given due date, batch size and given machines; and then hopefully to extend the model successively to encounter the short term and long term problem, (a) and (b).

The problem of making a schedule for a fixed number of jobs and machines was first attacked theoretically by S. M. Johnson (1954), who considered the case of two and three machines. If the jobs had to be processed on all of the machines in the same order, Johnson showed that the optimal sequence for one machine (minimizing the total processing time) was the same for the other machines. Several authors have elaborated on Johnson's model, among others Dudek and Teuton (1964), who developed an algorithm which is based on combinatorial analysis. They assumed that the jobs were processed in the same sequence for all the machines (i. e. no passing of operations were allowed). Their mathematical formulation "deals with minimizing of idle time accumulated on the last machine to process each job."

H. M. Wagner (1959) and later A.. S. Manne (1960) made one of the most significant theoretical contributions to the job shop scheduling when they formulated the sequencing problem as an integer linear programming problem.

In line with the search for feasible schedules of the LP-approach we
have the complete enumeration methods, proposer by B. Giffler and G. L.
Thompson (1960) and by J. Heller and G. Logemann (1962). In the

former study a Gantt chart is used to describe the relationship between the operations of the jobs. By means of combinatorial analysis the number of cases which must be studied can be reduced to a set of "active" scedules,since it is shown that this set contains an optimal solution. A schedule is then selected from the set of active schedules at random (Monte Carlo technique). Based on these results, Brooks and White (1965) developed an algorithm which resembles a branch and bound technique.

Heller and Logemann states the problem in terms of linear graphs. Their algorithm "embodies a recursive method of considering the graphs corresponding to technological ordering into one feasible schedule graph." The feasible schedules were generated at random.

The models mentioned above are all static in the sense that a fixed number of jobs is to be scheduled, and that the objective function does not take into account the jobs that are expected to arrive in the future. Thus, it is difficult to fit the formulation into the continuous situation that we have presented.

A schedule is sought which simultaneously determines the sequence for all the machines. This means that the problem basically is that of examining a vast number of combinations (schedules) and to select the one with the best value of the objective function. The rapid increase in the dimensions of any combinatorial analysis when the number of elements is increased is a great hindrance to effective use of the algorithms proposed.

Another approach is to determine in stages the sequence of jobs to be processed on any of the machines. Then, only the operation to be performed next is found at any given time. The transformation of the scheduling problem into a multistage-decision process requires that we determine criteria for selecting the next operation to be processed. Such criteria are ordinarily given by dispatching rules (priority rules). This suggests a queuing approach, where each machine is considered as a server, and the jobs are customers. Hence, a job shop may be viewed as consisting of a set of individual queues interrelated by the technological ordering of the operations of the jobs.

One of the most important theoretical results along this line was obtainedby R. C. Reinitz (1963). He suggested "that we look upon an order as a member of a population of orders and evaluate the statistical properties of the population as influenced by the parameters of the job shop". In his model the job shop consists of a number of independent queuing systems (one for each machine-center), which are assumed to be in a statistical steady state. Assuming that the distribution of arrivals as well as of the service time are Poisson, Reinitz derives an analytical expression for the

waiting time distribution (in terms of inverse Laplace transforms). Unfortunately,this indirect form prevents us from drawing any significant conclusion about the waiting time distribution except in very trivial examples.Thus, the analytical expression serves merely as a means of computingthe distribution function for particular values of the parameters.

Reinitz's work is significant; in that he carries the analytical queueing
approach to the utmost extent of feasibility. Unfortunately, the results are
very complicated, in spite of the assumption of independence.

In view of the enormous difficulties encountered when an analytical solution is sought, many researchers have resorted to the approach of simulating the behavior of a particular job shop on a computer. A. J. Rowe (1960) examined two types of decision rules: 1) Scheduling rules, which determine the start date of a job considering the value of the job and its expected completion time, and 2) Dispatching rules, which are aimed at reducing the probability that a job will miss its due date. R. W. Conway and W. L. Maxwell (1962) have worked extensively with various decision rules for selecting a new operation to be procesed (see also R. W. Conway (1965 and W. S. Gere (1966)). Simulation provides useful ideas for improving many sequencing and scheduling procedures.

Although the theory of flows in networks (Ford and Fulkerson, 1962) at the present cannot handle a network as complicated as a job shop, it contains interesting aspects which may serve as guidelines for the direction of our search for a new way of looking at a job shop.

Recently, Conway, Maxwell and Miller (1967) published an extensive survey over the literature on scheduling as an attempt to organize the work that has been done in this field. Its bibliography contains over 200 references.

The Basic Idea of the Thesis.

As was concluded in a previous section, the solution of each of the many problems of job shop scheduling calls for an appropriate description of the behavior of the shop. Such a description is to be determined in accordance with the scope of the problem and its place in the hierarchy of problems.

Let us first discuss the question of measurement, which will help us identify the core of the problem and suggest a new approach. When we want to measure the behavior of a system, we seek symbols to represent properties of the system, such that the symbols have the same relevant relationship to each other as do the features of the system which we have

represented. Conceivably, there are many ways in which we can measure the performance of a system; each way defines a degree of precision in measurement. When we increase the precision, we are able to take into account more relations among our variables, and the description becomes more and more specific. At the same time we are losing sight of the generalcharacteristics of the system. The more specific our description becomes,the less general interest can it attract, and the fewer general featurescan be discovered. Thus, when attempting to add new elements to the theory of job shop scheduling, we should more be looking for some general properties, or invariants, of the job shop than search for features of the system which are valid under very specific conditions only. With respect to the previous approaches taken in job shop scheduling it may be said that the emphasis has been on precision, perhaps without realizing that it becomes more difficult to discover invariants of the system, when the precision in measurement is increased. On the other hand, if we have a small degree of precision, the invariants may be so general that they appear to be trivial.

We conclude that we should try to approach the problem of obtaining a measure of the behavior of the job shop from a more aggregate point of view. This suggests, for example, that we seek the probability distribution function of a variable, rather than the values of the variable itself. However, there is a need for measures with various degrees of precision. Due to the hierarchical structure of the problems and their different scopes, the description appropriate for each type of problem will vary with respect to the degree of accuracy. As far as the long term problems are concerned, only very general characteristics of the job shop are required, such as the overall capacity in the long run. On the other hand, the description suitable for the ultra short term problems ought to be so detailed that we can measure any significant difference between various dispatching rules.

Unfortunately, it is not always possible to choose a level of accuracy ad libitum, because the functional relations between the variables are given only at a very detailed level. As far as the job shop is concerned, we shall see for instance that the dispatching rule requires very detailed information. Hence, in order to obtain a description with a smaller degree of precision, it is necessary to develop various means of aggregation.

In summary, we shall try to describe the job shop in as general terms as possible, with the hierarchical structure and scope of the problems in mind, and with an eye to the degree of precision necessary for representing the functional relationship between the variables.

The study falls in three major parts: 1) development of a mathematical representation, 2) derivation of the long term features of a job shop, and 3) construction of a method for obtaining the dynamic properties of a job shop. In the following sections we shall briefly outline the content and method of these parts.

A Mathematical Representation.

In order to obtain a formal language in terms of which the activities of a job shop can be expressed, we have developed a mathematical representation. It relates functionally the state variables at f-f 1 to the state variables at t and the new jobs arrived duing (t,t +1). Thus the representation is Markovian. It is noted that many of the state variables can be expressed as Boolean variables which take on only two values: Yes or No; for example, at any given time a machine is either idle or busy; the operations preceding a given operation have either all been completed or not. Thus, the description relies heavily on Boolean operations, most of which we have defined ourselves, and it focuses on two events. The first event occurs when an operation has been completed, and the second event indicates that a new operation may start its processing, because its preceding operations are finished. The mathematical representation constitutes a new way of looking at a job shop which has proveen useful in the analysis of the long term properties, and in the use of simulation. From a theoretical point of view the description is an interesting application of Boolean algebra as a means of representing a complex system. The need for such new approach was clearly pointed out by the extreme difficulties encountered when an attempt was made to extend queuing theory to the complex system of a job shop, cfr. Reinitz (1963).

As an illustration of the idea of the representation let us discuss how
we can describe 1) the technological ordering, and 2) the event that the
technological requirements for an operation are met4).

For each job because of technological requirements there exists an order in which the operations have to be performed. For example, a hole has to be drilled before the bolt can be mounted; a chassis of a radio must be made before the soldering of the wire can take place. This ordering of operations can be represented by an "immediately precedes"-relation. The interpretation of the statement that operation i immediately precedes operationjii^j) is that operation i must be completed before operation j can

---

4) For a more detailed description see, J. O. Riis: "A Mathematical Representation of a Job Shop", submitted to the Journal of Operations Research Society of America.

be started. Further, any given operation can be started, if and only if all
its immediate predecessors have been completed.

Let there be N operations in the job shop. Then, in view of the "immediately precedes" relation introduced above, the technological ordering of the operations can be represented by an (NXN) incidence matrix, A, defined as follows

11, if the ith operation
immediately precedes
the fn operation,
0 otherwise.

The jlhj1h column of A will contain all operations that must be completed
before the jth operation can start. These are indicated by ones.

Let us introduce an incidence vector to denote the extent to which the
operations have been completed. Let Z(t) be (iVXI), such that

fO, if processing of the 2th operation
z;(t) == < has been completed at time t,
[1 otherwise.

If all Zi(t) are equal to one, then no operation has ben completed yet.

We shall introduce another vector, X(t), which will indicate whether
all the preceding operations have been completed, i. e., whether the technological
ordering is satisfied. Let X(t) be (ATXI), such that

iO, if and only if the j_th operation can start at time t (with respect to the technological ordering), 1 otherwise.

Xi(t) is a function of some of the Zj(t), namely for the j's corresponding to operations preceding the I^th operation. In order to express the relationship between X(t) and Z(t) we shall define the product of an incidence matrix and an incidence vector, Pnxn © Qnxi = Rnxi, as follows

where © is the Boolean product of two Boolean variables (equal to the
arithmetical product)

© is the Boolean sum for two Boolean variables

Having defined this particular operation 0 for matrices, and denoting
the transpose of A by A', X(t) can be related to Z(t) in the following way

(1)

Hence, if the degree of completion for all the operations (i.e., Z(t)) is
known, we can obtain an expression for the extent to which the technological
requirements are met, i.e., X(t).

To prove (1), consider

If the ;^th operation is immediately preceded by operation i, then an — 1; and if further the i_th operation has been completed, we have zi(t) =0. Hence, an 0 zi{t) =0. Since this holds for all i<tj, and since an 0 zi(t) = 0, if an = 0, regardless of Zi(t), we have established a proof of necessity.

The Boolean expression of Xj(t) is a sum of N terms. So, Xj(l) is zero, if and only if all the terms are equal to zero. For n<\<j (n not immediately preceding j) a_nj =0, and a_nj 0 z_n(J) ==- 0, regardless of Zn(t). For i<€j, an = 1 and anQx(t) = 0, if and only if zi(t) = 0. We conclude that whenever Xj(t) — 0, the operations that immediately precede j have all been completed. This concludes the proof of sufficiency.

Above we have developed an expression for the operation that may be started as far as the technological ordering is concerned. However, the machines may not be able to cope with these operations at time f. Hence, the next step is to find an idle machine that is capable of processing a particular operation for which the technological requirements are met (i. e., Xi{t) = 0). A matrix is introduced to represent the capabilities of the machines with respect to processing a particular operation. Ordinarily, the machine which can perform the processing trie fastest is selected. As far as choosing an operation to be processed next on a machine, several decision rules may be employed. To select the operation with 1) the smallest processing time, 2) the highest value, 3) the earliest arrival time are just a few of the many decision rules, all of which may be represented by a priority matrix.

The state of the machines are indicated by an incidence matrix for the operations currently being processed, and by a vector denoting the number of time units before the processing is completed. By means of a series of transformations (matrix operations) we produce a list of operations that have been selected to start their processing at time f, and for which processing time is available on the machines.

With I his result and knowledge of the new jobs just arrived we are able to update the state of the machines and the operations. This means that we can obtain an expression of the state of the job shop at time f+l, when we know the state at time t, and the new jobs arrived during (t, tr 1). The representation has thus been made Markovian, because ihe state of the system only depends upon the input during the past time unit and the state of the system one time unit earlier. By advancing the time we can describe the proceedings of a job shop.

The Analysis of Stability.

The management of a job shop must inevitably be concerned with the problem of whether the present value of the input will eventually lead to an infinitely large queue size. Thus, it is important to determine the criteria for stability of a job shop.

The mathematical representation is used to study the behavior of the system over a long period of time. New variables are introduced expressing the work load at each machine, and the time-averages of these variables arc derived. The analysis results in a theorem stating the conditions for stationarity. In addition, it is shown that the incoming demand for processing which yields a stationary system is independent of the technological ordering of the operations. Besides revealing some interesting time-average properties, the analysis provides a useful framework for studying the problem of stability from a more general point of view.

By means of the time-average analysis we can examine the effect of a particular sequence of arriving jobs. This description may be generalized by characterizing the new jobs in a probalistic sense. Hence, the incoming demand for processing at the various machines is defined as a stochastic process, and the concept of boundedness must then be defined in probabilistic terms. A job shop is said to be stable if the distribution function for the work waiting for processing tends to an honest distribution⁵). It was possible to prove the following theorem

Theorem I: A job shop is stable, if the incoming demand forms a metrically transitive and strictly stationary sequence of random variables, and if the expected demand for processing is less than one.

---

5) A random variable and its distribution function arc said to be honest if the random variable is almost everywhere finite. Let F(a) be the distribution function for a random variable. Then, F(a) is honest if F(a) ->• 1, as a-> 00. See for example R. M. Loyncs: The Stability of a Queue with Non-independent Inter-Arrival and Service Times, Camb. Philos. 58,3, 1962.

In his classic paper Lindley (1952) proved that a single server system was stable, if the input formed a sequence of independent and identically distributed random variables, and if the expected input, EUj, is less than one. This result was extended by Loynes (1962) to the more general case where the input constitutes a strictly stationary sequence of random variables. Loynes also studied a sequence of queuing systems, proving that the total system was stable if EUj < 1 for all ;'.

In accordance with the results from the time average analysis Theorem 1 implies that the criteria for stability are independent of the technological ordering of the operations. Hence, we do not have to know the technology of the incoming jobs. The theorem thus extends Loynes' results according to which two jobs had to be processed on the same machines in the same order.

Furthermore, Theorem 1 marks a generalization as far as the priority rule is concerned. Both Lindley and Loynes used the waiting time as their state variables. In order to obtain simple expressions they both assumed that the "first come, first served" priority rule was used. We took a different approach. By virtue of the fact that the busy period is independent of the priority rule, the state variable was defined to be the total amount of work waiting in the queue, because this quantity could be bounded by the busy period. Our result is thus completely general with respect to the priority rule.⁶).

In practice, the production facilities are very often extended at the time where the waiting times have become extremely large. Such ad hoc decisions will ordinarily not be optimal, because they are only based on the current state of the job shop. The theorem on stability has provided a means of determining a long term program for expansion (or reduction) of the production facilities, if the expected incoming demand for processing is known and assumed stationary. Hence, one of the interesting and important implications of the theorem is the possibility of introducing long term planning of the manufacturing facilities in order that the incoming rate and technology of the jobs arriving at the shop can match the capability of the machines.

The Study of the Dynamic Behavior.

In the preceding section the focus was on the asymptotic behavior of
a job shop as time tended to infinity. The. analysis of that problem resulted
in general theorems about the long term properties. However, this approach

---

6) For a complete description of the proof, see J. O. Riis: "Stability of a Job Shop", submitted to the Journal of Applied Probability.

did nol: disclose any of the dynamic features. This has pointed out the
need lor a new approach to the problem of obtaining measures a job shop's
short term behavior.

A detailed description stating the degree of completion and the location ol each job in the shop will contain more specific information than is of general interest. In order to make the results more general, a probabilistic representation has been sought. Thus the problem has been to derive probability distributions (or means and variances) for variables which describe the most important features of a job shop. However, the functional relationship between the variables as well as the decision rules require minute details about the state of the system. In view of the lack of conformity between the aggregate level of description sought and the detailed level necessary for a complete representation, we have developed a method for generating a sequence of distribution functions for the most important variables. The method makes use of the mathematical representation discussed in a previous section.

The basic idea of the method is, by means of the Boolean algebra, to transform each point in the sample space of jobs at time f into a point of the corresponding sample space at t +1. If we at time f know the probability density function for all the points in the sample space of jobs, we can obtain a probability distribution for the jobs at time t-\-\. When the distribution function for the incoming jobs is given, we can add the new jobs to each of the old points. No assumptions need to be made about the distribution function for the initial state or of the new jobs.

The idea behind the method appears to be a very direct way of generating a probability distribution, in spite of the complex expression of the transformation which yields the state of the shop at f-f1 for a given state at t. In fact, the most interesting feature of the method is that we need not make any assumption about the form of this transformation. The method proposed in this thesis may be considered as an attempt to avoid the restrictive assumptions of a conventional analytical approach, and to utilize Jhe information about the probabilistic structure ol the input as well as the initial state in a better way than does a simulation approach. The method accomplishes this by asigning weights to each string of realizations.

Let us illustrate the basic idea of the method in a more formal way. Suppose x(t) describes the state of a system at time t; and that y(t) is a stochastic variable defined on the sample space &, i.e., y(t) = y{«),t) i»iO. Assume now that #(t-fl) is functionally related to x(t) and y(co,t) in a deterministic way, such that for each pair of values [x(t), y(oj,t)} =

[x;, yi\ there exists a unique value of x(t +1) =- xi. Similarly, let z(t+l)
be a variable which is functionally related to x(t) and y (ft), f)7).

Then,

If u(oj;t;x) is the conditional probability density function for the sample space & at time t and for a given value of x(t), then we can find the conditional distribution functions for x(t+\) and z(t+\), assuming (o is discrete.

For a given x(t) — xi let all the points coi, for which the pair [xi, y(o)ij)]
results in the same x(t+\) = xi, be denoted by i 3 f, i. e.,

Then,

Similarly,

From the density functions given above we can derive the distribution
functions.

In the case where the initial condition is given as a probability distribution
we can find P[x(t-\-l) = xi\ by summing over all x{t) and weight
the conditional probability P[x(t +1) =xi x(t)] by P[x(t) — x].

As may be seen in Figure 4, the function f( ) and g( ) are employed to evaluate x(t-\-l) and z{t\-\) for each pair [x(t), y(t)]. The probability density functions for x(t-\~\) and z(t-\-\) are obtained by first summing over Q and then over X(t), and each time weighting the events by the appropriate probability..

The idea presented above has been applied to the job shop where f( ) and g( ) take on such a complicated form that it appears to be impossible to find the distribution functions in the usual manner (e.g., assume a certain distribution function for y(t) and x(t), and then use the moment generating function to derive an expression of the distribution function for x(t+l) and z{t+\)). The mathematical representation provides a suitable expression for the functions f( ) and g( ).

---

7) x(t), y(co,t) and z(t) may be vectors.

8) The functional relationship may even be a function of time, such that x(t-\-\) f[x(t);y(ai,t);t].

Associated with the number of jobs of each type, each of which constitutes a point in the sample space of jobs, is information about the state of the operations, Z, and about the state of the machines, S and M. Hence, a new point having a particular number of jobs of each type at t-\-\, may have been formed by old points with different values of Z, S and M. For each new point we may thus have several sets {Z, S, M}. The method could be repeated for each of these sets, but the number of points and sets will increase exponentially with the number of time periods. By proposing a way of aggregating the different sets {Z, S, M} associated with each new point into one set, and by deleting the points with a very small probability, the method has been made recursive, and the number of points in the sample space of jobs remains almost the same. Other means of aggregation has been outlined; for example, it could be assumed that all jobs belonging to one type had the same technological ordering.

A small example with 5 machines and 3 types of jobs has been calculatedon a computer (IBM 360 f65). Some of the main features of the job shop were obtained for various input distribution, and we studied the effect of changing the number of points in the sample space which characterizesthe state of the shop. In addition, a special simulation program

---

9) Z = Szj\ indicates the degree of completion, S = (sjj\ denotes the operations cuncntly being processed, and M = {™j} gives for each machine the time until the processing will be completed. Thus, Z indicates the state of the operation, while S and M indicate the state of the machines.

was developed for testing the method. In view of the conplcxity of the problem of obtaining measures of the dynamic behavior of a job shop, we conclude that the method proposed above is based on a interesting idea which deserves a thorough investigation. Unfortunately, the dimensionsof the problem have not been reduced to an extent where the method can be used in practice on a large scale basis.

A Generalization.

In this paper the job shop has been the main object for our investigation. But the problem as well as the results are related to the more general problem of representing a complex system at appropriate levels of aggregation. The methodology applied thus seems to be suitable for the analysis of a system in general. Accordingly, the following three steps should be carried out: 1) development of a mathematical representation, 2) analysis of the system's long term properties, especially with respect to the concept of stability, and 3) analysis of the system's short term properties.

References.

Brooks, G. 11., and C. R. White: An Algorithm for Finding Optimal or Near-Optimal
Solutions to the Production Scheduling Problem, f. Ind. Eng., January 16, 1963.

Conway, R. W.: Priority Dispatching and Work-in-Process Inventory in a Job Shop
f. Ind. Eng., February 16, 1965.

Conway, R. W.: Priority Dispatching and Job Lateness in a Job Shop, f. Ind. Eng
April 16, 1965.

Conway, R. W., and W. L. Maxwell: Network Dipatching by the Shortest-Operation
Discipline, Operations Research, January 10, 1962.

Conway, R. W., W. L. Maxwell, and L. W. Miller: Theory of Scheduling, Reading,
Mass.: Addison-Wesley, 1967.

Dudek, R. A., and O. F. Teuton, Jr.: Development of M-Stage Decision Rule for Scheduling
n Jobs Through m Machines, Operations Research, March 12, 1964.

Ford, L. R., Jr., and D. R. Fulkerson: Flows in Networks, Princeton, N. J.: Princeton
University Press, 1962.

Gere, W. S., Jr.: Heuristics in Job Shop Scheduling, Management Science, 13, p. 167,
1966.

Giffler, 8., and G. 1,. Thompson: Algorithms [or Solving Production Scheduling Problems,
Operations Research, April 8, 1962.

Heller, J., and G. Logemann: An Algorithm for the Construction and Evaluation of
Feasible Schedules, Management Science, March 8. 1962.

Johnson, S. M.: Optimal Two- and Three-Stage Production Schedules with Setup Times
Included, Nav. Res. Log. Quart., January 1, 1954.

Lindley. D. V.: The Theory of Queues with a Single Server, Proc. Camb. Phil. Soc, 48
277-289, 1952.

Loynes, R. M.: The Stability of a Queue with Non-independent Inter-Arrival and Serv
ice Times, Proc. Camb. Phil. Soc, 58, 497-520, 1962.

Manne, A. S.: On the Job-Shop Scheduling Problem, Operations Research, February 2
1960.

Pounds, W. F.: The Scheduling Environment, Chapter 1 of Industrial Scheduling,. J. F
Muth and G. L. Thompson (eds.), Englewood Cliffs, N. J.: Prentice-Hall, 1863

Reinitz, R. C: On the Job Shop Scheduling Problem, Chapter 5 of Industrial Schedul
ing, J. F. Muth and G. L. Thompson (eds.), Englewood Cliffs, N. J.: Prentice
Hall, 1963.

Rowe, A. J.: Toward a Theory of Scheduling, f. Ind. Eng., February 2, 1960.

Wagner, H. M.: An Integer Linear-Programming Model for Machine Scheduling
Nav. Res. Log. Quart., February 6, 1959.