9512.net

甜梦文库

甜梦文库

当前位置：首页 >> >> # Directeur de thèse

INSTITUT NATIONAL POLYTECHNIQUE DE GRENOBLE

` THESE pour obtenir le grade de DOCTEUR DE L’INPG Sp?cialit? : AUTOMATIQUE, PRODUCTIQUE e e

pr?par?e au laboratoire e e

VERIMAG

dans le cadre de L’Ecole Doctorale ELECTRONIQUE, ELECTROTECHNIQUE, AUTOMATIQUE, TELECOMMUNICATION, SIGNAL pr?sent?e et soutenue publiquement e e par

Yasmina Abdedda¨ ?m

le 28 Novembre 2002

Titre

Mod?lisation et R?solution de Probl`mes d’Ordonnancement ` e e e a l’aide d’Automates Temporis?s e

Directeur de th`se e

Oded Maler

JURY M. M. M. M. M. M. Jean Della Dora, Ed Brinksma, Kim Larsen, Oded Maler, Claude Le Pape, Stavros Tripakis, President Rapporteur Rapporteur Directeur de th`se e Examinateur Examinateur

Remerciements

Je remercie Mr Oded Maler, mon directeur de th`se, il a ?t? un encadreur exceptionnel, e ee tant par l’originalit? de ses id?es que par sont engagement dans mon travail, il a ?t? pour moi e e ee l’encadreur id?al. e Je remercie Mr Jean Della Dora, Mr Ed Brinksma, Mr Kim Larsen, Mr Claude Le pape et Mr Stavros Tripakis d’avoir particip? ` mon jury de th`se. ea e Je remercie Mr Joseph Sifakis directeur du laboratoire VERIMAG pour avoir su diriger un laboratoire o` r`gnent toutes les bonnes conditions de travail et o` on retrouve un grand m?lange u e u e culturel tr`s enrichissant. e Je remercie Mr Eugene Asarin pour tout le temps qu’il m’a consacr? durant nos longues e discussions, pour sa grande p?dagogie et sa modestie. e Je remercie Marius Bozga connu ` VERIMAG pour ?tre toujours disponible a donner un a e ` coup de main et des explications tr`s claires. e Je remercie Stavros Tripakis pour ses discutions scienti?ques et g?n?rales toujours pleines de e e convictions. Un grand merci aux chercheurs et enseignants de VERIMAG et plus sp?cialement Sergio e Yovine, Paul Caspi et Saddek Bensalem. Merci ` Thao Dang ma soeur de VERIMAG, Gordon Pace pour toutes les journ?es pass?es a e e ensemble, Christos Kloukinas et ses silences expressifs, Moez Mahfoudh et ses histoires abracadabrantes, Radu Iosif qui s’est tr`s vite int?gr?, Catalin Dima qui a support? mes taquineries. e e e e Merci ` mes amis et ` mes rencontres de Grenoble, je ne peux tous les citer, qui m’ont fait a a r???chir sur d’autres sujets que mon sujet de th`se. e e e Merci ` mes amis d’Alger qui ont su me rester ?d`les. a e Je tiens ` remercier ma famille, mes parents qui m’ont donn? un grand coup de pouce, mon a e fr`re Said qui a ?t? pour moi d’un grand secours durant toutes les ?tapes de ma th`se et qui a e ee e e su me conseiller avec son grand calme communicatif, ma soeur Amina et son grand sourire, je te promets que je vais ?nir par trouver du temps pour venir te voir. Merci Zahir.

Contents

1 Introduction 1.1 Contribution of the Thesis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 9 9

I

Background

Shop Scheduling The problem . . . . . . . . . . . . . . . Disjunctive Graph Representation . . . Constrained Optimization Formulations Enumerative Methods . . . . . . . . . . Approximation methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

13

15 15 16 17 18 19 21 21 27 31 31 34 38

2 Job 2.1 2.2 2.3 2.4 2.5

3 Discrete Veri?cation and Graph Algorithms 3.1 Reachability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2 Shortest Paths . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 Adding Time to Automata 4.1 Explicit Modeling of Time . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2 Clock Variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.3 Basics of Timed Automata . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

II

Contribution

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

45

47 47 49 49 50 53 55 57 58 59 61 64 64 65

5 Deterministic Job Shop Scheduling 5.1 Formal de?nitions . . . . . . . . . . . . . . . . . . 5.2 Modeling with Timed Automata . . . . . . . . . . 5.2.1 Modeling Jobs . . . . . . . . . . . . . . . . 5.2.2 Modeling Job Shop Speci?cations . . . . . . 5.3 Runs and Schedules . . . . . . . . . . . . . . . . . 5.4 Shortest Path using Timed Automata Reachability 5.5 Laziness and Non-Laziness . . . . . . . . . . . . . . 5.5.1 Lazy Schedule . . . . . . . . . . . . . . . . 5.5.2 Immediate and Lazy Runs . . . . . . . . . . 5.6 The Search Algorithm . . . . . . . . . . . . . . . . 5.7 Reducing the Search Space . . . . . . . . . . . . . 5.7.1 Domination Test . . . . . . . . . . . . . . . 5.7.2 Best-?rst Search . . . . . . . . . . . . . . . 5

CONTENTS

5.8

5.7.3 Sub-Optimal Solutions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Experimental Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

65 65 67 68 69 71 72 73 76 78 81 81 83 88 88

6 Preemptive Job Shop Scheduling 6.1 Modeling with Stopwatch Automata 6.1.1 Modeling Jobs . . . . . . . . 6.1.2 The Global Model . . . . . . 6.1.3 Runs and Schedules . . . . . 6.2 E?cient Schedules . . . . . . . . . . 6.3 Searching for E?cient Runs . . . . . 6.4 Experimental Results . . . . . . . . . 7 Task Graph Scheduling 7.1 The Problem . . . . . . . . . . . . . 7.2 Modeling with Timed Automata . . 7.3 Adding Deadlines and Release Times 7.4 Experimental Results . . . . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

8 Scheduling Under Uncertainty 8.1 The Problem . . . . . . . . . . . . . . . 8.2 The Hole-Filling Strategy . . . . . . . . 8.3 Adaptive Scheduling . . . . . . . . . . . 8.4 Modeling with Timed Automata . . . . 8.5 Optimal Strategies for Timed Automata 8.5.1 Implementation . . . . . . . . . . 8.6 Experimental Results . . . . . . . . . . . 9 Conclusions

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

. . . . . . .

91 . 91 . 93 . 94 . 96 . 99 . 100 . 100 105

6

Chapter 1

Introduction

1.1 Contribution of the Thesis

This thesis develops a new methodology for posing and solving scheduling problems. The essence of this approach is to model the system as a timed automaton where schedules correspond to paths in the automaton and optimal schedules correspond to shortest paths. The methods that we propose are inspired by several existing bodies of knowledge. The ?rst is algorithmic veri?cation methodology whose goal is to prove some properties concerning all runs of a discrete transition system (automaton). Veri?cation algorithms are based, this way or another, on graph algorithms that explore paths in the transition graph. On slightly richer models, where numerical weights are assigned to arcs or to nodes of the graph, one can formulate and solve shortest-path algorithms, that is, ?nd the minimal cost path between two given nodes. Our goal is to use such algorithms to ?nd optimal schedules, but in order to do so we need to ?nd a way to extend shortest path algorithms to problems where the cost associated with a path is the time elapsed from beginning to end. In the ?rst part of the document, we start by a short survey of the job-shop problem (Chapter 2) and the techniques traditionally used for its solution. In the Chapter 3 we give a survey of the basic algorithms for exploring directed graphs. In Chapter 4 we review a naive approach for expressing passage of time using weighted automata, then we move on to timed automata. The second part concerns our approach. We ?rst model the classical job-shop problem (Chapter 5), and then extend the model to treat preemption (Chapter 6), partially-ordered tasks (Chapter 7) and scheduling problems with temporal uncertainty (Chapter 8). For all these problems we develop algorithms, implement them and test their performance on benchmark examples. The thesis is a contribution both to the theory and practice of scheduling and to the analysis of timed automata.

1.2

Related Work

This work can be viewed in the context of extending veri?cation methodology in two orthogonal directions: from veri?cation to synthesis and from qualitative to quantitative evaluation of behaviors. In veri?cation we check the existence of certain paths in a given automaton, while in synthesis we have an automaton in which not all design choices have been made and we can 9

1.2. RELATED WORK

remove transitions (and hence make the necessary choices) so that a property is satis?ed. If we add a quantitative dimension (in this case, the duration of the path), veri?cation is transformed to the evaluation of the worst performance measure over all paths, and synthesis into the restriction of the automaton to one or more optimal paths. The idea of applying synthesis to timed automata was ?rst explored in [WH92]. An algorithm for safety controller synthesis for timed automata, based on operation on zones was ?rst reported in [MPS95] and later in [AMP95], where an example of a simple scheduler was given, and in [AMPS98]. This algorithm is a generalization of the veri?cation algorithm for timed automata [HNSY94, ACD93] used in Kronos [Y97, BDM+ 98]. In these and other works on treating scheduling problems as synthesis problems for timed automata, such as [AGP99], the emphasis was on yes/no properties, such as the existence of a feasible schedule, in the presence of an uncontrolled adversary. A transition toward quantitative evaluation criteria was made already in [CY91] where timed automata were used to compute bounds on delays in real-time systems and in [CCM+ 94] where variants of shortest-path problems were solved on a timed model much weaker than timed automata. To our knowledge, the ?rst quantitative synthesis work on timed automata was [AM99] in which the following problem has been solved: “given a timed automaton with both controlled and uncontrolled transitions, restrict the automaton in a way that from each con?guration the worst-case time to reach a target state is minimal”. If there is no adversary, this problem corresponds to ?nding the shortest path. Due to the presence of an adversary, the solution in [AM99] employs backward-computation (dynamic programming), i.e. an iterative computation of a function h : Q × H → R+ such that h(q, v) indicates the minimal time for reaching the target state from(q, v). The implementation of the forward algorithm developed in this thesis can be viewed as iterating with a function h such that h(q, v) indicates the minimal time to reach (q, v) from the initial state. The reachable states in the augmented clock-space are nothing but a relational representation of h. Around the same time, in the framework of the VHS (Veri?cation of Hybrid systems) project, a simpli?ed model of a steel plant was presented as a case-study [BS99]. The model had more features than the job-shop scheduling problem such as upper-bounds on the time between steps, transportation problems, etc. A. Fehnker proposed a timed automaton model of this plant from which feasible schedules could be extracted [F99]. Another work in this direction was concerned with another VHS case-study, a cyclic experimental batch plant at Dortmund for which an optimal dynamic scheduler was derived in [NY00]. The idea of using heuristic search is useful not only for shortest-path problems but for veri?cation of timed automata (and veri?cation in general) where some evaluation function can guide the search toward the target goal. These possibilities were investigated recently in [BFH+ 01a] on several classes of examples, including job-shop scheduling problems, where various search procedures and heuristics were explored and compared. In [NTY00] it was shown that in order to ?nd shortest paths in a timed automaton, it is su?cient to look at acyclic sequences of symbolic states (a fact that we do not need due to the acyclicity of job-shop automata) and an algorithm based on forward reachability was introduced. A recent generalization of the shortest path problem was investigated by [BFH+ 01b] and [ATP01], in a model where there is a di?erent price for staying in any state and the total cost associated with the run progresses in di?erent slopes along the path. It has been proved that the problem of ?nding the path with the minimal cost is solvable.

10

Part I

Background

13

Chapter 2

Job Shop Scheduling

The job shop problem is one of the most popular problems in scheduling theory. On one hand it is very simple and intuitive while on the other hand it is a good representive of the general domain as it exhibits the di?culty of combinatorial optimization. The di?culty is both theoretical (even very constrained versions of the problem are NP-hard) and practical (an instance of the problem with 10 jobs and 10 machines, proposed by Fisher and Thompson [F73a], remained unsolved for almost 25 years, in spite of the research e?ort spent on it). In the rest of the section we give an informal presentation of the problem and mention some of the methods suggested in the past for its solution.

2.1

The problem

A job shop problem consists of a ?nite set J = {J 1 , . . . , J n } of jobs to be processed on a ?nite set M = {m1 , . . . , mm } of machines. Each job J i is a ?nite sequence of steps to be executed one after the other, where each step is a pair of the form (m, d), m ∈ M and d ∈ N, indicating the required utilization of machine m for time duration d. Each machine can process at most one step at a time, and, due to precedence constraints, at most one step of each job may be processed at any time. Steps cannot be preempted once started. The objective is to determine the starting times for each step in order to minimize the total execution time of all jobs, i.e the time the last step terminates. This problem is denoted in the scheduling community as J||Cmax where Cmax is the maximum completion time, called makespan. Example 1.1 Consider M = {m1 , m2 , m3 } and three jobs J 1 , J 2 , J 3 to be scheduled on these machines. The job J 1 consists of 3 steps, the ?rst lasts 3 time units and must be carried out on the machine m1 , the second lasts 6 time units on machine m3 and so on. J 1 : (m1 , 3), (m3 , 6), (m2 , 5) J 2 : (m1 , 2), (m1 , 4), (m3 , 7) J 3 : (m3 , 1), (m2 , 5), (m1 , 6) Two schedules S1 and S2 are depicted in Figure 2.1 The length of S1 is 17 while the length of S2 is 16, and it is the optimal schedule. The two schedules are represented using Gantt diagram, showing the evolution of each job on the machines.

15

2.2. DISJUNCTIVE GRAPH REPRESENTATION

M1 S1 M2

J2

J1 J3

J3 J2 J1 J1 J2

10 11 12 16 17

M3 J3

2 5 6

M1 S2 M2 M3 J3

J1 J3

J2

J3 J2 J1 J1 J2

9 10 12 15 16

2

3

5 6

Figure 2.1: Two schedules S1 and S2 represented in a Gantt diagram

2.2

Disjunctive Graph Representation

In the lack of resource con?icts (when every job uses a distinct set of machines) the optimal schedule is achieved by letting every job execute its steps as soon as possible, that is, to start immediately with the ?rst step and move to the next step as soon the previous step terminates. In this case the minimal makespan is the maximal (over all jobs) sum of step durations. The di?cult (and interesting) part of the problem comes with con?icts: a job might want to start a step but the corresponding machine is occupied by another job. Here the optimal schedule need not be based on the greedy principle “start every step as soon as it is enabled” because it might be globally better to wait and leave the machine free for a later step of another job. It is this type of decisions that distinguishes one schedule from another as can be seen in an intuitive manner using the disjunctive graph model, introduced by Roy and Sussman [RS64]. A disjunctive graph associated with a job-shop problem is a graph G = (V, W, A, E) where V is a set of nodes corresponding to the steps of the problem with two additional (?ctitious) nodes “start” and “end”. The positive weight W (v) associated with each node v is equivalent to the duration the corresponding step. The precedence constraints between the steps of the same job are represented by a set A of directed edges such that (v, v ) ∈ A indicates that step v is an immediate predecessor of step v . The resource con?icts are represented by a set E of undirected edges, such that whenever step v and step v use the same machine, both (v, v ) ∈ E and (v , v) ∈ E. Clearly, E is an equivalence relation and let us denote by Em the subset of E corresponding to machine m. An orientation of E is a subset E ? E such that for every machine Em is a linear order. Every orientation can be seen as de?ning a priority relation between steps requiring the same machine. Two examples of orientation of the graph appears in Figure 2.2 where job J 2 has priority over job J 1 on machine m1 in the orientation corresponding to the schedule S1 and the opposite on the orientation of the schedule S2 . 16

2.3. CONSTRAINED OPTIMIZATION FORMULATIONS

V11

3

V12

6

V13

5

S1

0

start

V21

2

V22

4

V23

7

end 0

V31

1

V32

5

V33

6

V11

3

V12

6

V13

5

S2

0

start 2

V21

V22

4

V23

7

end 0

V31

1

V32

5

V33

6

Figure 2.2: The two orientations corresponding to the schedules S1 and S2 where Vij is the node corresponding to the step j of the job i.

For every given orientation, the length of the longest path from “start” to “end” is equal to the length of the shortest schedule among all the schedules that satisfy the corresponding priority relation. So ?nding the optimal schedule reduces to ?nding the priority relation whose associated orientation leads to the minimal longest path. There are ?nitely many such priority relations, hence the problem is solvable, however their number is exponential which makes the problem intractable. Note that some partial choices of priorities can make other priorities redundant, for example, if one job uses m at an early step and another job uses machine m toward the end, it might be the case that the priority relation between them need not be stated explicitly.

2.3

Constrained Optimization Formulations

An alternative formulation of the problem is as a constrained linear optimization problem where the combinatorial di?culty is manifested by the non-convexity of the set of feasible solutions. For the purpose of this formulation let us write a job J i as a sequence of steps (mi1 , di1 ), (mi2 , di2 ), . . . , (mim , dim ), let tij denote the start time of step j of job i and let T be the global termination time. The job shop problem can be formulated mathematically in the following form:

17

2.4. ENUMERATIVE METHODS

? ? Minimize T where ?J i tim ≤ T (T is the maximal makespan) ? ? ? subject to : ? ? ? ? ?J i ∈ J ?k ∈ {1 . . . m} tik ≥ 0 ? ? ? ?J i ∈ J tik ? tih ≥ dih if (mih , dih ) precedes (mik , dik ) ? ?J i ∈ J ?J j ∈ J if (mik = mjh ) ? ? ? tjk ? tik ≥ dik (mik , dik ) precedes (mjh , djh ) ? ? ? ? ∨ ? ? ? (mjh , djh ) precedes (mik , dik ) tik ? tjk ≥ djk

As one can see, the question of priority appears now in the form of disjunction. If we transform the constraints into a disjunctive normal form, every disjunct will indeed correspond to a priority relation under which the problem transforms into a trivial linear programming problem. An attempt to avoid the enumeration of priority relation and stay within the framework of linear programming is to transform the problem into mixed integer linear programming (MILP) format of Manne [Ma96]. A MILP problem is a linear program where some of the variables are integers. In the job shop problem the integer variables are binary and are used to model the disjunctive constraints.

? ? Minimize T where ?J i tim ≤ T (T is the maximal makespan) ? ? ? ? subject to : ? ? ? tik ≥ 0 ? ?J i ∈ J ?k ∈ {1 . . . m} ? ? ? yijk ∈ {0, 1} ? ?J i ∈ J ?J j ∈ J ?mk ∈ M ?J i ∈ J tik ? tih ≥ dih if (mih , dih ) precedes (mik , dik ) ? ? ?J i ∈ J ?J j ∈ J if (mik = mjh ) ? ? ? ? tjk ? tik + K(1 ? yijk ) ≥ dik ? ? ? ? tik ? tjk + K(yijk ) ≥ djk ? ? ? K is a big number

Even for the more compact mathematical formulations a large number of constraint are required [Ma96] and the number of integer variables grows exponentially [B59]. Gi?er and Thompson [HLP93] mention that integer programs have not led to practical methods of solutions while French [GT60] expresses the view that an integer programming formulation of scheduling problems is computationally infeasible. The best results that has been obtained using mathematical formulation are due to Lagrangian relaxation (LR) approaches [F73b, Fr82, V91, FT63, KSSW95] and decomposition methods [A67, ?, DR94, M60] The results indicate that solutions are usually of poor quality.

2.4

Enumerative Methods

Since the embedding of the problem in the continuous optimization framework does not seem to work, most approaches are based on enumeration, a search in the space of feasible solutions. In order to avoid an exhaustive search, enumerative methods use clever elimination techniques that reduce the number of solutions that need to be explored. The general framework for such a search is called Branch and Bound (BB) and is best explained using the following example. Suppose our search space consists of all 6 priority relations (permutations) over {1, 2, 3}. We can create the permutations incrementally, for example decide ?rst whether 1 ? 2 or 2 ? 1. The ?rst choice amounts to choosing the subset {123, 132, 312} of the possible permutations, and each permutation corresponds to a leaf in a search tree such as the one in Figure 2.3. A crucial component of BB is the ability to evaluate the quality of a partial choice (non-leaf node) 18

2.5. APPROXIMATION METHODS

by an over-approximation. The general idea is then to choose one or more full branches in the search tree and evaluate them. This gives an upper-bound (if the problem is minimization) on the quality of the solution. Then a search can be conducted on the tree, cutting branches whose estimated evaluation is worse than the upper-bound. {123, 132, 213, 231, 312, 321} 1?2 {123, 132, 321} 1?3 {123, 132} 2?3 {123} 3?2 {132} 3?1 {321} 1?3 {213} 2?3 {231} 2?1 {213, 231, 321} 3?1 {231, 321} 3?2 {321}

Figure 2.3: A search in the space of priority relations

The ?rst applications of BB to the job shop problem was proposed by Balas [B69], followed by many others, including Carlier [C82], Carlier and Pinson [CPP92], Appelgate and Cook [?], Brucker and al. [BJS94], Perregaard and Clausen [PC95], Boyd and Burlingame [BB96] and Martin [Ma96]. Although the computational study indicates that improvements have been achieved by BB methods, this is mainly attributed to improvement in computer technology rather than to the techniques used.

2.5

Approximation methods

Although approximation methods do not guarantee optimal solutions, they can attain near optimal solutions within moderate computing time and are adequate to large problems. Main categories of approximation techniques are: priority dispatch rules, bollelneck based heuristics, Constraint Satisfaction and local search methods. Approximation applied to job shop problem were ?rst developed on the basis of Priority Dispatching Rule (PDR). In this method, at each step all the operations which are available to be scheduled are assigned a priority and the operation with the highest priority is chosen to be sequenced. Usually several runs of PDRs are made in order to achieve valid results. The best results due to this technique are those of Sabuncuoglu and Bayiz [SB97]. However the deviations from the optimum are still high, the results suggest that PDRs are more suitable as an initial solution technique. The Shifting Bottleneck (SB) procedure decomposes the job shop problem into a series of single-machine subproblems. It schedules the machines one by one and focuses on bottleneck machines. One example of such approach is the Shifting Bottleneck Procedure of Adams and all. [ABZ88] A general weakness of the SB approaches is the level of programmer sophistication required. 19

2.5. APPROXIMATION METHODS

Constraint Satisfaction techniques aim at reducing the e?ective size of the search space by applying constraints that restrict the order in which variables are selected and the sequence in which possible values are assigned to each variable. After a value is assigned to a variable any inconsistency arising is removed. These techniques has been applied to solve the job-shop problem in [BPN95, CY94, NA96, PT96, NP98].

20

Chapter 3

Discrete Veri?cation and Graph Algorithms

3.1 Reachability

The domain of veri?cation is concerned with proving that systems, such as computer programs or digital circuits, behave as required and contain no bugs under all conceivable circumstances. Typically each component of such a system is modeled as an automaton, a system with a ?nite set of states and transitions between states that corresponds to events or actions performed by the component. In this framework a job in a job-shop problem can be modeled by an automaton whose states represent the progress of the job along its sequence of steps, and transitions correspond to the initiation and termination of steps. The automaton characterizing a whole system is obtained by composing the automata its components1 and obtaining an automaton whose states are elements of the Cartesian product of the state sets of the components. The set of all possible behaviors of the system is thus represented by the set of all paths in this transition graph, whose size grows exponentially with the number of components. So technically, the problem of veri?cation can be reduced to the problem of checking the existence of certain paths in a directed graph, the transition graph of the automaton. The simplest type of properties to which veri?cation is applied are reachability properties, properties that are veri?ed by a path depending on whether or not it visits some speci?c states. In some cases we want to check that all behaviors avoid a set of “bad” states (for example, a state where the same machine is given to two jobs), and in others we do not want behaviors to get stuck but rather to proceed to some ?nal state (for example, a state where all jobs have terminated). Such properties are examples of safety and liveness properties, respectively. The algorithmic approach to veri?cation, also known as model-checking, uses graph algorithms in order to explore the paths in the automaton and to show that they satisfy these and more complex properties. In the sequel we will survey some of the basic algorithms for exploring directed graphs, starting with those that can solve reachability problems. Later, by assigning numerical weights to the automaton transitions, we associate real numbers (length, cost) with runs and search for runs that are optimal in this sense, using shortest path algorithms. Automata and directed graphs describe essentially the same objects and we will use the terminology and notation of automata theory. De?nition 1 (Finite State Automata) A ?nite state automaton is a pair A = (Q, δ) where Q is a ?nite set of states, and δ ? Q × Q is a transition relation. A ?nite run of the automaton

There are many forms of compositions depending of the mode of interaction between the components and other features that are beyond the scope of this thesis.

1

21

3.1. REACHABILITY

starting from a state q0 is a sequence of states q0 → q1 → . . . → qk such that (qi , qi+1 ) ∈ δ for every i, 0 ≤ i ≤ k ? 1. In graph-theoretic terminology states are vertices, or nodes transitions are edges or arcs and runs are paths. We use Succ(q) and P re(q) to denote the sets of successors and predecessor of a state q: Succ(q) = {q : (q, q ) ∈ δ} and P re(q) = {q : (q , q) ∈ δ}. A useful concept for visualizing all the possible runs of the automaton starting from a state q is the q-unfolding of the automaton, a tree constructed by starting at q, adding nodes and transitions for each of its successors, and repeating the procedure recursively for these nodes. If the automaton contains cycles (paths leading from a state to itself) its unfolding will be in?nite. Otherwise it is ?nite but its size can be exponential in the size of the automaton. An automaton is depicted in Figure 3.1 and an initial part of its unfolding is shown in Figure 3.2.

q4 q2 q1 q3 q6

Figure 3.1: An automaton A = (Q, δ)

q5

q7

22

3.1. REACHABILITY

q1

q3 q7 q3

q2

q6 q2

q7

q4

q6

q6

q7

q6

q7

q3

q7

q4

q2

q2

q6

q2

q6

Figure 3.2: The q1 -unfolding of the automaton of Figure 3.1 We will now demonstrate the various approaches to graph searching in order to solve the following reachability problem: “given an automaton and two states q and q , is there a path leading from q to q ”. Clearly the answer to this question is positive if the unfolding of the automaton starting at q contains a node labeled by q . The simplest algorithm for doing it is the breadth-?rst search (BFS) algorithm described below. The algorithm maintains two datastructures, a set of explored states whose successors have already been encountered and an ordered list of waiting states that need to be explored (these are sometimes called the frontier of the search). The algorithm terminates either by reaching q and answering “yes” or by computing all the states reachable from q without reaching q . Termination of the algorithm is guaranteed by the ?niteness of Q. Algorithm 1 (Reachability-BFS (A, q, q )) Waiting := {q} ; Explored:={}; Reached := no; while ( Reached = no and Waiting = ?) do begin Pick ?rst v ∈ Waiting; if (v ∈ Explored) then / begin for every u such that u ∈ Succ(v) ∧ u ∈ Explored do / if (u = q ) then Reached := yes; else Insert u into the end of Waiting; Insert v into Explored; end Remove v from Waiting; end return(Reached); 23

3.1. REACHABILITY

Note that BFS explores the unfolding of the automaton according to levels, that is, the order in which it explores the nodes of the tree is consistent with their distance from the root, where “distance” here means the number of transitions. If, in addition to the yes/no answer, we want to obtain a path when it exists, we can modify the algorithm by storing with each inserted node the path that has led to it, i.e. inserting v · u into Waiting instead of inserting only u. While the BFS algorithm advances “in parallel” over all paths, the depth-?rst search (DFS) algorithm attempts to reach q along a path and then move to another one. Technically the di?erence between the algorithms is in the place where new nodes are added to the waiting list, at the end (BFS) or at the beginning (DFS). In other words, the list is FIFO (?rst in ?rst out) in BFS and LIFO (last in ?rst out) in DFS. Algorithm 2 (Reachability-DFS (A, q, q )) Waiting:= {q}; Explored:={}; Reached := no; while ( Reached = no and Waiting = ?) do begin Pick ?rst v ∈ Waiting; if (v ∈ Explored) then / begin for every u such that u ∈ Succ(v) ∧ u ∈ Explored do / if (u = q ) then Reached := yes; else Insert u at the beginning of Waiting; Insert v into Explored; end Remove v from Waiting; end return(Reached); Note that both algorithms have an under-speci?ed component, that is, the order in which the successors of the same node are explored. As we will see from the examples, this choice may a?ect the behavior of the algorithms, especially that of DFS in case a path exists. Example: Consider the automaton depicted in Figure 3.1 and the following two reachability problems: ? P1 : Is q5 reachable from q1 ? ? P2 : Is q6 reachable from q1 ? For P1 , the answer is negative and the two search algorithms end up computing all the states reachable from q1 . In Figure 3.3 we see the behavior of the two algorithms under the following exploration ordering of successors: q3 ? q2 for Succ(q1 ) and q3 ? q7 ? q4 for Succ(q2 ). The dashed nodes indicate the places where the search stopped, that is, nodes whose successors have not been explored because they have been explored along other paths.

24

3.1. REACHABILITY

q1

q1

q3

q2

q3 q3

q2

q6

q7

q3

q7

q4

q7

q4

q2

q6

q7

q6

q7

q7 q6

q2

Breadth-first search Depth-first search

Figure 3.3: The explored search BFS and DFS trees for problem P1 .

The search trees for P2 under the same successor ordering can be see in Figure 3.4. BFS always ?nds the shortest (in terms of transitions) path while DFS, under this ordering ?nds a longer run q1 → q2 → q4 → q7 → q6 . The sensitivity of DFS to the ordering of successors is demonstrated in Figure 3.5 where we show the behavior of the algorithm when the successors of q1 are ordered according to q2 ? q3 . BFS ?nds the same shortest path as before (with some less exploration) and DFS now ?nds this path as well.

25

3.1. REACHABILITY

q1

q1

q3

q2

q3 q3

q2

q6

q7

q7

q4

q7 q6

Breadth-first search Depth-first search

Figure 3.4: The search trees for P2 with q3 ? q2 .

q1

q1

q2

q3

q2 q7 q6

q3

q3

q7

q4

q6

q7

Breadth-first search

Depth-first search

Figure 3.5: The search trees for P2 with q2 ? q3 . In certain application domains there might be some useful evaluation function on states that can be used for a more sophisticated search procedure. For example, if the state-space of the automaton consists of Boolean n-tuples, and the dynamics is de?ned in a certain way, the Hamming distance between a state and q will give an indication how close we are to our goal. An algorithm that keeps the waiting list ordered according to such a measure is called a best-?rst search algorithm and will be later used extensively for the job-shop problem. The algorithms described so far explore the automaton in a forward direction, starting from q toward q . Alternatively we could do it backwards, starting from state q and then computing its predecessors until reaching q or exhausting test set of state from which q is reached. One way to do a backward search on an automaton A = (Q, δ) is to construct an automaton A = (Q, δ ) where δ is the inverse of the transition relation δ. Solving the q → q reachability problem in A is equivalent to solving the q → q reachability problem in A by backward search. 26

3.2. SHORTEST PATHS

It is important to mention that the transition graphs of the automata treated in veri?cation are typically very big and are not stored explicitly in the computer memory, but rather generated on the ?y during the search. The successors of a global state are generated by choosing each time a transition of one of the components (or several components if this transition is common to more than one component) and transforming the global state according to the e?ect of this transition.

3.2

Shortest Paths

For the automata we will construct for the job-shop problem, the answer to the reachability problem is obvious: in the absence of constraints such as deadlines there will always be a path from the initial state (before any job has started) to the ?nal state (all jobs have terminated). In fact, there will be in?nitely many such paths corresponding to the di?erent feasible schedules and the optimization problem is to choose the one with the shortest makespan. This can be done by techniques based on shortest path algorithms, originally applied to weighted automata/graphs. Weighted automata can be used to associate some cost (energy, time, etc.) with transitions. Or, when the nodes correspond to physical locations, the weight associated with an edge can correspond to the length of the route between its vertices. Formally a weighted automaton is A = (Q, δ, w) where w : δ → R is a function that assigns to each transition (q, q ) ∈ δ a weight wq,q . With every ?nite run q0 ?→ q1 ?→ . . . ?→ qk we associate a cost C = w0,1 + w1,2 + . . . + wk+1,k . The shortest path between two states q and q is the run with the minimal C. From now on we assume that w is always positive and hence the shortest path between any two states has no cycles. The q-unfolding of a weighted automaton is a tree labeled with pairs in Q × R+ , starting with (q, 0) and generating for every node (p, r) successors of the form (p , r ) such that (p, p ) ∈ δ and r = r + wp,p . Clearly, for any node (p, r) in the tree, r corresponds to the distance from q to p via the corresponding path. A weighted automaton and its unfolding appear in Figures 3.6 and 3.7. Finding the shortest path between q and q is thus equivalent to ?nding the node (q , r) with the minimal r in the q-unfolding of the automaton.

1

w0,1 w1,2 wk?1,k

q2

10 9 4 7 5

q4

q1

2

3

6

q3

2

q5

Figure 3.6: A weighted automaton A(Q, δ, w)

27

3.2. SHORTEST PATHS

q1 , 0

q2 , 10

q3 , 5

q3 , 12

q4 , 11

q2 , 8

q4 , 14

q5 , 7

q2 , 15

q4 , 21

q5 , 14

q5 , 15

q3 , 10

q4 , 9

q5 , 18

q1 , 14

q4 , 13

Figure 3.7: The q1 -unfolding of the weighted automaton of Figure 3.6

The BFS algorithm can stop after reaching q while there exists a shorter path to q with 10 1 more transitions. For example, BFS can reach q4 via the path q1 ?→ q2 ?→ q4 , Figure 3.8, 5 3 1 while there exists a shorter path q1 ?→ q3 ?→ q2 ?→ q4 .

q1

10 5

q2

2 1

q3

q3

q4

Figure 3.8: BFS algorithm applied to the automata of Figure 3.6

The well-known algorithm due to Dijkstra ?? gives the shortest path from q to any other state for graphs with positive weights. Dijkstra’s algorithm can be viewed as iterating with a function d : Q → R+ such that at every iteration i, di (p) is the length of the shortest path to p having at most i transitions. If p is not reachable within i steps di (p) = ∞. When the algorithm terminates d(p) holds the length of the shortest path to p. Algorithm 3 (Dijkstra’s algorithm (A, q))

28

3.2. SHORTEST PATHS

d0 (q) = 0; ?p = q d0 (p) = ∞; i = 0; Repeat begin i := i + 1; ?p ∈ Q; di (p) = min({di?1 (p ) + Wpp ] : p ∈ P re(p)} ∪ {di (p)}); end Until di = di+1

29

Chapter 4

Adding Time to Automata

Models based on ?nite-state automata can express only qualitative temporal relations between events in a system. We can say that one events precedes another but we cannot specify in a natural way the quantity of time that separates them. In many application domains such as real-time programming or circuit timing analysis, the correctness of a system depends on the relative speeds of the system and its environment. Hence we need a formalism where we can express quantitative timing features of systems such as response time of programs, propagation delays in logical gates or constraints on inter-arrival times of external events. In the context of scheduling problems, we would like to express the duration of a step in a job as a constraint on the time elapsed between its initiation and termination transitions. Several proposals for extending veri?cation methodology to model quantitative time were proposed in the late 80s and the timed automaton model Alur and Dill [ACD93, AD94] turned out to be very useful. This model is rich enough to express all timing problems of practical interest, yet the basic reachability problems for it can be solved algorithmically [HNSY94] using extensions of the graph search algorithms presented in Section Chapter 3.1 Timed automata can be viewed as a special class of hybrid systems, systems that combine discrete transitions and continuous evolution, of the type usually described by di?erential equation. This intuition is not so easy to grasp upon ?rst reading. We will present timed automata incrementally, by investigating ?rst the most straightforward approaches for a adding quantitative time to automata.

4.1

Explicit Modeling of Time

Consider two processes P1 and P2 , with execution times of 3 and 2 time units, respectively. Each process can be in three basic “modes”: it can be waiting before starting, it can be active (executing), and it can be ?nished after having passed enough time in the active mode. The state of the process in the active mode is determined by the amount of time since the process has started. If we ?x the time granularity to be one time unit we can model the processes using the automata A1 and A2 of Figure 4.1. The states of A1 are {p1 , 0, 1, 2, 3, p 1 } where p1 is the initial state indicating that the process is still inactive, and p1 is the ?nal state. The other states represent the amount of time elapsed in the active mode. The automaton have two types of transition, immediate transitions such as “start” and “end”, that consume no time, and a special time-passage transition “tick” indicating the passage of time unit. The behaviors of the processes are the runs of the automaton consisting of sequences of states and both types of transitions. For example, a behavior where P1 waits one of one time unit and then starts is

Another discrete formalism for which quantitative timing information can be added are the Petri nets, which are quite popular for modeling manufacturing systems.

1

31

4.1. EXPLICIT MODELING OF TIME

captured by the run p1 ?→ p1 ?→ 0 ?→ 1 ?→ 2 ?→ 3 ?→ p1 and its corresponding duration is the number of tick transitions.

tick

tick start1 tick tick tick end1

tick

p1

start1 0 tick 1 tick 2 tick 3 end1 tick

p2

start2 0 tick 1 tick 2 end2 tick

p2

p1

Figure 4.1: The two automata A1 and A2 corresponding to P1 and P2

When two or more automata run in parallel, each automaton can take its immediate transitions independently but the “tick” transitions are synchronized: if one process takes such a transition, all the the others need to take it as well. The e?ect of the tick transition on any active process in a state i is is to move it to state i + 1. The automaton A = A1 ||A2 is shown in Figure 4.2. It starts in an initial state (p1 , p2 ) where the two processes are waiting. Each of the processes can start executing after any number of ticks and all the possible behaviors of the system correspond to runs of A. For example, the behavior where both processes wait 2 time units and then start at the same time2 is captured by the run: (p1 , p2 ) ?→ (p1 , p2 ) ?→ (p1 , p2 ) ?→ (0, p2 ) ?→ (0, 0) ?→ (1, 1) ?→ (2, 2) ?→ (2, p2 ) ?→ (3, p2 ) ?→ (p1 , p2 ) A behavior where P1 starts immediately and P2 starts 2 time units later is represented by the

2 In fact, behaviors where several independent immediate transitions occur at the same time can usually be represented by more than one run, each run corresponding to a di?erent interleaving of concurrent transitions. For start1 start2 start2 start1 example, the run fragment (p1 , p2 ) ?→ (0, p2 ) ?→ (0, 0) can be replaced by (p1 , p2 ) ?→ (p1 , 0) ?→ (0, 0).

tick

tick

start1 tick

start2

tick

tick

end2

end1

32

4.1. EXPLICIT MODELING OF TIME

run

(p1 , p2 ) ?→ (0, p2 ) ?→ (1, p2 ) ?→ (2, p2 ) ?→

tick end1 tick end2

start1

tick

tick

start2

(2, 0) ?→ (3, 1) ?→ (p1 , 1) ?→ (p1 , 2) ?→ (p1 , p2 ) A behavior where P2 starts immediately and P1 starts 1 unit after P2 terminates is represented by the run (p1 , p2 ) ?→ (p1 , 0) ?→ (p1 , 1) ?→ (p1 , 2) ?→ (p1 , p2 ) ?→

start1 tick tick tick end1 start2 tick tick end2 tick

(p1 , p2 ) ?→ (0, p2 ) ?→ (1, p2 ) ?→ (2, p2 ) ?→ (3, p2 ) ?→ (p1 , p2 ) The duration of a run, the time from the initial state to (p1 , p1 ), is just the number of ticks in the run (5, 4 and 6 units, respectively). Since each processes can choose to perform its start transition independently, many possible combination of clock values are possible, each re?ecting a di?erent choice in the past. This can lead to a state explosion as the number of processes grow. In addition, each re?nement of the time scale (e.g. letting events occur in time instants that are multiples of 1/2) will increase the number of states in each automaton. The advantage of this representation is, however, that it allows us to stay within the familiar framework of automata and to apply standard reachability and shortest-path algorithms to timed systems, by assigning weight 1 to tick transitions and 0 to immediate transitions

33

4.2. CLOCK VARIABLES

tick start1

p1 p2

start2

0 p2

tick start2

p1 0

start1 tick

1 p2

tick start2

00

tick start1

p1 1

tick

2 p2

tick start2

10

tick

11

tick

01

tick start1

p1 2

end2

3 p2

20

tick

21

22

12

02

p1 p2

start1

tick

31

end1 end2

0 p2

tick

p1 1

tick tick

1 p2

p1 2

2 p2

tick end2 end1 tick

3 p2

p1 p2

Figure 4.2: The global automaton of A = A1 ||A2 .

4.2

Clock Variables

A more compact representation of such automata can be achieved by using special auxiliary variables to represent time passage instead of encoding elapsed time explicitly inside states. These are clock variables or counters that are reset to zero when an active state is entered, 34

4.2. CLOCK VARIABLES

incremented by one with every tick and their value is tested in transitions that leave active states. Figure 4.3 shows how this is done for the automata of Figure 4.1, by adding clock variables X1 and X2 . A state (or con?guration) of an augmented automaton is a pair of the form (q, v) where q is an explicit state and v is a value for the variable(s). Such clock variables can range over the non-negative integers with the special value ⊥ indicating that the clock is not active in a state. A run of A1 will look like (p1 , ⊥) ?→ (p1 , ⊥) ?→ (p1 , 0) ?→ (p1 , 1) ?→ (p1 , 2) ?→ (p1 , 3) ?→ (p1 , ⊥)

tick atart1 tick tick tick end1

tick

p1

start1

p2

start2

tick

x1 := 0

tick

x2 := 0 p2

tick

x1 := x1 + 1

p1 x1 = 3

end1

x2 := x2 + 1 x2 = 2

end2

tick

p1

p2

tick

Figure 4.3: The automata A1 and A2 : using clocks variables. Note that the di?erence between the two approaches is purely syntactic. If we expand the automata A1 and A2 by adding clock values to the states we obtain automata isomorphic to A1 and A2 (see Figure 4.4).

35

4.2. CLOCK VARIABLES

tick

tick

(p1 , ⊥) (p2 , ⊥)

start1

(p1 , 0)

start2

(p2 , 0)

tick

(p1 , 1)

tick

(p2 , 1)

tick

(p1 , 2)

tick

(p2 , 2)

tick

(p1 , 3)

end2

(p2 , ⊥)

tick

end1 tick

(p1 , ⊥)

Figure 4.4: The automata A1 and A2 expanded with explicit representation of clock values in the state. When we compose A1 and A2 we obtain the global automaton A of Figure 4.5 which looks simpler than A of Figure 4.2. This simplicity of the transition graph is, however, misleading. Consider for example state (p1 , p2 ) where both processes are active. There are two transitions leaving this state and they are guarded by conditions X1 = 3 and X2 = 2, respectively. The state itself does not tell us whether each of the transitions can be taken as this depends on the values of the clocks which, in turn, depends on the previous history (when the clocks were reset to zero). In the worst case, reachability algorithms for A might need to expand it into A. Nevertheless, although modeling with clock variables does not change the worst-case complexity of the reachability problem, it allows us to use symbolic methods and work with an arbitrary time granularity.

36

4.2. CLOCK VARIABLES

tick start1

p1 p2

start2

x1 := 0

tick

x2 := 0

tick

x1 := x1 + 1

end1 tick

p1 p2

start2

p1 p2

x2 := 0 x1 := 0

start1

x2 := x2 + 1

end2

x1 = 3

tick

x2 = 2

tick

p1 p2

start2

x1 := x1 + 1 x2 := x2 + 1

p1 p2

x1 = 3 x2 = 2

end2

p1 p2

start1

x2 := 0

tick

end1

x1 := 0 x1 := x1 + 1

tick

x2 := x2 + 1

p1 p2

x2 = 2

end2 tick

p1 p2

x1 = 3

end1

p1 p2

Figure 4.5: The global automaton A = A1 ||A2 . Symbolic or implicit representation methods can be applied to variables that belong to some mathematical domain such as integers. Instead of representing a set of states explicitly (e.g. in a table) it can be represented by a formula. Suppose, for example, two processes with durations d1 and d2 , respectively such that d1 < d2 , that enter their respective active states 2 time units one after the other. The set of reachable clock values has the form {(2, 0), (3, 1), (4, 2), . . . (d1 , d1 ? 2)} and its size depends on d1 . However the formula X1 ? X2 = 2 ∧ X1 ≤ d1 characterizes this set, and its size does not depends on d1 . In fact, it can characterize the reachable states even if we do not assume any ?xed time granularity and work with dense time. This way we may allow events happen anywhere on the real-time axis and view the clocks di?erently, as continuous variables that evolve with derivative 1 inside active states. These are timed automata, see Figures 4.6 and 4.7, which can be seen as the limit of a process that makes the time steps associated with tick transitions in?nitesimal.

37

4.3. BASICS OF TIMED AUTOMATA

p1

start1

p2

start2

x1 := 0 x1 = 1 ˙ p1

end1

x2 := 0 p2 x2 = 1 ˙

end2

x1 = 3 p1 p2

x2 = 2

Figure 4.6: Two Timed Automata

p1 p2

start1 start2

x1 := 0 x1 = 1 ˙ x1 = 3

end1

x2 := 0

p1 p2

start2

p1 p2 x2 = 1 ˙

x2 := 0

start1

x2 = 2

end2

x1 := 0 x1 = 1 ˙ x2 = 1 ˙

p1 p2

start2

p1 p2

x2 = 2

end2

p1 p2

start1

x1 = 3

end1

x2 := 0 x2 = 1 ˙

x1 := 0

p1 p2

x2 = 2

end2

p1 p2 x1 = 1 ˙

x1 = 3

end1

p1 p2

Figure 4.7:

4.3

Basics of Timed Automata

De?nition 2 (Timed Automata) A timed automaton is a tuple A = (Q, C, s, f, Δ) where Q is a ?nite set of states, C is a ?nite set of clocks, and Δ is a transition relation consisting of 38

4.3. BASICS OF TIMED AUTOMATA

elements of the form (q, φ, ρ, q ) where q and q are states, ρ ? C and φ (the transition guard) is a boolean combination of formulae of the form (c ∈ I) for some clock c and some integer-bounded interval I. States s and f are the initial and ?nal states, respectively. De?nition 3 (Clock Valuation) A clock valuation is a function v : C → R+ ∪ {0}, or equivalently a |C|-dimensional vector over R+ . We denote the set of all clock valuations by H. A con?guration of the automaton is hence a pair (q, v) ∈ Q × H consisting of a discrete state (sometimes called “location”) and a clock valuation. Every subset ρ ? C induces a reset function Resetρ : H → H de?ned for every clock valuation v and every clock variable c ∈ C as Resetρ v(c) = 0 if c ∈ ρ v(c) if c ∈ ρ

That is, Resetρ resets to zero all the clocks in ρ and leaves the other clocks unchanged. We use 1 to denote the unit vector (1, . . . , 1) and 0 for the zero vector. De?nition 4 (Steps and Runs) A step of the automaton is one of the following: ? A discrete step: (q, v) ?→ (q , v ), where there exists δ = (q, φ, ρ, q ) ∈ Δ, such that v satis?es φ and v = Resetρ (v). ? A time step: (q, v) ?→ (q, v + t1), t ∈ R+ . A run of the automaton starting from a con?guration (q0 , v0 ) is a ?nite sequence of steps ξ:

1 2 n (q0 , v0 ) ?→ (q1 , v1 ) ?→ · · · ?→ (qn , vn ).

0

t

t

t

t

The logical length of such a run is n and its metric length is t1 + t2 + · · · + tn . It is sometimes useful to augment a time automaton A with an additional clock t which is active in every state and never reset to zero. We call the obtained automaton A the extended automaton of A, and its runs are called extended runs of A . Since t always represents absolute time, (q, v, t) is reachable in A i? (q, v) is reachable in A at time t. Note that we omit transition labels, such as “start” or “end”, used in the previous section from the runs because we will not need them in the sequel, and we use their duration, 0, instead. Although in the formal de?nition all clocks evolve uniformly with derivative 1 in all states, there are states were certain clock values are not important because in all paths starting from those states they are not tested before being reset to zero (for example, clock X1 in state (p1 , p2 )). We say that a clock is inactive in such a state and instead of writing down its value we use the symbol ⊥. The following run of the automaton A of Figure 4.7 corresponds to the case where P1 started after 0.23 time units and P2 started 2.1 time units later: (p1 , p2 , ⊥, ⊥) ?→ (p1 , p2 , 0, ⊥) ?→ (p1 , p2 , 2.1, ⊥) ?→ (p1 , p2 , 2.1, 0) ?→ (p1 , p2 , 3, 0.9) ?→ (p1 , p2 , ⊥, 0.9) ?→ (p1 , p2 , ⊥, 2) ?→ (p1 , p2 , ⊥, ⊥) Note also that the de?nition of a run allows to “split” time steps, for example, the step 2.1 0.6 0.7 0.8 (p1 , p2 , 0, ⊥) ?→ (p1 , p2 , 2.1, ⊥) can be written as (p1 , p2 , 0, ⊥) ?→ (p1 , p2 , 0.6, ⊥) ?→ (p1 , p2 , 1.3, ⊥) ?→ (p1 , p2 , 2.1, ⊥). One of the most useful features of timed automata is their ability to epxress and analyze system with temporal uncertainty. In the automaton of Figure 4.8 we see that the transition 39

0 1.1 0 0.23 2.1 0 0.9

4.3. BASICS OF TIMED AUTOMATA

from q1 to q2 can happen when the value of X is anywhere in the interval [1, 3]. A veri?cation algorithm should explore all these in?nitely-many runs that correspond to this choice, and the major result on timed automata [AD94, HNSY94, ACD93] is that although the state space is in?nite, reachability and other veri?cation problems for timed automaton are solvable. The basic idea for reachability computation for timed automata is the following: 1. Sets of reachable con?gurations are stored as unions of symbolic states of the form (q, Z) where q is a discrete state and Z is a subset of the clock space H. 2. Computation of successors of a symbolic state is done in two phases. First all the time successors of (q, Z) are computed leading to (q, Z ) where Z consists of all clock valuation reachable from Z by letting time progress by any amount. Then Z is intersected with the transition guard of each transition to determine the con?guration where the transition can take place and then the reset operations is applied to those con?gurations.

1 ≤ X ≤ 3 X := 0 q1 q2 2≤Y ≤4

2≤Y ≤4 Y := 0

q3

X =1

q4

Figure 4.8: A timed automaton.

Consider the automaton of Figure 4.8. Starting from the symbolic state (q1 , X = Y = 0), letting time pass we reach the symbolic state (q1 , X = Y ≥ 0). The intersection with the guard of the transition to q2 gives (q1 , 1 ≤ X = Y ≤ 3) and the resetting of X leads us ?nally to (q2 , X = 0 ∧ 1 ≤ Y ≤ 3) from where we restart with time passage and so on. The whole computation for that automaton appears in Figure 4.9. The fundamental result concerning timed automata is that the sets of clock valuations in symbolic states always belong to a special class of polyhedra called zones which is ?nite for any given automaton. De?nition 5 (Zones and Symbolic States) A zone is a subset of H consisting of points satisfying a conjunction of inequalities of the form ci ? cj ≥ d or ci ≥ d. A symbolic state is a pair (q, Z) where q is a discrete state and Z is a zone. It denotes the set of con?gurations {(q, z) : z ∈ Z}. De?nition 6 (Successors) Let A = (Q, C, s, f, Δ) be a timed automaton and let (q, Z) be a symbolic state. ? The time successor of (q, Z) is the set of con?gurations which are reachable from (q, Z) by letting time progress: P ostt (q, Z) = {(q, z + r1) : z ∈ Z, r ≥ 0}. We say that (q, Z) is time-closed if (q, Z) = P ostt (q, Z). 40

4.3. BASICS OF TIMED AUTOMATA

? The δ-transition successor of (q, Z) is the set of con?gurations reachable from (q, Z) by taking the transition δ = (q, φ, ρ, q ) ∈ Δ: P ostδ (q, Z) = {(q , Resetρ (z)) : z ∈ Z ∩ φ}. ? The δ-successor of a time-closed symbolic state (q, Z) is the set of con?gurations reachable by a δ-transition followed by passage of time: Succδ (q, Z) = P ostt (P ostδ (q, Z)). ? The successors of (q, Z) is the set of all its δ-successors: Succ(q, Z) =

δ∈Δ

(Succδ (q, Z)).

Equipped with these operations (which transform zones into zones) we can solve reachability problems for timed automata using graph search algorithms that work on the “simulation graph”, a graph whose nodes are symbolic states connected by the successor relation. This approach for verifying timed automata was ?rst proposed in [HNSY94] and implemented in the tool KRONOS [Y97]. As we will see in the next chapter, the timed automata for modeling job-shop problems have a special structure and in particular they are acyclic. The following generic algorithm computes all the reachable con?guration for such automata starting from con?guration (s, 0). Algorithm 4 (Forward Reachability for Acyclic Timed Automata) Waiting:={P ostt {(s, 0)}}; while Waiting = ? do Pick (q, Z) ∈ Waiting; For every (q , Z ) ∈ Succ(q, Z); Insert (q , Z ) into Waiting; Remove (q, Z) from Waiting; end

41

4.3. BASICS OF TIMED AUTOMATA

q1 X=Y =0

q2 1≤Y ≤3 X =0

q3 2≤X≤4 Y =0

q4 2≤Y ≤4 X ≥0

Figure 4.9: Forward reachability computed for the automaton of Figure 4.8

Since the automaton is acyclic the algorithm will terminate even if we do not keep a list of explored states. However, for performance reasons such tests are important as we will see later, especially when there are many paths that lead to the same discrete state. As in untimed automata, reachable sets can be computed backwards by computing the predecessors of a symbolic state. The de?nitions are similar to that of successors, except for the fact the we need to compute inverse images of reset functions. De?nition 7 (Predecessors) Let A = (Q, C, s, f, Δ) be a timed automaton and let (q, Z) be a symbolic state. ? The time predecessors of (q, Z) is the set of con?gurations from which (q, Z) can be reached by letting time progress: P ret (q, Z) = {(q, v) : v + r1 ∈ Z, r ≥ 0}. We say that (q, Z) is time-closed if (q, Z) = P ret (q, Z). ? The δ-transition predecessor of (q, Z) is the set of con?gurations from which (q, Z) is reachable by taking the transition δ = (q , φ, ρ, q) ∈ Δ: P reδ (q, Z) = {(q , v ) : v ∈ Reset?1 (Z) ∩ φ}. ρ ? The predecessors of (q, Z) is the set of all con?guration from which (q, Z) is reachable by any transition δ followed by passage of time: P re(q, Z) =

δ∈Δ

P ret (P reδ (q, Z)).

42

4.3. BASICS OF TIMED AUTOMATA

The following algorithm computes the set of states from which a ?nal state f is reachable. Algorithm 5 (Backward Reachability for Acyclic Timed Automata) Waiting:={(f, H)}; while Waiting = ? do Pick (q, Z) ∈ Waiting; For every (q , Z ) ∈ P re(q, Z); Insert (q , Z ) into Waiting; Remove (q, Z) from Waiting; end

q4

q2 Y ≤4

q3 X≤1

q1 X≤3Y ≤4 Y ?X ≤3

q1 X≤1Y ≤4 Y ?X ≥1

Figure 4.10: Backward reachability computed for the automaton of Figure 4.8

43

Part II

Contribution

45

Chapter 5

Deterministic Job Shop Scheduling

In this chapter we model the job-shop scheduling problem using a special class of acyclic timed automata. Finding an optimal schedule corresponds, then, to ?nding a shortest (in terms of elapsed time) path in the automaton. This representation provides new techniques for solving the optimization problem. We present algorithms and heuristics for ?nding shortest paths in timed automata and test their implementation on numerous benchmark examples.

5.1

Formal de?nitions

De?nition 8 (Job-Shop Speci?cation) Let M be a ?nite set of resources (machines). A job speci?cation over a set M of resources is a triple J = (k, μ, d) where k ∈ N is the number of steps in J, μ : {1..k} → M indicates which resource is used at each step, and d : {1..k} → N speci?es the length of each step. A job-shop speci?cation is a set J = {J 1 , . . . , J n } of jobs with J i = (ki , μi , di ). We make the assumption that each machine is used exactly once by every job. This assumption simpli?es the presentation but still maintains the inherent complexity. We denote R+ by T , abuse J for {1, . . . , n} and let K = {1, . . . , k}. De?nition 9 (Feasible Schedules) A feasible schedule for a job-shop speci?cation J = {J 1 , . . . , J n } is a relation S ? J × K × T so that (i, j, t) ∈ S indicates that job J i is busy doing its j th step at time t and, hence, occupies machine μi (j). A feasible schedule should satisfy the following conditions: 1. Ordering: if (i, j, t) ∈ S and (i, j , t ) ∈ S then j < j implies t < t (steps of the same job are executed in order). 2. Covering and Non-Preemption: For every i ∈ J and j ∈ K, the set {t : (i, j, t) ∈ S} is a non-empty set of the form [r, r + d] for some r ∈ T and d = di (j) (every step is executed continuously until completion). 3. Mutual Exclusion: For every i, i ∈ J , j, j ∈ K and t ∈ T , if (i, j, t) ∈ S and (i , j , t) ∈ S then μi (j) = μi (j ) (two steps of di?erent jobs which execute at the same time do not use the same machine). The start time time of step j in job i is s(i, j) = min t

(i,j,t)∈S

47

5.1. FORMAL DEFINITIONS

The length of a schedule is the maximal t over all (i, j, t) ∈ S. The optimal schedule of a job-shop speci?cation J is a feasible schedule with the shortest length. From the relational de?nition of schedules one can derive the following commonly-used de?nition, namely 1. The machine allocation function α : M × T → J stating which job occupies a machine at any time, de?ned as α(m, t) = i if (i, j, t) ∈ S and μi (j) = m. 2. The task progress function β : J × T → M stating what machine is used by a job is at a given time, de?ned as β(i, t) = m if (i, j, t) ∈ S and μi (j) = m. The machine allocation and task progress function are partial, because a machine or a job might be idle at certain times. A machine m is idle at t, α(m, t) = ⊥, if / ?i, j s.t. μi (j) = m (i, j, t) ∈ S. A job i is idle at t, β(i, t) = ⊥, if / ?j s.t. μi (j) = m (i, j, t) ∈ S. A step j in a job i is enabled at t if s(i, j ? 1) + di (j ? 1) < t < s(i, j) and α(m, t) = ⊥.

As an example consider M = {m1 , m2 , m3 } and two jobs J 1 = (m3 , 2), (m2 , 2), (m1 , 4) and J 2 = (m2 , 3), (m3 , 1) Two schedules S1 and S2 are depicted in Figure 5.1 in both machine allocation and task progress forms. The length of S2 is 8 and it is the optimal schedule.

48

5.2. MODELING WITH TIMED AUTOMATA

α m1 J1 S1 J2

0

β

J1 J2 J1

0 2

m3 m2

m2 m3

2 3 4 5

m1

m2 m3

J1 J2

3 4 5

9

9

m1 J1 S2 J2

0 2 4

J1 J1 J1

0 2 4

m3

m2

m1 m2 m3

7

m2 m3

J2 J2

7

8

8

Figure 5.1: Two feasible schedules S1 and S2 visualized as the machine allocation function α and the task progress function β.

Note that a job can be idle at time t even if its precedence constraints are satis?ed and the machine needed at this time is available. As one can see in schedule S2 of Figure 5.1, machine m2 is available at time t = 0 whereas J 2 does not use it and remains idle until time t = 4. If we execute the steps of J 2 as soon as they are enabled we obtain the longer schedule S1 . The ability to achieve the optimum by waiting instead of starting immediately increases the set of feasible solutions that need to be explored and is the major source of the complexity of scheduling.

5.2

5.2.1

Modeling with Timed Automata

Modeling Jobs

We construct for every job J = (k, μ, d) a timed automaton with one clock c and 2k + 1 states. For every step j such that μ(j) = m there will be two states in the timed automata, a state m which indicates that the job is waiting to start the step and a state m indicating that the job is executing the step. The initial state is the state μ(1) where the job J has not started yet, and the ?nal state is the state f where the job has terminated all its steps. The clock c is inactive at states m and upon entering m it is reset to zero without being tested. The automaton can leave the state m only after time d(j) has elapsed, this is done while testing if the clock c is larger or equal to d(j). Let M = {m : m ∈ M } and let μ : K → M be an auxiliary function such that μ(j) = m whenever μ(j) = m. De?nition 10 (Timed Automaton for a Job) Let J = (k, μ, d) be job. Its associated timed automaton is A = (Q, {c}, Δ, s, f ) with Q = P ∪ P ∪ {f } where P = {μ(1), . . . μ(k)}, and P = {μ(1), . . . , μ(n)}. The initial state is μ(1).

49

5.2. MODELING WITH TIMED AUTOMATA

The transition relation Δ consists of the following tuples j = 1..k (μ(j), true, {c}, μ(j)) (μ(j), c = d(j), ?, μ(j + 1)) j = 1..k ? 1 (μ(k), c = d(k), ?, f )

μ(1)

c := 0

μ(1)

μ(j)

c := 0

μ(j)

c = d(j)

?(j + 1)

μ(k)

c = d(k)

f

Figure 5.2: The automaton corresponding to the job J = (k, μ, d).

5.2.2

Modeling Job Shop Speci?cations

To construct the timed automaton for the whole job shop speci?cation we need to compose the automata for the individual tasks. The composition is rather standard, the only particular feature is the enforcement of mutual exclusion constraints by forbidding con?icting states, that is, global states in which two or more automata are in a state corresponding to the same resource m. De?nition 11 (Con?icting states) An n-tuple q = (q 1 , . . . , q n ) ∈ Qn is said to be con?icting if it contains two components q a and q b such that q a = q b = m ∈ M . 50

5.2. MODELING WITH TIMED AUTOMATA

Let be J = {J 1 , . . . , J n } a job shop speci?cation, and let be Ai = (Qi , {ci }, Δi , si , f i ) the timed automaton for job J i . We compose these automata and obtain a time automaton A = (Q, C, Δ, s, f ) with n clocks. The states of the composition is the Cartesian product of the states of the individual automata, excluding con?icting states. De?nition 12 (Mutual Exclusion Composition) Let J = {J 1 , . . . , J n } be a job-shop speci?cation and let Ai = (Qi , C i , Δi , si , f i ) be the automaton corresponding to each J i . Their mutual exclusion composition is the automaton A = (Q, C, Δ, s, f ) such that Q is the restriction of Q1 × . . . Qn to non-con?icting states, C = C 1 ∪ . . . ∪ C n , s = (s1 , . . . , sn ), f = (f 1 , . . . , f n ) and the transition relation Δ contains all the tuples of the form ((q 1 , . . . , q a , . . . , q n ), φ, ρ, (q 1 , . . . , pa , . . . , q n )) such that (q a , φ, ρ, pa ) ∈ Δa for some a and both (q 1 , . . . , q a , . . . , q n ) and (q 1 , . . . , pa , . . . , q n ) are non-con?icting.

1 2 n q0 , q0 , . . . , q0

Δ1

1 2 n q1 , q0 , . . . , q0

Δ2

1 2 n q0 , q1 , . . . , q0

Δn

1 2 n q0 , q0 , . . . , q1

Δ

1 2 n q2 , q0 , . . . , q0

1

Δ2

1 2 n q1 , q1 , . . . , q0

Δ2

1 2 n q2 , q1 , . . . , q0

Δ1

Figure 5.3: The timed automaton corresponding to the job shop speci?cation J {J 1 , J 2 , . . . , J n }

=

As can be seen from the de?nition and Figure 5.3, each discrete transition in A corresponds to a transition in one automaton. This is called the interleaving semantics and it is used only for technical convenience. If in a schedule two automata make transitions δ1 , δ2 at the same time δ1 δ2 δ2 δ1 instant, there will be two corresponding run fragments q ?→ q ?→ p and q ?→ q ?→ p in the automaton. As an example consider M = {m1 , m2 } and two jobs J 1 = (m1 , 4), (m2 , 5) and J 2 = (m1 , 3) The corresponding automata for the two jobs are depicted in Figure 6.4 and there composition in Figure 8.5. 51

5.2. MODELING WITH TIMED AUTOMATA

The job-shop timed automaton is acyclic and “diamond-shaped” with an initial state in which no job has started and a ?nal state where all jobs have terminated. A run of this automaton is called complete if it starts at s and terminates at f . All transitions in the global timed automaton indicate either a component moving from an active to an inactive state (these are guarded by conditions of the form ci = d), or a component moving into an active state (these are labeled by resets ci := 0 and are called starti transitions). Two transitions outgoing from the same state might represent a choice of the scheduler, for example, the two transitions outgoing from the initial state represent the decision to whom to give ?rst the resource m1 , either to J 1 and move to (m1 , m1 ), or to J 2 and move to (m1 , m1 ). The scheduler can also decide to start a job or let it idle, as we can see in the two transitions outgoing from the state (m2 , m1 ). The scheduler either starts job J 2 on machine m1 or let time pass until clock c1 satis?es the guard, and move to (f, m1 ). On the other hand some duplication of paths are just artifacts due to interleaving, for example, the two paths outgoing from (m2 , m1 ) to (m2 , m1 ) are practically equivalent. Recall that in a timed automaton, the transition graph might be misleading, because two or more transitions entering the same discrete state, e.g. transitions to (m2 , f ) might enter it with di?erent clock valuations, and hence lead to di?erent continuations.

m1 c1 := 0 m1 c1 = 4 m2 c1 := 0 m2 c1 = 5 f

m1 c2 := 0 m1 c2 = 3 f

Figure 5.4: The automata corresponding to the two jobs J 1 = (m1 , 4), (m2 , 5) and J 2 = (m1 , 3).

52

5.3. RUNS AND SCHEDULES

m1 m1

c1 := 0 c2 := 0

m1 m1

c1 = 4

m1 m1

c2 = 3

m2 m1

c1 := 0 c2 := 0

m1 f

c1 := 0

m2 m1

c1 = 5 c2 := 0

m2 m1

c1 := 0 c2 = 3

m1 f

c1 = 4

f m1

c2 := 0

m2 m1

c1 = 5 c2 = 3

m2 f

c1 := 0

f m1

c2 = 3 c1 = 5

m2 f

f f

Figure 5.5: The global timed automaton for the two jobs.

5.3

Runs and Schedules

In this section we will show the tight correspondence between feasible schedules and runs of the automaton. De?nition 13 (Derived Schedule) The derived schedule Sξ of a run ξ is a schedule where for every i, j s(i, j) = t where t is the absolute time in ξ and Ai makes a start transition from μi (j) to μi (j) Claim 1 Let A be the automaton generated for the job-shop speci?cation J according to De?nitions 1 and 2. Then: 1. For every complete run ξ of A, its derived schedule Sξ is feasible for J . 2. For every feasible schedule S for J there is a complete run ξ of A such that Sξ = S. Proof: The proof is by induction on the lengths of the run and schedule. A partial schedule S is a schedule S restricted to an interval [0, t]. A partial run is a run not reaching f . The section of a schedule at time t is given by a tuple (P , P, P , e) such that P , P and P are, respectively,

53

5.3. RUNS AND SCHEDULES

the sets of waiting, active and ?nished steps and e is a function from P to R+ indicating the time elapsed since the beginning of each active state. Formally: P = {(i, j) : s(i, j) > t} P = {(i, j) : 0 ≤ t ? s(i, j) ≤ di (j)} P = {(i, j) : di (j) ≤ t ? s(i, j)} and e(i, j) = t ? s(i, j). We de?ne the following correspondence between con?gurations of the automaton and sections of a schedule. Let ((q1 , . . . , qn ), (v1 , . . . , vn ), t) be an extended con?guration. Its associated section is de?ned by de?ning for each i ∈ J qi = μi (j) i? ?j < j (i, j) ∈ P ∧ ?j ≥ j (i, j) ∈ P

?j < j (i, j) ∈ P ∧ ?j > j (i, j) ∈ P ∧ qi = μi (j) i? (i, j) ∈ P ∧ vi = t ? s(i, j) The inductive hypothesis is that every partial run reaching (q, v, t) corresponds to a partial schedule which is feasible until t and whose section at t matches (q, v, t). This is true at the initial state and time t = 0 and can be easily shown to be preserved by discrete transitions and time passage. The proof of the other direction is similar, progressing over the ordered set of start and end time points. The schedules S1 and S2 appearing in Figures 5.6 and 5.7 correspond respectively to the complete runs ξ1 and ξ2 of the timed automaton of Figure 8.5.

J1 S1 J2

0

m1 m1

4

m2

7

9

Figure 5.6: A schedule ξ1 : (m1 , m1 , ⊥, ⊥) ?→ (m1 , m1 , 0, ⊥) ?→ (m1 , m1 , 4, ⊥) ?→ (m2 , m1 , ⊥, ⊥) ?→ (m2 , m1 , 0, ⊥) ?→ (m2 , m1 , 0, 0) ?→ (m2 , m1 , 3, 3) ?→ (m2 , f, 3, ⊥) ?→ (m2 , f, 5, ⊥) ?→ (f, f, ⊥, ⊥)

2 0 0 0 3 0 0 4 0

54

5.4. SHORTEST PATH USING TIMED AUTOMATA REACHABILITY

J1 S2 J2

0

m1 m1

3 7

m2

12

Figure 5.7: Another schedule ξ2 : (m1 , m1 , ⊥, ⊥) ?→ (m1 , m1 , ⊥, 0) ?→ (m1 , m1 , ⊥, 3) ?→ (m1 , f, ⊥, ⊥) ?→ (m1 , f, 0, ⊥) ?→ (m1 , f, 4, ⊥) ?→ (m2 , f, ⊥, ⊥) ?→ (m2 , f, 0, ⊥) ?→ (m2 , f, 5, ⊥) ?→ (f, f, ⊥, ⊥) Corollary 2 (Job-Shop Scheduling and Timed Automata) The optimal job-shop scheduling problem can be reduced to the problem of ?nding the shortest path in a timed automaton.

5 0 0 4 0 0 0 3 0

5.4

Shortest Path using Timed Automata Reachability

In this section we show how the symbolic forward reachability algorithm is used to ?nd a shortest path and hence to solve the optimal job-shop scheduling problem. Let A be the extended timed automaton obtained from A by adding an absolute clock t. The two runs ξ1 and ξ2 are, respectively, the extended runs of ξ1 and ξ2 . ξ1 : (m1 , m1 , ⊥, ⊥, 0) ?→ (m1 , m1 , 0, ⊥, 0) ?→ (m1 , m1 , 4, ⊥, 4) ?→ (m2 , m1 , ⊥, ⊥, 4) ?→ (m2 , m1 , 0, ⊥, 4) ?→ (m2 , m1 , 0, 0, 4) ?→ (m2 , m1 , 3, 3, 7) ?→ (m2 , f, 3, ⊥, 7) ?→ (m2 , f, 5, ⊥, 9) ?→ (f, f, ⊥, ⊥, 9) ξ2 : (m1 , m1 , ⊥, ⊥, 0) ?→ (m1 , m1 , ⊥, 0, 0) ?→ (m1 , m1 , ⊥, 3, 3) ?→ (m1 , f, ⊥, ⊥, 3) ?→ (m1 , f, 0, ⊥, 3) ?→ (m1 , f, 4, ⊥, 7) ?→ (m2 , f, ⊥, ⊥, 7) ?→ (m2 , f, 0, ⊥, 7) ?→ (m2 , f, 5, ⊥, 12) ?→ (f, f, ⊥, ⊥, 12) The value of the additional clock in each reachable con?guration represents the time to reach the con?guration according to this run, and, in particular, its value in the ?nal state represents the length of this run, 9 in ξ1 and 12 in ξ2 . Consequently to ?nd the shortest path in a timed automaton we need to compare the value of t in all the reachable extended con?gurations of the form (f, v, t). This set of reachable con?gurations can be found using the standard forward reachability algorithm for acyclic timed automata Algorithm 4. Remark: A common method used in reachability algorithms for reducing the number of explored symbolic states is the inclusion test. It is based on the fact that Z ? Z implies 55

5 0 0 4 0 0 0 3 0 2 0 0 0 3 0 0 4 0

5.4. SHORTEST PATH USING TIMED AUTOMATA REACHABILITY

Succδ (q, Z) ? Succδ (q, Z ) for every δ ∈ Δ. Hence, whenever a new symbolic state (q, Z) is generated, it is compared with any other (q, Z ) in the waiting list: if Z ? Z then (q, Z) is not inserted and if Z ? Z, (q, Z ) is removed from the list. Allowing the job-shop automaton to stay inde?nitely in any state makes the explored zones “upward-closed” with respect to absolute time and increases signi?cantly the e?ectiveness of the inclusion test. Figure 5.8 shows the simulation graph of the extended timed automaton of Figure 8.5. From every ?nal symbolic state (f, Z) in the simulation graph we can extract G(f, Z), the length of the minimal run among all the runs that share the same qualitative path: G(f, Z) = min{t : (v, t) ∈ Z} Thus the length of the optimal schedule is t? = min{G(f, Z) : (f, Z) is reachable in A }. To construct the optimal schedule it is su?cient to ?nd a run of length t? . Hence, running a reachability algorithm on A is guaranteed to ?nd the minimal schedule.

56

5.5. LAZINESS AND NON-LAZINESS

m1 m1

m1 m1

t = c1 ≥ 0

m1 m1

t = c2 ≥ 0

m2 m1

t≥4

m1 f

t≥3

t≥4 c1 ≥ 0 t ? c1 ≥ 4

m2 m1

t≥4 c2 ≥ 0 t ? c2 ≥ 4

m2 m1

t≥3 c1 ≥ 0 t ? c1 ≥ 3

m1 f

f m1

t≥9

t≥4 c1 ≥ c2 ≥ 0 t ? c1 ≥ 4 t ? c2 ≥ 4

m2 m1

t≥4 c2 ≥ c1 ≥ 0 t ? c1 ≥ 4 t ? c2 ≥ 4

m2 m1

m2 f

t≥7

t≥9 c2 ≥ 0 t ? c2 ≥ 9

f m1

t≥9 t ? c2 ≥ 4 c2 ≥ 0

f m1

t≥7 t ? c1 ≥ 4 c1 ≥ 3

m2 f

t≥7 t ? c1 ≥ 4 1 ≤ c1

m2 f

m2 f

t≥7 c1 ≥ 0 t ? c1 ≥ 3

f f

t ≥ 12

f f

t ≥ 12

f f

t≥9

f f

t≥9

f f

t ≥ 12

Figure 5.8: The simulation graph of the extended job-shop timed automaton of Figure 5.3

5.5

Laziness and Non-Laziness

In this section we show that only one point inside the zone of each symbolic state is su?cient for ?nding the optimal schedule.

57

5.5. LAZINESS AND NON-LAZINESS

5.5.1

Lazy Schedule

De?nition 14 (Lazy Schedules) Let S be a schedule, let i be a job and j a step with μi (j) = m. We say that S exhibits laziness at (i, j) if there exists in S an interval [t, s(i, j)] where (i, j) is enabled. A schedule S is non-lazy if it exhibits no laziness. Laziness captures the phenomenon of useless waiting: a job whose step is enabled is waiting while no other job pro?ts from its waiting. We will prove that every schedule can be transformed into a non-lazy one without increasing its length. Consider ?rst the schedule S of Figure 5.9 exhibiting laziness at (2, 1). By starting step (2, 1) earlier we obtain the schedule S with two new occurrences of laziness at (2, 2) and (3, 1). Those are removed yielding S with laziness at ? (3, 2) and after removing it we obtain the non-lazy schedule S. Claim 3 (Non-Lazy Optimal Schedules) Every lazy schedule S can be transformed into a ? ? non-lazy schedule S with |S| ≤ |S|. Hence every job-shop speci?cation admits an optimal nonlazy schedule. Proof: Let S be a schedule, and let L(S) ? J × K be the set of steps that are not preceded by laziness in S, namely L(S) = {(i, j) : ?(i , j ) (i, j) there is no laziness in(i , j )}.

In Figure 5.9 these sets are at the left of the dashed lines. We pick a lazy step (i, j) s.t. / s(i, j) ≤ s(i , j ) for all (i , j ) ∈ L(S) and shift its start time backward until we obtain a new feasible schedule S which is not lazy at (i, j). The schedule S veri?es L(S ) ? L(S) ∪ (i, j) and |S | ≤ |S|. Applying this procedure successively we increase L(S) at each step and due to ?niteness of the set of steps, the laziness removal procedure terminates.

58

5.5. LAZINESS AND NON-LAZINESS

J1 S J2 J3

0

m1

m2 m1 m2 m1 m3

11

2

4

6 7 8 9

J1 S J2 J3

0

m1

m2 m1 m2 m1 m3

2

5 6 7 8 9

11

J1 S J2 J3

0

m1

m2 m1 m1

2 5 6 8

m2 m3

11

J1 ? S J2 J3

0

m1

m2 m1 m1 m2 m3

8

2

5 6

9

Figure 5.9: Removing laziness from a schedule. The dashed line indicates the frontier between L(S) and the rest of the steps

5.5.2

Immediate and Lazy Runs

Having shown that an optimal schedule can be found among the non-lazy ones we can modify our search procedure to look only for runs of the automaton whose corresponding schedules are non-lazy. We ?rst de?ne the weaker notion of immediate runs such that each non-lazy schedule corresponds to an immediate run but not all immediate runs are non-lazy. De?nition 15 (Immediate Runs) An immediate run is a run where all the transitions are taken as soon as they are enabled. A non-immediate run contains a fragment (q, v) ?→ (q, v + t) ?→ (q , v ) 59

t 0

5.5. LAZINESS AND NON-LAZINESS

where the transition taken at (q, v + t) is enabled already at (q, v + t ) for some t < t. Clearly a derived schedule of a non-immediate run exhibits laziness. Corollary 4 In order to ?nd an optimal schedule it is su?cient to explore the (?nite) set of immediate runs. Every qualitative path in a timed automaton may correspond to in?nitely many runs. For example the family of runs {ξ(r) : 0 ≤ r ≤ 2} ξ(r) : (m1 , m1 , ⊥, ⊥) ?→ (m1 , m1 , 0, ⊥) ?→ (m1 , m1 , 4, ⊥) ?→ (m2 , m1 , ⊥, ⊥) ?→ (m2 , m1 , 0, ⊥) ?→ (m2 , m1 , r, ⊥) ?→ (m2 , m1 , r, 0) ?→ (m2 , m1 , r + 3, 3) ?→ (m2 , f, r + 3, ⊥) ?→ (m2 , f, 5, ⊥) ?→ (f, f, ⊥, ⊥) Each ξ(r) corresponds to a schedule like S(r) of Figure 5.10. Whenever r > 0 the run is not immediate and the schedule is lazy. Corollary 4 allows us to explore only ξ(0).

0 2?r 0 0 r 0 3 0 4 0

J1 S(r) J2

0

m1

m2 m1

4

4+r

7+r

9

Figure 5.10:

Note that the derived schedule of an immediate run is not necessarily non-lazy. The feasible schedule of Figures 5.11 derived from run ξ3 is a lazy schedule, while run ξ3 is an immediate run.

J1 S3 J2

0

m1

m2 m1

4 7 9

12

Figure 5.11: ξ3 : (m1 , m1 , ⊥, ⊥) ?→ (m1 , m1 , 0, ⊥) ?→ (m1 , m1 , 4, ⊥) ?→ (m2 , m1 , ⊥, ⊥) ?→ (m2 , m1 , 0, ⊥) ?→ (m2 , m1 , 5, ⊥) ?→ (f, m1 , ⊥, 0) ?→ (f, m1 , ⊥, 0) ?→ (f, m1 , 3, ⊥) ?→ (f, f, 5, ⊥)

3 0 0 5 0 0 0 4 0

60

5.6. THE SEARCH ALGORITHM

De?nition 16 (Lazy Runs) A lazy run in a job-shop timed automaton A is a run containing a fragment (q, v) . . . ?→ . . . (q , v ) ?→i (q , v ) s.t. the starti transition is enabled in all states (q, v) . . . (q , v ). The immediate run ξ3 is lazy due to the fragment (m2 , m1 , 0, ⊥) ?→ (m2 , m1 , 5, ⊥) ?→ 0 (f, m1 , ⊥, 0) ?→ (f, m1 , ⊥, 0). The start transition for J 2 is taken at (f, m1 ) while it was continuously enabled since (m2 , m1 ). Claim 5 Let S ? be the set of non-lazy schedules of a job shop speci?cation J and let A be its automaton. Let SI and SL be the sets of derived schedules for all the immediate and non-lazy runs of A, respectively, then S ? = SL ? SI . Corollary 6 (Job-Shop Scheduling and Timed Automata) The optimal job-shop scheduling problem can be reduced to the problem of ?nding the shortest non-lazy path in a timed automaton.

5 0 t start

5.6

The Search Algorithm

Based on Corollary 11 we build a search algorithm that explores only the non-lazy runs. For more clarity we start by showing how to generate immediate runs, then reduce even more the search space to obtain the set of non-lazy runs. De?nition 17 (Domination point) Let (q, Z) be a symbolic state in an extended timed automaton. We say that the reachable con?guration (q, v? , t? ) is domination point of (q, Z) if t? = G(q, Z) and for every i, (earliest arrival time)

? vi = max{vi : (v1 , . . . , vi , . . . , vn , t? ) ∈ Z}.

This point is the one reachable via an immediate run. Restricting the search algorithm to these points and their successor makes the algorithm much more e?cient. Instead of working with symbolic state of the form (q, Z) where Z is a zone represented by a DBM of size O(n2 ), and where computing successors is a non-trivial operation, we can work with a point representation of size O(n) where passage of time is a simple vector addition. We de?ne the timed successor Succt (q, v, t) and the discrete successor Succδ (q, v, t) of every con?guration (q, v, t) as follows: Let θ be the maximal amount of time that can elapse in a con?guration (q, v, t) until an end transition becomes enabled, i.e. θ = min{(di ? vi ) : ci is active at q}. The timed successor of a con?guration is the result of letting time progress by θ and terminating all that can terminate by that time: Succt (q1 , . . . , qn , v1 , . . . , vn , t) = {(q1 , . . . , qn , v1 , . . . , vn , t + θ)} 61

5.6. THE SEARCH ALGORITHM

such that for every i (qi , vi ) = if the transition (qi , vi + θ) → (qi , vi ) is enabled (qi , vi ) (qi , vi + θ) otherwise.

The discrete successors are all the successors by immediate start transition: start Succδ (q, v, t) = {(q , v , t) s.t. (q, v, t) ?→ i (q , v , t)} The set of successors of each (q, v, t) is: Succ(q, v, t) = Succt (q, v, t) ∪ Succδ (q, v, t) Using the successor operator in a reachability algorithm for discrete graphs, we can compute all the immediate runs in a timed automaton. Figure 5.12 shows the 5 immediate runs of the automaton of Figure 8.5.

(⊥, ⊥, 0) m1 m1

(0, ⊥, 0) m1 m1

m1 m1

(⊥, 0, 0)

(⊥, ⊥, 4) m2 m1

m1 f

(⊥, ⊥, 3)

(0, ⊥, 4) m2 m1

m2 m1

(⊥, 0, 4)

m1 f

(0, ⊥, 3)

(⊥, ⊥, 9)

f m1

m2 m1

(0, 0, 4)

m2 f

(⊥, ⊥, 7)

(⊥, 0, 9) f m1

m2 f

(3, ⊥, 7)

m2 f

(0, ⊥, 7)

(⊥, ⊥, 12) f f

f f

(⊥, ⊥, 9)

f f

(⊥, ⊥, 12)

Figure 5.12: The immediate runs of the timed automaton of Figure 8.5

To restrict the search further to non-lazy runs, we must eliminates all useless waiting. This can be done as follows. If from a state (q, v) we choose to take the time successor (q, v + θ) while a starti transition associated with a step (i, j) is enabled in (q, v), we mark component i as “freezed” in (q, v + θ) and this marking is propagated to its successors and is removed only after the starti transition was disabled and enabled again (some other job took and then released the machine in question). In every con?guration we restrict the set of successors only to transitions of non-freezed components. Moreover, if the duration of step (i, j) is such that if started at (q, v) 62

5.6. THE SEARCH ALGORITHM

it will terminate before another con?icting transition is enabled, it must be taken and not freezed (this is the case when it is the only remaining step that needs the This successor computation is implemented using annotated con?gurations (q, v, t, F ) where F is a set of freezed components, initialized to the empty set. sors are computed as follows: Succt (q, v, t, F ) = (Succt (q, v, t), F ∪ F1 ? F2 )

immediately machine). of the form The succes-

where F1 is the set of components i s.t. a starti transition is enabled in (q, v, t) and F2 is the set of components i s.t. the transition releases the machine for which i is waiting, and Succδ (q, v, t, F ) = {(q , v , t, F ) : (q, v, t) → (q , v , t)} / where (q, v, t) → (q , v , t) is a starti transition s.t. i ∈ F. If there is a transition enabled at (q, v) which will not block any other job Succ(q, v, t, F ) = Succδ (q, v, t, F ) otherwise Succ(q, v, t, F ) = Succδ (q, v, t, F ) ∪ Succt (q, v, t, F ) Applying these operators in a reachability algorithm, we obtain the set of non-lazy runs. Figure 5.14 shows the 4 non-lazy runs of the automaton of Figure 8.5.

(⊥, ⊥, 0) m1 m1

(0, ⊥, 0) m1 m1

m1 m1

(⊥, 0, 0)

(⊥, ⊥, 4) m2 m1

m1 f

(⊥, ⊥, 3)

(0, ⊥, 4) m2 m1

m2 m1

(⊥, 0, 4)

m1 f

(0, ⊥, 3)

(0, 0, 4) m2 m1

m2 f

(⊥, ⊥, 7)

(3, ⊥, 7) m2 f

m2 f

(0, ⊥, 7)

(⊥, ⊥, 9) f f

f f

(⊥, ⊥, 12)

Figure 5.13: Non-lazy runs of the timed automaton of Figure 8.5

63

5.7. REDUCING THE SEARCH SPACE

5.7

Reducing the Search Space

Although using points instead of zones reduces signi?cantly the computational cost, the inherent combinatorial explosion remains. In this section we describe further methods to reduce the search spaces, some of which preserve the optimal solutions and some provide sub-optimal ones.

5.7.1

Domination Test

The con?gurations (m2 , f, 3, ⊥, 7) and (m2 , f, 0, ⊥, 7) in Figure 5.14 share the same state (m1 , f ) but have di?erent clock values. Both are reached at the same time t = 7 but in (m2 , f, 0, ⊥, 7) the value of c1 is smaller, and hence all the run continuing from it cannot reach f before those continuing from (m2 , f, 3, ⊥, 7). Hence the successors of (m2 , f, 0, ⊥, 7) can be discarded without missing the optimum. De?nition 18 (Domination) Let (q, v, t) and (q, v , t ) be two reachable con?gurations. We say that (q, v, t) dominates (q, v , t ) if t ≤ t and v ≥ v . Clearly if (q, v, t) dominates (q, v , t ) then for every complete run going through (q, v , t ) there is a run which traverses (q, v, t) and which is not longer.

(⊥, ⊥, 0) m1 m1

(0, ⊥, 0) m1 m1

m1 m1

(⊥, 0, 0)

(⊥, ⊥, 4)

m2 m1

m1 f

(⊥, ⊥, 3)

(0, ⊥, 4) m2 m1

m2 m1

(⊥, 0, 4)

m1 f

(0, ⊥, 3)

(0, 0, 4) m2 m1

m2 f

(⊥, ⊥, 7)

(3, ⊥, 7) m2 f

(⊥, ⊥, 9) f f

Figure 5.14:

64

5.8. EXPERIMENTAL RESULTS

5.7.2

Best-?rst Search

In order to apply best-?rst search and explore the “most promising” directions ?rst, we need an evaluation function over con?gurations. For every con?guration (q, v) of a job automaton g(q, v) is a lower-bound on the time remaining until f is reached from the con?guration (q, v): g(f, v) = 0 g(μ(j), v) = k d(l) l=j g(μ(j), v) = g(μ(j), v) ? min{v, d(j)} The evaluation of global con?gurations is de?ned as: E((q1 , . . . , qn ), (v1 , . . . , vn , t)) = t + max{gi (qi , vi )}n i=1 Note that max{gi } gives the most optimistic estimation of the remaining time, assuming that no job will have to wait. The best-?rst search algorithm is guaranteed to produce the optimal path because it stops the exploration only when it is clear that the unexplored states cannot lead to schedules better than those found so far. Algorithm 6 (Best-?rst Forward Reachability) Waiting:={Succ(s, v, t)}; Best:=∞ (q, v, t):= ?rst in Waiting; while Best > E(q, v, t) do For every (q , v, t) ∈ Succ(q, v, t); if q = f then Best:=min{Best,E(q , v, t)} else Insert (q , v , t) into Waiting; Remove (q, v, t) from Waiting (q, v, t):= ?rst in Waiting; end

5.7.3

Sub-Optimal Solutions

The best-?rst algorithm improves performance but the combinatorial explosion remains. To avoid it we use an algorithm which is a mixture of breadth-?rst and best-?rst search with a ?xed number w of explored nodes at any level of the automaton. For every level we take the w best (according to E) states, generate their successors but explore only the best w among them, and so on. The number w is the main parameter of this technique, and although the number of explored states grows monotonically with w, the quality of the solution does not — sometimes the solution found with a smaller w is better than the one found with a larger w.

5.8

Experimental Results

We have implemented a prototype that models the job shop problem in a timed automaton, and generates all the non-lazy runs. Applying the domination test and using a best ?rst search we could solve problems with 6 jobs and 6 machines in few seconds. Beyond that we had to employ the sub-optimal heuristic.

65

5.8. EXPERIMENTAL RESULTS

We tested the heuristic algorithm on 10 problems among the most notorious job-shop scheduling problems. Note that these are pathological problems with a large variability in step durations, constructed to demonstrate the hardness of job-shop scheduling. For each of these problems we have applied our algorithm for di?erent choices of w. In Table 6.4 we compare our best results on these problems with the best results reported in Table 15 of the recent survey [JM99], where the results of the 18 best-known methods were compared. As one can see our results are typically 5 ? 10% from the optimum.

problem name #j #m FT10 10 10 LA02 10 5 LA19 10 10 LA21 10 15 LA24 10 15 LA25 10 15 LA27 10 20 LA29 10 20 LA36 15 15 LA37 15 15

time 3 1 15 98 103 148 300 149 188 214

heuristic length deviation 969 4.09 % 655 0.00 % 869 3.21 % 1091 4.03 % 973 3.95 % 1030 5.42 % 1319 6.80 % 1259 9.29 % 1346 6.15 % 1478 5.80 %

Opt length 930 655 842 1046 936 977 1235 1152 1268 1397

Table 5.1: The results for 10 hard problems using the bounded width heuristic. The ?rst three columns give the problem name, no. of jobs and no. of machines (and steps). Our results (time in seconds, the length of the best schedule found and its deviation from the optimum) appear next, To appreciate the contribution of the fact that we use points instead of zones due to nonlaziness, we can look at he performance of zone-based versions of our algorithms et Table 5.2, where the largest problem that can be solved exactly is of size 6 jobs and 4 machines. Problem size #ds #tree 77 632 629 67298 4929 279146 37225 m.o. 272125 m.o. Inclusion #s time 212 1 5469 2 159994 126 m.o. m.o. m.o. m.o. Domination #s time 100 1 1143 1 11383 2 116975 88 1105981 4791 Best-?rst #s time 38 1 384 1 1561 1 2810 1 32423 6

#j 2 3 4 5 6

Table 5.2: The results for n jobs with 4 tasks. Columns #j, #ds and #tree show, respectively, the number of jobs, the number of discrete states in the automaton and the number of di?erent reachable symbolic states (which is close to the number of nodes in the unfolding of the automaton into a tree). The rest of the table shows the performance, in terms of the number of explored symbolic states and time (in seconds), of algorithms employing, progressively, the inclusion test, the domination test, and the best-?rst search (m.o. indicates memory over?ow).

66

Chapter 6

Preemptive Job Shop Scheduling

In this chapter we extend the results on deterministic Job-shop scheduling problem to preemptible jobs, i.e. jobs that can use a machine for some time, stop for a while and then resume from where they stopped. Such situations are common, for example, when the machines are computers. As an example let M = {m1 , m2 , m3 } be a set of resources and J = {J 1 , J 2 } a job speci?cation over a M where J 1 = (m1 , 3), (m2 , 2), (m3 , 4) and J 2 = (m2 , 5). Two feasible schedules S1 and S2 appear in Figure 6.1. In the schedule S1 the job J 2 is preempted at time t = 3 on the machine m2 to give the machine to the job J 1 . After J 1 has terminated job J 2 restarts on m2 . The length of S1 is 9 and it is the optimal schedule.

S1

J1

S2 m1

J1

m1 α m2 m3

J2

J1

J2

J2

m2

J1

J1

0

3

5

7

9

m3

J1

0 3 5 7

11

J1 β J2

m1

m2

m3

J1 J2

m1

m2

m3

m2

0 3 5

m2

7

m2

0 3 5 7

9

11

Figure 6.1: Two schedule S1 and S2 visualized as the machine allocation function α and the task progress function β.

The de?nition of a job-shop speci?cation (De?nition 1) and of feasible schedule (De?nition 2) remains the same except the relaxation of the non preemption constraint in De?nition 2. this 67

6.1. MODELING WITH STOPWATCH AUTOMATA

means that for every step (i, j) the set {t, (i, j, t) ∈ S} is a union of intervals such that the sum of their lengths is equal to the step duration.

6.1

Modeling with Stopwatch Automata

The timed automaton model proposed in the Chapter 1, is not valid any more because it can not express preemption of a step. A job automaton can leave an execution state only if the step has terminate. To model preemption we need an additional state “preempt” such that the automaton can move back and forth between “execute” and “preempt” as in Figure 6.2. Since only the time spent in “execute” counts, we cannot use the value of c1 as is in the transition guard to termination. One solution is to add an additional clock c2 , measuring the preemption time and updating c1 to be c1 ? c2 each time execution resumes. This operation is beyond the reset operation allowed in timed automata.

start

c1 := 0 c2 := 0

execut

c1 := 0

terminate

c1 := c1 ? c2

c2 := 0

preempt

Figure 6.2:

An alternative and more natural solution is to extend the model of timed automata to have clocks which can be freezed at certain states, in other words clocks with derivative zero. Such automata were called Integration Graphs in [KPSY99] where they were studied as models for the Duration Calculus [CHR91]. The results in [KPSY99] included the undecidability of the reachability problem for these automata, and a decision procedure for some special sub-classes based on reducing the problem into linear constraint satisfaction. Similar automata were also investigated in [MV94] and in [CL00] where an implementation of an approximate veri?cation algorithm was described. De?nition 19 (Stopwatch Automata) A stopwatch automaton is a tuple A = (Q, C, s, f, u, Δ) where Q is a ?nite set of states, C is a ?nite set of n clocks, u : Q → {0, 1}n assigns a constant slope to every state and Δ is a transition relation consisting of elements of the form (q, φ, ρ, q ) where q and q are states, ρ ? C and φ (the transition guard) is a boolean combination of formulae of the form (c ∈ I) for some clock c and some integer-bounded interval I. States s and f are the initial and ?nal states, respectively.

68

6.1. MODELING WITH STOPWATCH AUTOMATA

6.1.1

Modeling Jobs

We construct for every job J = (k, μ, d) a stopwatch automaton with one clock such that for every step j with μ(j) = m there are three states: a waiting state m, an active state m and a state m indicating that the job is preempted after having started. Upon entering m the clock ? is reset to zero, and measures the time spent in m. Preemption and resumption are modeled by transitions to and from state m in which the clock does not progress. When the clock value ? reaches d(j) the automaton can leave m to the next waiting state. Let M = {m : m ∈ M }, ? ? ? M = {m : m ∈ M } and let μ : K → M and μ : K → M be auxiliary functions such that ? μ(j) = m and μ(j) = m whenever μ(j) = m. ? ? De?nition 20 (Stopwatch Automaton for a Job) Let J = (k, μ, d) be a job. Its associated automaton is A = (Q, {c}, u, Δ, s, f ) with Q = ? ? μ ? P ∪ P ∪ P ∪ {f } where P = {μ(1), . . . μ(k)},P = {μ(1), . . . , μ(n)} and P = {?(1), . . . , μ(n)}. The slope is de?ned as uq = 1 when q ∈ P and uq = 0 otherwise. The transition relation Δ consists of the following types of tuples type begin pause resume end end q μ(j) μ(j) μ(j) ? μ(j) μ(k) φ ρ q true {c} μ(j) true ? μ(j) ? true ? μ(j) c = d(j) ? μ(j + 1) c = d(k) ? f

1) 2) 3) 4)

j j j j

= 1..k = 1..k = 1..k = 1..k ? 1

The initial state is μ(1).

69

6.1. MODELING WITH STOPWATCH AUTOMATA

μ(1)

c := 0 c = 0 μ(1) ˙ ?

μ(1)

c=1 ˙

μ(j)

c := 0 c = 0 μ(j) ˙ ?

μ(j)

c=1 ˙

c = d(j)

?(j + 1)

c = 0 μ(k) ˙ ?

μ(k)

c=1 ˙

c = d(k)

f

Figure 6.3: A generic stopwatch automaton for a job

The stopwatch automata corresponding to the two jobs of the Example are depicted in Figure 6.4.

70

6.1. MODELING WITH STOPWATCH AUTOMATA

m1 c1 := 0 c1 = 0 ˙ m1 ? m 1 c1 = 1 ˙ c1 = 3 m2 c1 := 0 c1 = 0 ˙ m2 ? m2 c1 = 1 ˙ c2 = 0 ˙ m2 ? m2 c2 := 0 m2 c2 = 1 ˙

c1 = 2 m3 c1 := 0 c1 = 0 ˙ m3 ? m 3 c1 = 1 ˙ c1 = 4 f f

c2 = 6

Figure 6.4: The automata corresponding to the jobs J 1 = (m1 , 3), (m2 , 2), (m3 , 4) and J 2 = (m2 , 5).

6.1.2

The Global Model

To obtain the stopwatch automaton modeling the preemptive job shop problem we need to compose the automata of the jobs, using the mutual exclusion composition described in the Chapter 1. Part of the automaton obtained by composing the two automata of Figure 6.4 appears in Figure 6.5. We have omitted the preemption/resumption transitions for m1 and m3 as well as some other non-interesting paths. Unlike the non-preemptive job-shop automaton, this automaton is cyclic, due to the possibility to preempt and resume a step at any moment.

71

6.1. MODELING WITH STOPWATCH AUTOMATA

m1 m2 c1 := 0 m1 m2 c2 := 0 m1 m2

m1 m2 c1 = 3 c1 := 0 m2 m2 ? ? m2 m2 ? m2 m2 ? m2 m2 c2 = 5

c1 = 2 m3 m2 ? c1 := 0

m2 f c1 := 0

m3 m2 ?

m3 m2

m2 f c1 = 2

m3 m2 c1 = 4 c2 = 5

m3 f

c1 := 0 f m2 m3 f

c2 = 5 ff

c1 = 4

Figure 6.5: Part of the global stopwatch automaton for the two jobs.

6.1.3

Runs and Schedules

The correspondence between runs and feasible schedules is similar to the non-preemptive problem. Claim 7 Let A be the stopwatch automaton of a preemptive job shop speci?cation J . Every complete run of A corresponds to a feasible schedule with a length equal to the metric length of the run. The two schedules of Figure 6.1 correspond to the following two runs:

72

6.2. EFFICIENT SCHEDULES

ξ1 :

(m1 , m2 , ⊥, ⊥) ?→ (m1 , m2 , 0, ⊥) ?→ (m1 , m2 , 0, 0) ?→ (m1 , m2 , 3, 3) ?→ ? ? ? (m2 , m2 , ⊥, 3) ?→ (m2 , m2 , ⊥, 3) ?→ (m2 , m2 , 0, 3) ?→ (m2 , m2 , 2, 3) ?→ ? (m3 , m2 , ⊥, 3) ?→ (m3 , m2 , ⊥, 3) ?→ (m3 , m2 , 0, 3) ?→ (m3 , m2 , 2, 5) ?→ (m3 , f, 2, ⊥) ?→ (m3 , f, 4, ⊥) ?→ (f, f, ⊥, ⊥) ξ2 :

0 0 3 0 2 0 0 0 2 0 0 0 2 0

0

0

3

0

(m1 , m2 , ⊥, ⊥) ?→ (m1 , m2 , 0, ⊥) ?→ (m1 , m2 , 0, 0) ?→ (m1 , m2 , 3, 3) ?→ (m2 , m2 , ⊥, 3) ?→ (m2 , m2 , ⊥, 5) ?→ (m2 , f, ⊥, ⊥) ?→ (m2 , f, 0, ⊥) ?→ (m2 , f, 2, ⊥) ?→ (m3 , f, ⊥, ⊥) ?→ (m3 , f, 0, ⊥) ?→ (m3 , f, 4, ⊥) ?→ (f, f, ⊥, ⊥) Corollary 8 The optimal preemptive job-shop scheduling problem can be reduced to the problem of ?nding the shortest path in a stopwatch automaton. While trying to ?nd the shortest path in this automaton we encounter two problems: 1. General reachability problems for stopwatch automata are known to be undecidable [C92, KPSY99]. 2. The global stopwatch automaton is cyclic and thus have an in?nite number of qualitative runs. However, we will show, using a well-known result concerning optimal preemptive schedules, that these problems can be overcome.

0 0 4 0 2 0 0 2

6.2

E?cient Schedules

De?nition 21 (Con?icts and Priorities) Let S be a feasible schedule. let Tji be the set of time instants where job i ∈ J is executing its i j th step and Ej = [s(i, j ? 1) + di (j ? 1), s(i, j) + di (j)] i.e. the time interval between the enabling of the step and its termination. We say that job i is in con?ict with job i on machine m in S (denoted by i ?m i ) when there are two respective steps j and j such that μi (j) = μi (j ) = m i i and Ej ∩ Ej = ?. We say that i has priority in S on m over a con?icting job i (denoted by i ?m i ) if it ?nishes using m before i does, i.e. s(i, j) + di (j) < s(i , j ) + di (j ). De?nition 22 (E?cient Schedules) A schedule S is e?cient if for every job i and a step j such that μi (j) = m, job i uses m during i all the time interval Ej except for times when another job i such that i ?m i uses it.

i In other words, e?ciency means that every step (i, j) uses the machine during all Ej except for times when the machine is used by a step which terminates earlier than (i, j).

73

6.2. EFFICIENT SCHEDULES

S3 m1 m2 m3 J1 J1 J2 J1

0 3 5 9

10

S4 m1 m2 m3 J1 J2 J1 J2 J1

0 3 4 6 7

10

S5 m1 m2 m3 J1 J2 J1 J2 J1 J1

0 3 4 5 6 7

11

Figure 6.6: Three ine?cient schedule S3 , S4 and S5 . The interval of ine?ciency are indicated by the dashed lines

The schedules of Figure 6.6 are three feasible schedules of the example. We will see why these three schedules are all ine?cient schedules. According to De?nition 21 we can deduce for each problem the priority relation between the jobs J 1 and J 2 on machine m2 and the time 1 2 intervals E2 and E1 .

1 2 ? S3 : J 1 ?m2 J 2 , E2 = [3, 5], E1 = (0, 10] 1 2 ? S4 : J 1 ?m2 J 2 , E2 = [3, 6], E1 = (0, 7] 1 2 ? S5 : J 2 ?m2 J 1 , E2 = [3, 7], E1 = (0, 6]

In schedule S3 job J 2 can use machine m2 during the time interval [0, 10] while it starts at t = 5 and no other job uses the machine in [0, 3].

74

6.2. EFFICIENT SCHEDULES

J2 J1

In schedule S4 job J 1 can use machine m2 during the time interval [3, 6] while in [3, 4], job occupies the machine while J 1 ?m2 J 2 . In schedule S5 job J 2 can use machine m2 during the time interval [0, 6] while in [3, 4], job occupies the machine while J 2 ?m2 J 1 .

We will show that any problem admits an optimal schedule that corresponds to ?xed priority relation among jobs on machine such that: ? A step of a job executes as soon as it is enabled except for times when it is in con?ict with a higher priority job. ? Preemption occurs only when a step which has higher priority than an executing step becomes enabled. Hence the number of preemptions is ?nite. Theorem 9 (E?ciency is Good) Every preemptive job-shop speci?cation admits an e?cient optimal schedule. Proof: The proof is by showing that every ine?cient schedule S can be transformed into an e?cient schedule S with |S | ≤ |S|. Let I be the ?rst interval when ine?ciency occurs for job J i and machine m. We modify the schedule by shifting some of the later use of m by J i into I. If m was occupied during I by another job J i such that J i ?m J i , we give it the time slot liberated by J i . The termination of the step by J i is not delayed by this modi?cation because it happens anyway after J i terminates its step. As an illustration consider the schedules appearing in Figure 6.7 with J 1 ?m J 2 ?m J 3 and where J 2 is enabled in the interval [t1 , t2 ]. The ?rst ine?ciency in S1 is eliminated in S2 by letting J 2 use the free time slot before the arrival of J 1 . The second ine?ciency occurs when J 3 uses the machine while J 2 is waiting, and it is removed in S3 . The last ine?ciency where J 3 is waiting while m is idle is removed in S4 .

J1 S1 J2 J1 S2 J2 J1 S3 J2 J1 J2 S4

t1 t2

J3

J2

J3

J3 J2

J2 J3 J3

J3 J3

Figure 6.7: Removal of ine?ciency, J 1 ? J 2 ? J 3 . This result reduces the set of candidates for optimality from the non-countable set of feasible schedules to the ?nite set of e?cient schedules, each of which corresponds to a ?xed priority relation. There are potentially kn! priority relations but only a fraction of those needs to be considered because when i and i are never in con?ict concerning m, the priority i ?m i has no in?uence on the schedule. 75

6.3. SEARCHING FOR EFFICIENT RUNS

6.3

Searching for E?cient Runs

In order to ?nd shortest paths in stopwatch automata we will take advantage of Theorem 9 to restrict the search to runs whose corresponding schedules are e?cient. De?nition 23 (E?cient Runs) A run of a stopwatch automaton is e?cient if all discrete transitions are taken as soon as they are enabled, and all con?icts are resolved according to a ?xed priority relation. An e?cient run allow us : 1. To restrict the search only to immediate runs. 2. To restrict the number of qualitative paths to be ?nite by avoiding loops and other useless preemptions and resumption. To be more precise, let J 1 and J 2 be two jobs which are in con?ict concerning machine m and let J 1 be the one with the highest priority on m. Table 6.3 depicts all the potential con?ict situations and how they are resolved. state (m, m) (m, m) ? (m, m) (m, m) ? (m, m) ? ? (m, m) ? (m, m) (m, m) ? (m, m) action start 1 start 1 preempt 2 resume 1 resume 1 (continue) (continue) new state (m, m) (m, m) ? (m, m) ? (m, m) (m, m) ? (m, m) (m, m) ? (impossible) J 2. remark

1 2 3 4 5 6 7 8 9

(impossible)

Table 6.1: Resolving con?icts when J 1

m

In situations 1, 2, 4, and 5 J 1 is waiting for the machine which is not occupied and so it takes it. Such situations could have been reached, for example, by a third job of higher priority releasing m or by J 1 ?nishing its prior step and entering m. Situation 3 is similar but with J 2 occupying m and hence has to be preempted to reach situation 2. Situation 6, where J 1 is preempted and J 1 is executing, contradicts the priority and is not reachable. In situations 7 and 8, J 1 is executing and no preemption action is taken. Finally situation 9 violates mutual exclusion. Claim 10 Let A be the stopwatch automaton of a preemptive job shop speci?cation J . Every complete e?cient run of A corresponds to a feasible e?cient schedule with a length equal to the metric length of the run. Corollary 11 (Preemptive Scheduling and Stopwatch Automata) The optimal preemptive job-shop scheduling problem can be reduced to the problem of ?nding the shortest e?cient run in a stopwatch automaton.

76

6.3. SEARCHING FOR EFFICIENT RUNS

The restriction to e?cient runs makes the shortest path problem decidable: we can enumerate all the priority relation, and for each of them check the length of the induced e?cient run. As in the non-preemptive case, the search algorithm that we employ on the unfolding of the automaton generates priorities on the ?y whenever two jobs come into con?ict. In the example of Figure 6.5 the ?rst con?ict is encountered in state (m2 , m2 ) and from there we may choose between two options, either to continue with time passage or preempt J 2 . In the ?rst case we ?x the priority J 2 ?m2 J 1 and let J 2 ?nish without considering preemption anymore while in the ? second case the priority is J 1 ?m2 J 2 , we move to (m2 , m2 ) and the transition back to (m2 , m2 ) becomes forbidden. From there we can only continue to (m2 , m2 ) and let the time pass until J 1 ? releases m2 . To formalize this we de?ne a valid successors relation over tuples of the form (q, v, t, Π) where (q, v, t) is a global con?guration of the extended automaton and Π is a (partial) priority relation. When there are no start transitions enabled in (q, v, t) we have Succ(q, v, t, Π) = {(Succt (q, v, t), Π)} where Succt (q, v, t) is the timed successor as de?ned for the non-preemptive case. When there are start transitions enabled in (q, v, t) we have Succ(q, x, Π, θ) = L1 ∪ L2 ∪ L3 where L1 = {(q , x , Π, θ) : (q, x) ?→ (q , x )} for every immediate transition δ such that δ is non-con?icting or belongs to the job whose priority on the respective machine is higher than those of all competing jobs. In addition, if there is a con?ict on m involving a new job i whose priority compared to job i? , having the highest priority so far, has not yet been determined, we have L2 = {(q, x, Π ∪ {i? ? i}, θ)} and L3 = {(q, x, Π ∪

{i :i ?m i} δ

{i ? i }, θ)}.

The successor in L2 represent the choice to prefer i? over i (the priority of i relative to other waiting or preempted jobs will be determined only after i? terminates), while L3 represents the choice of preferring i over all other jobs. The search tree generated by our algorithm for the example appears in Figure 6.8.

77

6.4. EXPERIMENTAL RESULTS

(⊥, ⊥, 0) m1 m2

(0, ⊥, 0) m1 m2

(0, 0, 0)

m1 m2

(⊥, 3, 3) m2 m2

(⊥, 3, 3) m2 m2 ?

m2 f

(⊥, ⊥, 5)

(0, 3, 3)

m2 m2 ?

m2 f

(0, ⊥, 5)

? (⊥, 3, 5) m3 m2

m3 f (⊥, ⊥, 7)

(0, 3, 5)

m3 m2 ?

m3 f

(0, ⊥, 7)

(0, 3, 5)

m3 m2

f f

(⊥, ⊥, 11)

(2, ⊥, 7)

m3 f

(⊥, ⊥, 9)

f f

Figure 6.8: The e?cient runs of the timed automaton of Figure 6.5

6.4

Experimental Results

With a best-?rst algorithm we were able the ?nd optimal schedules of system with up to 8 jobs and 4 machines (128 discrete states and 8 clocks). We test the same heuristic proposed in the case of deterministic job shop problem on 16 di?cult job-shop scheduling problems, for each of these problems we have applied our algorithms for di?erent choices of w (it takes, on the average few minutes for each problem). In Table 6.4 we compare our best results on these problems to the most recent results reported by Le Pape and Baptiste [PB96, PB97] where the problem was solved using state-of-the-art constraint satisfaction techniques. 78

6.4. EXPERIMENTAL RESULTS

problem name #j LA02 10 FT10 10 ABZ5 10 ABZ6 10 ORB1 10 ORB2 10 ORB3 10 ORB4 10 ORB5 10 LA19 10 LA20 10 LA21 10 LA24 10 LA27 10 LA37 15 LA39 15

#m 5 10 10 10 10 10 10 10 10 10 15 15 15 20 15 15

non preempt optimum 655 930 1234 943 1059 888 1005 1005 887 842 902 1046 936 1235 1397 1233

optimum 655 900 1203 924 1035 864 973 980 849 812 871 1033 909 1235 1397 1221

preemptive [PB96, PB97] stopwatch 655 655 900 911 1206 1250 924 936 1035 1093 864 884 994 1013 980 1004 849 887 812 843 871 904 1033 1086 915 972 1235 1312 1397 1466 1221 1283

deviation 0.00 % 1.21 % 3.76 % 1.28 % 5.31 % 2.26 % 3.95 % 2.39 % 4.28 % 3.68 % 3.65 % 4.88 % 6.48 % 5.87 % 4.71 % 4.83 %

Table 6.2: The results of our implementation on the benchmarks. Columns #j and #m indicated the number of jobs and machines, followed by the best known results for non-preemptive scheduling, the known optimum for the preemptive case, the results of Le Pape and Baptiste, followed by our results and their deviation from the optimum.

79

Chapter 7

Task Graph Scheduling

In this chapter we apply the methodology suggested for the job shop problem to a di?erent problem, task graph scheduling on parallel identical machines. In this problem we have a ?xed number of parallel and identical machines on which we have to execute a set of tasks linked by a set of precedence constraints represented by a task graph as in Figure 7.1. A task can be executed only if all its predecessors in this graph have completed. The job shop problem is a particular case where this graph is a set of linear chains, each chain representing the precedence relation in one job.

16

P2

P1

2

2

P6

6

P3

P4

16

2

P7

P5

8

Figure 7.1: A task graph. The numbers represent task durations

Contrary to the job shop problem, a task can be executed on any idle machine and every pair of tasks can be a-priori in con?ict two tasks can thus be in con?ict on any machine. The signi?cant parameter in this problem is not any more the identity of the occupied machines but the number of occupied machines.

7.1

The Problem

A task graph is a triple G = (P, ?, d) such that P = {P1 , . . . , Pm } is a set of m tasks, ? is a partial-order relation on P and d : P → N is a function which assigns a duration to each task. 81

7.1. THE PROBLEM

We denote by Π(P ) the set of immediate predecessors of P . Given a set {M1 , . . . , Mn } of n parallel identical machines, we need to ?nd the schedule that minimizes the total execution time and respects the following conditions: ? A task can be executed only if all its predecessors have completed. ? Each machine can process at most one task at a time. ? Tasks cannot be preempted. If we have as many machines as we want, the optimal schedule is obtained by starting every task as soon as its predecessors terminate. In that case the length of the optimal schedule is the length of the maximal path from a minimal to a maximal element of (P, ?. The schedule of Figure 7.2 is an optimal schedule for the task graph of Figure 7.1 when the number of machines is unlimited. Notice that 3 machines are su?cient to construct this schedule, because no more than 3 tasks are enabled simultaneously, see Figure 7.3.

P7 P6 P5 P4 P3 P2 P1

0 2 8 16 18 20

26

Figure 7.2: An optimal schedule of the task graph of Figure 7.1 when the number of machine is unlimited.

M1 M2 M3 P1

0 2

P3 P2 P4

8 16 18 20

P6P7 P5

26

Figure 7.3: An optimal schedule of the task graph of Figure 7.1 using 3 machines.

On the other hand, if we have only 2 machines the number of enabled tasks may exceed the number of machines. We can see in schedules S1 and S2 of Figure 7.4 that at t = 2, P2 is already 82

7.2. MODELING WITH TIMED AUTOMATA

occupying M1 where both P3 and P4 become enabled. In S1 we give the remaining machine to P3 , and in S2 we give it to P4 .

M1 S1 M2 P1

0 2

P2 P3

8

P6 P7 P4

16 18 20 24

P5

32

S2

M1 M2 P1

0 2

P2 P4

P3 P6 P7

P5

16 18 20 22 24

30

M1 S3 M2 P1

0 2

P3 P4

8

P2 P5

18

P6 P7

24 26

28

Figure 7.4: Three feasible schedules of the task graph of Figure 7.1 on 2 machines.

Unlike the case of in?nitely many machine and similarly to the job-shop problem, an optimal schedule may be obtained by not executing a task as soon as it is enabled. For example, schedule S3 achieves the optimum while not starting task P2 as soon as possible.

7.2

Modeling with Timed Automata

Our goal is to translate this problem into a timed automaton such that every run corresponds to a feasible schedule and the shortest run gives the optimal schedule. For every task P we build a 3-state automaton with one clock c and a set of states Q = {p, p, p} where p is the waiting state before the task starts, p is the active state where the task executes and p is a ?nal state indicating that the task has terminated. The transition from p to p resets the clock and can be taken only if all the tasks in Π(P ) are in their ?nal states. The transition from p to p is taken when c = d(p). The automata for the task graph of Figure 7.1 appear in Figure 7.5. In order to model task graph as composition of timed automata we need to modify a bit the de?nition of the transition relation Δ to include tuples of the form (q, φ, ρ, q ) where φ is either, as before, a combination of clock inequalities, or a formula specifying states of other automata. De?nition 24 (Timed Automaton for a Task) Let G = (P, ?, d) be a task graph. For every task P ∈ P its associated timed automaton is A = (Q, {c}, Δ, s, f ) with Q = {p, p, p} where the initial state is p and the ?nal state is p. The

83

7.2. MODELING WITH TIMED AUTOMATA

transition relation Δ consists of the two transitions: (p,

P ∈Π(P )

p , {c}, p)

and (p, c = d(p), ?, p)

p1

c1 := 0

p2

c2 := 0

p3

p1 /c3 := 0

p4

p1 /c4 := 0

p5

p6

p7

p3 ∧ p4 /c5 := 0 p1 ∧ p2 /c6 := 0 p3 ∧ p6 /c7 := 0

p1

c1 = 2

p2

c2 = 16

p3

c3 = 6

p4

c4 = 16

p5

c5 = 8

p6

c6 = 2

p7

c7 = 2

p1

p2

p3

p4

p5

p6

p7

Figure 7.5: The automata for the task graph of Figure 7.1

As for the job shop problem, the global automaton representing all the feasible schedules can be obtained as a composition of the individual task automata, a composition that takes care that the number of tasks active in any global state does not exceed the number of machines. Although in terms of the number of reachable global states this automaton is as good as we can get, it has some features which make its analysis impractical and which can be improved. The global states are m-tuples where m can be very large and the number of clocks is m as well. In reality, however, even in the presence of in?nitely many machines, the number of tasks that can be active simultaneously is bounded by the width of the task graph, the maximal number of elements incomparable with respect to ?. De?nition 25 (Chain) A chain in a partially-ordered set (P, ?) is a subset P of P such that for every P, P ∈ P either P ? P or P ? P . De?nition 26 (Chain Cover) A chain covering of a partially-ordered set (P, ?) is a set of chains H = {H1 , . . . Hk } satisfying 1. Each Hi is a linearly ordered subset of P . 2. Hi ∩ Hj = ? for every i = j. 3.

i≤k

Hi = P

An example of a chain cover for our task graph appears in Figure 7.6. The structure of a chain is similar to that of a job except for the fact that tasks in one chain might depend also on the termination of tasks in other chains.

84

7.2. MODELING WITH TIMED AUTOMATA

The external predecessors of a task P ∈ Hi are Π (P ) = Π(P ) ∩ (P ? Hi ). The start transition from p to p is then enabled if for every P ∈ Π(P ) ∪ Hj , the automaton for P is in a state beyond p . We denote this condition by: >p.

P ∈Π (P )

From here we can apply the methodology developed in Chapter 5, built an automaton for every chain (Figure 7.7, compose the chain automata and apply the same search algorithms. It is worth mentioning that chain covers are related to the width of a partial order via Dilworth’s theorem [D50]. Theorem 12 (Dilworth) The width of a partial order is equal to the minimal number of chains needed to cover it. Although the computation of the width and its associated cover is polynomial, we do not compute it exactly but use a fast and simple algorithm to approximate it.

P2

P1

P6

P3

P4

P7

P5

Figure 7.6: A chain covering of the task graph of Figure 7.1

85

7.2. MODELING WITH TIMED AUTOMATA

p2 c1 := 0 p2 c1 = 16 p6 > p1 /c1 := 0 p6 c1 = 2 p7 > p3 /c1 := 0 p7 c1 = 2 f

p1 c2 := 0 p1 c2 = 2 p3 c2 := 0 p3 c2 = 6 p5 > p4 /c2 := 0 p5 c2 = 8 f

p4 > p1 /c3 := 0 p4 c3 = 16 f

Figure 7.7: The automata for the chain cover of Figure 7.6

The timed automaton of Figure 7.8 represents a part of the timed automaton obtained by composing the automata of Figure 7.6 when there are 2 machines. This automaton has only 3 clocks (the number of chains in the cover). In the initial state, where tasks P2 , P1 and P4 are waiting, there are only two possible successors, to start P2 (state (p2 p1 p4 )) or to start P1 (state (p2 p1 p4 )). The transition to the state (p2 p1 p4 ) is disabled because task P1 has not terminated. No start transition can be taken from (p2 , p3 , p4 ) because all the machines are occupied in this state.

86

7.2. MODELING WITH TIMED AUTOMATA

p2 p1 p4 c1 := 0 p2 p1 p4 c1 = 16 p6 p1 p4 c2 := 0 c1 = 16 p6 p1 p4 c2 = 2 c2 := 0 p2 p1 p4 c2 = 2 p2 p3 p4 c1 := 0 c2 := 0 p2 p1 p4 c1 := 0 c2 = 2 p2 p3 p4 c2 := 0 c3 := 0

c1 = 16 c2 := 0 p2 p3 p4

p2 p3 p4 p2 p3 p4 c1 := 0 c3 := 0 c2 = 6 c3 := 0 c2 := 0 c3 = 16 c1 := 0 p2 p3 p4 c3 = 16 c1 := 0 p2 p5 p4 p2 p3 p4 p2 p3 f c2 := 0

p6 p3 p4

c1 = 16 c2 = 6 c1 := 0 c2 := 0 c1 = 16 c3 := 0 p6 p3 p4 p6 p3 p4 p6 p3 p4

c3 := 0 c2 = 6 c3 = 16 c1 := 0 p2 p3 f p2 p5 p4 c1 := 0 p2 p5 p4 c3 = 16 p2 p5 f c2 := 0 p2 p5 f c1 = 16 p6 p5 f c1 := 0 p6 p5 f c1 = 2 p7 p5 f c2 = 8 p7 f f c1 := 0 p7 f f c1 = 2

p2 p5 p4

p2 p3 f c3 = 16 p2 p5 f

c1 := 0 c2 := 0 c3 = 16 p6 p3 p4 p6 p3 p4 c3 = 16 p6 p3 f c1 := 0 p6 p3 f c1 = 2 p7 p3 f c2 = 6 p7 p5 f c1 := 0 p7 p5 f c2 := 0 p7 p5 f c1 = 2 f p5 f c2 = 8 p6 p3 f

f f f

Figure 7.8: The timed automaton obtained by composing the automata of Figure 7.7 for the case of 2 machines. The two runs corresponding to the schedules S2 and S3 are indicated by the 87 dashed and dotted lines, respectively.

7.3. ADDING DEADLINES AND RELEASE TIMES

7.3

Adding Deadlines and Release Times

Our model can be extended to include two additional feature that are often present in task graph scheduling problems ,deadlines and release times. For every task Pj a deadline λ(j) indicates that the task must imperatively terminate before time t = λ(j). The release time r(j) indicates that the task can not be executed before time t = r(j). A feasible schedule S must respect thus two new constraints: ? ?Pj ∈ P s(Pj ) + d(j) ≤ λ(j). ? ?Pj ∈ P s(Pj ) ≥ r(j). These features can be easily integrated into the model by making reference to the additional clock t measuring absolute time, as can be seen in Figure 7.9. This way a complete run corresponds to a feasible schedule respecting the additional constraints (a run fragment violating a deadline cannot be completed). The results concerning non-lazy schedules hold in this setting as well. It is worth mentioning that these results do not hold if we add relative deadline constraints of the form s(P ) ? s(P ) ≤ λ.

p t≥r ∧

P ∈Π(P )

> p /c := 0

p c=d ∧ t≤λ p

Figure 7.9: An automaton for a task with release time and deadline.

7.4

Experimental Results

To test our approach we have taken several benchmark problems from [YI99] having up to few thousands of tasks. For each of them we have applied a simple algorithm for ?nding a chain cover, built the automata and applied the heuristic sub-optimal shortest path algorithm. The execution time of the algorithm was around 1 minute for a problem and the results very close to the best known results as reported in Table 7.4.

88

7.4. EXPERIMENTAL RESULTS

name 001 000 018 074 021 228 071 271 237 231 235 233 294 295 292 298

#tasks 437 452 730 1007 1145 1187 1193 1348 1566 1664 1782 1980 2014 2168 2333 2399

#cchains 125 43 175 66 88 293 124 127 152 101 218 207 141 965 318 303

# machines 4 20 10 12 20 8 20 12 12 16 16 19 17 18 3 10

[YI99] 1178 537 700 891 605 1570 629 1163 1340 t.o t.o 1118 1257 1318 8009 2471

TA 1182 537 704 894 612 1574 634 1164 1342 1137 1150 1121 1261 1322 8009 2473

Table 7.1: Computation of optimal schedules for benchmark problems. Our results appear in the TA column

89

Chapter 8

Scheduling Under Uncertainty

All models presented in the previous chapters were deterministic in the sense that all tasks and their durations are known in advance to the scheduler. The only non-determinism in the problem speci?cation comes from the scheduler’s decisions and once they are chosen, the system exhibits a unique run/schedule with pre-determined start times for each task. In this chapter we extend our framework to treat the more challenging problem of scheduling under uncertainty. Among the many ways to introduce uncertainty to the model, we have chosen one of the most natural ones, namely uncertainty in the duration of tasks.

8.1

The Problem

We work on a variation of the job-shop scheduling problem where the duration of each task, instead of being given, is only known to be inside an interval of the form [l, u]. It is the external environment that chooses each time number d ∈ [l, u] for every task. An assignment of a number to each uncertainty interval is called an instance1 of the environment. As a running example consider two jobs J 1 = (m1 , 10) ? (m3 , [2, 4]) ? (m4 , 5) J 2 = (m2 , [2, 8]) ? (m3 , 7)

The uncertainties concern the durations of the ?rst task of J 2 and the second task in J 1 . Hence an instance is a pair d = (d1 , d2 ) ∈ [2, 8] × [2, 4]. In this example the only resource under con?ict is m3 and the order of its usage is the only decision the scheduler needs to take. Each instance de?nes a deterministic scheduling problem, Figure 8.1 depicts optimal schedules for instances (8, 4), (8, 2) and (4, 4). Of course, such an optimal schedule can only be generated by a clairvoyant scheduler which knows the instance in advance.

1

Or realization.

91

8.1. THE PROBLEM

m1 J1 d = (8, 4) J2 m2

m3

m4

m3

21 m1 J1 d = (8, 2) J2 19 m1 J1 d = (4, 4) J2 20 m2 m3 m3 m4 m2 m3 m3 m4

Figure 8.1: Optimal schedules for three instances. For the ?rst two the optimum is obtained with J 1 ? J 2 on m3 while for the third — with J 2 ? J 1 . If worst-case Performance is all that we care about we can do the following: ?nd an optimal schedule for the worst instance, extract the start time for each task and stick to the schedule regardless of the actual instance. The behavior of a static schedule based on instance (8, 4) is depicted in Figure 8.2, and one can see that it is rather wasteful for other instances. Intuitively we will prefer a smarter adaptive scheduler that reacts to the evolution of the environment and uses additional information revealed during the execution of the schedule. This is the essential di?erence between a schedule (a plan, a feed-forward controller) and a scheduling strategy (a reactive plan, a feedback controller). The latter is a mechanism that observes the state of the system (which tasks have terminated, which are executing) and decides accordingly what to do. In the former, since there is no uncertainty the scheduler knows exactly what will be the state at every time instant, so the strategy can be reduced to a simple assignment of start times to tasks.

92

8.2. THE HOLE-FILLING STRATEGY

m1 J1 d = (8, 4) J2 m2

m3

m4

m3

21 m1 J1 d = (8, 2) J2 19 m1 J1 d = (4, 4) J2 21 m2 m3 m3 m4 m2 m3 m3 m4

Figure 8.2: A static schedule based on the worst instance (8, 4). It gives the same length for all instances.

8.2

The Hole-Filling Strategy

One of the simplest ways to be adaptive is the following. First we choose a nominal instance d and ?nd a schedule S which is optimal for that instance. Rather than taking S “literally”, we extract from it only the qualitative information, namely the order in which con?icting tasks utilize each resource. In our example the optimal schedule for the worst instance (8, 4) is associated with the ordering J 1 ? J 2 on m3 . Then, during execution, we start every task as soon as its predecessors have terminated, provided that the ordering is not violated. As Figure 8.3 shows, such a strategy is better for instances such as (8, 2). It takes advantage on the earlier termination of the second task of J 1 and “shifts forward” the start times of the two tasks that follow. On the other hand, instance (4, 4) cannot bene?t from the early termination of m2 , because shifting m3 of J 2 forward will violate the J 1 ? J 2 ordering on m3 .

93

8.3. ADAPTIVE SCHEDULING

m1 J1 d = (8, 4) J2 m1 J1 d = (8, 2) J2 m2 m2

m3

m4

m3

m3

m4

21

m3

19 m1 J1 d = (4, 4) J2 21 m2 m3 m3 m4

Figure 8.3: The behavior of a hole ?lling strategy based on instance (8, 4).

Note that this “hole-?lling” strategy is not restricted to the worst-case. One can use any nominal instance and then shift tasks forward or backward as needed while maintaining the order. On the other hand, a static schedule can only be based on the worst-case (a static schedule based on another nominal instance may assume a resource available at some time point, while in reality it will be occupied). While the hole ?lling strategy can be shown to be optimal for all those instances whose optimal schedule has the same ordering as that of the nominal instance, it is not good for instances such as (4, 4), where a more radical form of adaptiveness is required. If we look at the optimal schedules for (8, 4) and (4, 4) in Figure 8.1, we see that the decision whether or not to execute the second task of J 2 is done in both cases in the same qualitative state, namely m1 is executing and m2 has terminated. The only di?erence is in the time elapsed in the execution of m1 at the decision point. Hence an adaptive scheduler should base its decisions also on such quantitative information which, in the case of timed automata models, is represented by clock values.

8.3

Adaptive Scheduling

Consider the following approach: initially we ?nd an optimal schedule for some nominal instance. During the execution, whenever a task terminates (before or after the time we assumed it will) we reschedule the “residual” problem, assuming nominal values for the tasks that have not yet terminated. In our example, we ?rst build an optimal schedule for (8, 4). If task m2 in J 2 terminated after 4 time we have the residual problem J1 = (m1 , 6, !) ? (m3 , 4) ? (m4 , 5) J2 = (m3 , 7)

where the ! indicates that m1 must be scheduled immediately (we assume no preemption). For this problem the optimal solution will be to start m3 of J 2 . Likewise if m2 terminates at 8 we have J2 = (m3 , 7) J1 = (m1 , 2, !) ? (m3 , 4) ? (m4 , 5) 94

8.3. ADAPTIVE SCHEDULING

and the optimal schedule consists of waiting for the termination of m1 and then starting m3 of J 1 . The property of the schedules obtained this way, is that at any moment in the execution they are optimal with respect to the nominal assumption concerning the future.2 This approach involves a lot of online computation, namely solving a new scheduling problem each time a task terminates. The alternative approach that we propose in this chapter is based on expressing the scheduling problem using timed automata and synthesizing a control strategy o?-line. In this framework [AMPS98, AM99, AGP99] a strategy is a function from states and clock valuations to controller actions (in this case, starting tasks). After computing such a strategy and representing it properly, the execution of the schedule may proceed while keeping track of the state of the corresponding automaton. Whenever a task terminates, the optimal action is quickly computed from the strategy look-up table and the results are identical to those obtained via online re-scheduling. We will use notations similar to the partial-order precedence used in Chapter 7 although our examples consist of linearly ordered jobs. De?nition 27 (Uncertain Job-Shop Speci?cation) An uncertain job-shop speci?cation is J = (P, M, ?, μ, D, U ) where P is a ?nite number of tasks, M is a ?nite set of machines, ? is a partial-order precedence relation on tasks, μ : P → M assigns tasks to machines, D : P → N × N assigns an integer-bounded interval to each task and U is a subset of immediate tasks consisting of some ?-minimal elements. The set U is typically empty in the initial de?nition of the problem and we need it to de?ne residual problems. We use Dl and Du to denote the projection of D on the lower- and upperbounds of the interval, respectively. The set Π(p) = {p : p ? p} denotes all the predecessors of p, namely the tasks that need to terminate before p starts. In the standard job-shop scheduling problem, ? decomposes into a disjoint union of chains (linear orders) called jobs. An instance of the environment is any function d : P → R+ , such that d(p) ∈ D(p) for every p ∈ P . The set of instances admits a natural partial-order relation: d ≤ d if d(p) ≤ d (p) for every p ∈ P . Any environment instance induces naturally a deterministic instance of J , denoted by J (d), which is a classical job-shop scheduling problem. The worst-case is de?ned by the maximal instance d(p) = Du (p) for every p. De?nition 28 (Schedule) Let J = (P, M, ?, μ, D, U ) be an uncertain job-shop speci?cation and let J (d) be a deterministic instance. A feasible schedule for J (d) is a function s : P → R+ , where s(p) de?nes the start time of task p, satisfying: 1. Precedence: For every p, s(p) ≥ maxp ∈Π(p) (s(p ) + d(p )). 2. Mutual exclusion: For every p, p such that μ(p) = μ(p ) [s(p), s(p) + d(p)] ∩ [s(p ), s(p ) + d(p )] = ?. 3. Immediacy: For every p ∈ U , s(p) = 0. In order to be adaptive we need a scheduling strategy, i.e. a rule that may induce a di?erent schedule for every d. However, this de?nition is not simple because we need to restrict ourselves to causal strategies, strategies that can base their decisions only on information available at the time they are made. In our case, the value of d(p) is revealed only when p terminates.

A similar idea is used in model-predictive control where at each time actions at the current “real” state are re-optimized while assuming some “nominal” prediction of the future.

2

95

8.4. MODELING WITH TIMED AUTOMATA

De?nition 29 (State of Schedule) A state of a schedule is S = (P f , P a , c, P e ) such that P f is a downward-closed subset of (P, ?) indicating the tasks that have terminated, P a is a set of active tasks currently being executed, c : P a → R+ is a function such that c(p) indicates the time elapsed since the activation of p and P e is the set of enabled tasks consisting of those whose predecessors are in P f . The set of all possible states is denoted by S. De?nition 30 (Scheduling Strategy) A (state-based) scheduling strategy is a function σ : S → P ∪ {⊥} such that for every S = (P f , P a , c, P e ), σ(S) = p ∈ (P e ∪ {⊥}) and for every p ∈ P a , μ(p) = μ(p ). In other words the strategy decides at each state whether to do nothing and let time pass (⊥) or to choose an enabled task, not being in con?ict with any active task, and start executing it. An operational de?nition of the interaction between a strategy and an instance will be given later using timed automata, but intuitively one can see that the evolution of the state of a schedule consists of two types of transitions: uncontrolled transitions where an active task p terminates after d(p) time and moves from P a to P f , leading possibly to adding new tasks to P e , and a decision of the scheduler to start an enabled task. The combination of a strategy and an instance yields a unique schedule s(d, σ) and we say that a state is (d, σ)-reachable if it occurs in s(d, σ). Next we formalize the notion of a residual problem, namely a speci?cation of what remains to be done in an intermediate state of the execution. De?nition 31 (Residual Problem) Let J = (P, M, ?, μ, D, U ) and let S = (P f , P a , c, P e ) be a state. The residual problem starting from S is JS = (P ? P f , M, ? , μ , D , P a ) where ? and μ are, respectively, the restrictions of ? and μ, to P ? P f and D is constructed from D by letting . D(p) ? c(p) if p ∈ P a D (p) = D(p) otherwise De?nition 32 (d-Future-Optimal Strategies) Let d be an instance. A strategy σ is d-future optimal if for every instance d and from every (σ, d)-reachable state S, it produces the optimal schedule for JS (d). This is exactly the property of the online re-scheduling approach described informally in the previous section.

8.4

Modeling with Timed Automata

For each task we construct a timed automaton AD that captures all instances of the task: this automaton can stay in an active state p as long as c ≤ u and can leave p as soon as as c ≥ l. It represents the possible behaviors of the task in isolation, i.e. ignoring precedence and resource constraints. The transition from a waiting state p to p is triggered by a decision of the scheduler, while the time of the transition from p to p depends on the instance. For a given instance d we have the automaton Ad of Figure 8.4-(b) where this transition happens after exactly d time. The automaton AD,d of Figure 8.4-(c) will be used later for computing d-future optimal strategies: it can terminate as soon as c ≥ d but can stay in p until c = u.

96

8.4. MODELING WITH TIMED AUTOMATA

p Start /c := 0

p Start /c := 0

p Start /c := 0

p c≤u End c≥l

p c≤d End c≥d

p c≤u End c≥d

p

p

p

AD

Ad

AD,d

Figure 8.4: (a) The generic automaton AD for a task p such that D(p) = [l, u]. (b) The automaton Ad for a deterministic instance d. (c) The automaton AD,d for computing d-future optimal strategies. Staying conditions for p and p are true and omitted from the ?gure.

The timed automaton for the whole job-shop speci?cation corresponding to the example appears in Figure 8.5. The automaton can be viewed as specifying a game between the scheduler and the environment. The environment can decide whether or not to take an “end” transition and terminate an active task and the scheduler can decide whether or not to take some enabled “start” transition. A strategy is a function that maps any con?guration of the automaton either into one of its transition successors or to the waiting “action”. For example, at (m1 , m3 ) there is a choice between moving to (m1 , m3 ) by giving m3 to J 2 or waiting until J 1 terminates m1 and letting the environment take the automaton to (m3 , m3 ), from where the con?ict concerning m3 can be resolved in either of the two possible ways. A strategy is d-future optimal if from every con?guration reachable in AD,d it gives the shortest path to the ?nal state. In the next section we use a simpli?ed form of the de?nitions and the algorithm of [AM99] to ?nd such strategies.

97

8.4. MODELING WITH TIMED AUTOMATA

c2 := 0

m2 m2

c2 ≤ 8

c2 ≥ 4 m3 c2 ≥ 2 m1 m2

c2 ≤ 8

c2 := 0 m3

c2 = 7 f

c2 := 0 m1 c1 := 0 m1 m2 c1 := 0

c2 := 0 m1 m3 m1 m3 c1 := 0 c2 := 0 m1 m3 m1 m3

c2 = 7 m1 f c1 := 0 c2 = 7 m1 f c1 = 10 c2 = 7 m3 m3 m3 f c1 := 0

c1 := 0 c2 := 0

c1 := 0 c2 ≥ 2

m1 c1 = 10

m1 m2

m1 m2

c2 ≤ 8

c1 = 10 m3 m2

c1 = 10 c2 := 0 m3 m2

c2 ≤ 8

c1 = 10 c2 ≥ 2 m3 m3

c1 = 10 c2 := 0

m3 c1 := 0

c1 := 0

c1 := 0 c2 := 0 m3 m2

c2 ≤ 8

c1 := 0 c2 ≥ 2 m3 m3

m3 c1 = 4

m3 m2

m3 f c1 = 4 c2 := 0 c2 = 7 m4 m3 m4 f c1 := 0 c2 = 7 m4 m3 m4 f c1 = 5 c2 = 7 f m3 ff

c1 = 4

c1 = 4 c2 := 0

c1 = 4 c2 ≥ 2

m4 c1 := 0

m4 m2

m4 m2

c2 ≤ 8

m4 m3

c1 := 0

c1 := 0

c1 := 0 c2 ≥ 2 m4 m3

c1 := 0 c2 := 0

c2 := 0

m4 c1 = 5 m1 m2

m4 m2

c2 ≤ 8

c1 = 5

c1 = 5 c2 := 0 f m2

c2 ≤ 8

c1 = 5 c2 ≥ 2 f m3

c1 = 5 c2 := 0

f

f m2

Figure 8.5: The global automaton for the job-shop speci?cation. The automata on the left and upper parts of the ?gure are the partial compositions of the automata for the tasks of J 1 and J 2 , respectively.

98

8.5. OPTIMAL STRATEGIES FOR TIMED AUTOMATA

8.5

Optimal Strategies for Timed Automata

Let J be a job-shop speci?cation and let AD,d = (Q, C, s, f, I, Δ) be the automaton corresponding to an instance d, that is, “end” transitions are guarded by conditions of the form ci ≥ d(pi ). Let h : Q × H → R+ be a function such that h(q, v) is the length of the minimal run from (q, v) to f , assuming that all uncontrolled future transitions will be taken according to d. This function admits the following recursive backward de?nition: h(f, v) = 0 h(q, v) = min{t + h(q , v ) : (q, v) ?→ (q, v + t1) ?→ (q , v )}. In other words, h(q, v) is the minimum over all successors q of q of the time it takes from (q, v) to satisfy the transition guard to q plus the time to reach f from the resulting con?guration (q , v ). In [AM99] it has been shown that h ranges over a class of “nice” functions, closely related to zones, and that this class is well-founded and hence the computation of h terminates even for automata with cycles, a fact that we do not need here as h is computed in one sweep through all paths from the ?nal to the initial state. Let us illustrate the computation of h on our example. We write the function in the form h(q 1 , q 2 , c1 , c2 ) and use ⊥ to denote cases where the value of the corresponding clock is irrelevant (its task is not active). We start with h(f, f, ⊥, ⊥) = 0 . h(m4 , f, c1 , ⊥) = 5 ? c1 . h(f, m3 , ⊥, c2 ) = 7 ? c2 This is because the time to reach (f, f ) from (m4 , f ) is the time it takes to satisfy the guard c1 = 5, etc. The value of h at (m4 , m3 ) depends on the values of both clocks which determine what will terminate before, m4 or m3 and whether the shorter path goes via (m4 , f ) or (f, m3 ). h(m4 , m3 , c1 , c2 ) = min

. . 7 ? c2 + h(m4 , f, c1 + (7 ? c2 ), ⊥), . c + h(f, m , ⊥, c + (5 ? c )) . 5? 1 3 2 1 t 0

. . = min{5 ? c1 , 7 ? c2 } . . 5 ? c1 if c2 ? c1 ≥ 2 . c . 7 ? 2 if c2 ? c1 ≤ 2

=

Note that in this state the outgoing transitions are both uncontrolled “end” transition and no decision of the scheduler is required. This procedure goes higher and higher in the graph, computing h for the whole state-space Q × H. In particular, for state (m1 , m3 ) where we need to decide whether to start m3 of J 2 or to wait, we obtain: . h(m1 , m3 , c1 , ⊥) = min{16, 21 ? c1 } = 16 if c1 ≤ 5 . 21 ? c1 if c1 ≥ 5

The extraction of a strategy from h is straightforward: if the optimum of h at (q, v) is obtained via a controlled transition to q we let σ(q, v) = q otherwise if it is obtained via an uncontrolled transition we let σ(q, v) = ⊥. For (m1 , m3 ) the optimal strategy is σ(m1 , m3 , c1 , ⊥) = 99 (m1 , m3 ) if c1 ≤ 5 ⊥ if c1 ≥ 5

8.6. EXPERIMENTAL RESULTS

meaning that if m1 is used for less than 5 time units we give m3 to J 2 and if it has been used for more than 5 time units we wait until it terminates and give machine m2 to J 1 . Note that if we assume that J 1 and J 2 started their ?rst tasks simultaneously, the value of c1 upon entering (m1 , m3 ) is exactly the duration of m2 in the instance. The results of Chapter ?? concerning “non-lazy” schedules imply that optimal strategies have the additional property that if σ(q, v) = ⊥ then σ(q, v ) = ⊥ for every v ≥ v. In other words, if an enabled controlled transition gives the optimum it should be taken as soon as possible. This fact will be used later in the implementation of the strategy. Theorem 13 (Computability of Optimal Strategies) Given an uncertain job-shop speci?cation and an instance d it is possible to compute a d-future optimal scheduling strategy. This result is a special case of the result of [AM99].

8.5.1

Implementation

Existing algorithms for timed automata work on sets, not on functions, and in order to apply them to the computation of h we use the following construction. Let A be an auxiliary automaton augmented with a clock representing absolute time. Clearly, if (q, v, t) is reachable in A from the initial state (s, 0, 0) then (q, v) is reachable in A in time t. Let Θ be a positive integer larger then the longest path in the automaton. Starting from (f, ⊥, Θ) and doing backward reachability we can construct a relational representation of h. More precisely, if (q, v, t) is backward reachable in the extended timed automaton A from (f, {⊥}, Θ) then f is forward reachable in A from (q, v) within Θ ? t time. Applying the standard backward reachability algorithm for timed automata we compute the set R of all backward-reachable symbolic states. In order to be able to extract strategies we store tuples of the form (q, Z, q ) such that Z is a zone of A and q is the successor of q from which (q, Z) was reached backwards. The set R gives su?cient information for implementing the strategy. Whenever a transition to (q, v) is done during the execution we look at all the symbolic states with discrete state q and ?nd h(q, v) = min{Θ ? t : (v, t) ∈ Z ∧ (q, Z, q ) ∈ R}. If q is a successor via a controlled transition, we move to q , otherwise we wait until a task terminates and an uncontrolled transition is taken. Non-laziness guarantees that we need not revise a decision to wait until the next transition.

8.6

Experimental Results

We have implemented the algorithm using the zone library of Kronos [BDM+ 98], as well as the hole-?lling strategy and the algorithm for the exponential distribution. As a benchmark we took the following problem with 4 jobs and 6 machines:

J1 J2 J3 J4 : : : : (m2 , [ 4, 10]) ? (m4 , [ 1, 7]) ? (m3 , [28, 40]) ? (m1 , [ 7, 15]) ? (m5 , [ 6, 25]) ? (m6 , [45, 63]) (m5 , [14, 25]) ? (m1 , [34, 46]) ? (m2 , [ 2, 27]) ? (m4 , [ 9, 14]) ? (m6 , [14, 29]) ? (m3 , [32, 48]) (m4 , [47, 55]) ? (m6 , [32, 46]) ? (m1 , [ 4, 12]) ? (m5 , [ 1, 14]) ? (m2 , [ 5, 16]) ? (m3 , [ 4, 9]) (m6 , [54, 72]) ? (m2 , [21, 36]) ? (m3 , [ 1, 8]) ? (m4 , [22, 37]) ? (m1 , [ 7, 18]) ? (m5 , [ 4, 18])

The static worst-case schedule for this problem is 210. We have applied Algorithm 1 to ?nd dfuture optimal strategies based on three instances that correspond, respectively, to “optimistic”, 100

8.6. EXPERIMENTAL RESULTS

“realistic” and “pessimistic” predictions. For every p such that D(p) = [l, u] they are de?ned as dmin (p) = l davg (p) = (l + u)/2 dmax (p) = u. We have generated random instances and compared the results of the abovementioned strategies with an optimal clairvoyant scheduler3 that knows d in advance, and a static worst-case scheduler. The ?rst table compares the performance on 30 instances where durations are drawn uniformly from the [l, u] intervals. As it turns out that the pessimistic adaptive strategy, based on dmax , is very good and robust. It gives schedules that, on the average, are only 2.39% longer than those produced by a clairvoyant scheduler. For comparison, the static worst-case strategy deviates from the optimum by an average of 16.18%. On the other hand the realistic and optimistic strategies are usually inferior to the pesimistic one and in some instances they are even worse than the static schedule. This can be explained by the fact that schedules that rely on the minimal prediction are almost always not executed as planned. The hole-?lling strategy based on worst-case prediction achieves good performance (3.73% longer than the optimum) with a much more modest computational e?ort (the results of hole-?lling based on optimisitc and realistic predictions are bad and are not shown in the table).

In the domain called online algorithms it is common to compare the performance of algorithms that receive their inputs progressively to a clairvoyant algorithm and the relation between their performances is called the competitive ratio.

3

101

8.6. EXPERIMENTAL RESULTS

Inst 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 Avg

Opt 172 193 157 175 177 186 176 176 180 167 202 166 189 176 180 167 178 175 174 176 170 167 185 170 158 171 179 174 162 172 175

Static 204 210 203 208 199 209 203 203 206 204 206 202 202 199 204 204 204 202 202 201 199 202 210 204 203 204 199 203 201 200 203.33

% 18.60 8.80 29.29 16.00 12.42 12.36 15.34 15.34 14.44 22.15 1.98 6.87 6.87 13.06 13.33 22.15 14.60 15.42 16.09 14.20 17.05 20.95 13.51 20.00 28.48 19.29 11.17 16.66 24.07 16.27 16.18

Max 172 193 172 181 177 189 177 186 180 171 202 166 189 176 180 171 180 182 174 180 170 168 185 191 163 193 179 180 170 179 179.19

% 0.00 0.00 9.55 3.43 0.00 1.16 0.57 5.68 0.00 2.40 0.00 0.00 0.00 0.00 0.00 2.40 1.12 4.00 0.00 2.27 0.00 0.60 0.00 12.35 3.16 12.87 0.00 3.45 4.94 4.07 2.39

Avg 186 193 178 181 198 192 180 209 186 170 202 172 189 184 185 175 187 184 181 183 187 174 185 177 168 193 193 182 171 193 184.60

% 8.13 0.00 13.37 3.42 11.86 3.22 2.27 18.75 3.33 1.79 0.00 3.61 0.00 4.54 2.77 4.79 5.05 5.14 4.02 9.97 10.00 4.19 0.00 4.11 6.32 12.86 7.82 4.59 5.55 12.02 5.48

Min 205 193 189 194 196 189 197 204 195 183 203 197 221 192 192 178 201 204 191 192 182 183 200 176 185 200 210 202 183 183 191.93

% 19.18 0.00 20.38 10.85 10.73 1.61 11.93 15.90 8.33 9.58 0.49 18.67 16.93 9.09 6.66 6.58 12.92 17.24 9.77 9.09 70.5 9.58 8.10 3.52 17.08 11.73 17.31 16.09 12.96 6.39 9.67

Hole 174 210 157 175 192 186 184 186 181 167 202 175 199 185 189 177 188 182 175 190 171 180 189 187 165 171 179 174 172 184 181.53

% 1.16 8.81 0.00 0.00 8.47 0.00 4.55 5.68 0.56 0.00 0.00 5.42 5.29 5.11 5.00 5.99 5.62 4.00 0.57 5.68 0.59 1.80 2.16 10.00 4.43 0.00 0.00 0.00 6.16 6.98 3.73

102

Chapter 9

Conclusions

In this thesis we have laid the foundations for an automaton-based scheduling methodology. As a ?rst step we have attacked problems such as the job-shop problem that can be solved using existing techniques, in order to see if the performance of timed automata technology is acceptable. As it turned out, the standard zone-based algorithms for timed automata were too heavy and this led us to the discovery of non-lazy schedules and runs. Using points instead of zones, we could compete with other techniques and this insight may be useful also for standard veri?cation of timed automata. The next step was to consider preemption, where the cyclic nature of the automaton poses problems also for other techniques. If the number of preemptions is not bounded, there is no bound on the number of variables in the corresponding constrained optimization problem. This led us to the rediscovery of “Jackson schedule” from the 50s, what we call “e?cient”. With this result, a point based search algorithm can be applied, leading to competetive performance. It also shows that the undecidability results for stopwatch automata are not always relevant. The generalization to the task graph problem was rather straightforward, the only signi?cant new feature was the decomposition of the partial order to form a chain cover, and the adaptation of the mutual exclusion condition to identical machines. Again the performance of our algorithm was not worse than the state-of-the-art in the domain. The treatment of uncertainty in Chapter 8 was supposed to be the ?rst domain where the advantages of a state-based approach like ours become visible. And indeed, the de?nition and computation of adaptive strategies would be very hard to perform without the insight coming from the automaton model. However we consider the results so far only as a partial success because the backward reachability algorithm in its current form has to explore all the state-space (unlike a best-?rst search used in forward reachability) and use the expensive zone technology. This implies that the size of problems that can be treated is much smaller than for the deterministic case. Much more work is needed to extend the scope of scheduling strategy synthesis. On the other hand, a less adaptive strategy such as hole ?lling can be easily implemented on top of our solution of the deterministic problem. For future work we envisage too major research directions, one concerned with improving the performance and the other in extending the models to treat more complex scheduling situations. The ?rst direction include: 1. New search heuristics for deterministic problems. 2. New techniques for “compositional” scheduling. The basic idea is that jobs can be grouped into subsets and an optimal schedule can be found for each subset. Then, each obtained schedule for a subset can be seen as a job by itself, and the composition of these “super jobs” de?nes a new scheduling problem. Clearly this technique is not guaranteed to give an 105

optimal solution but it may suggest a practical approach for treating a very large number of jobs.. 3. Combination of forward and backward reachability in strategy synthesis. The hardness of strategy synthesis is that a-priori a strategy should be computed for every reachable con?guration, but the de?nition of a reachable con?guration depends on the strategy. Consequently our current algorithm computes the strategy for all reachable con?guration under any strategy. Is is clear, however, that some strategies (especially very lazy ones) will never be chosen. If, using forward analysis, we can restrict the set of states for which we need to compute a strategy, we can restrict signi?cantly the computation time. Moreover, if we accept sub-optimal strategies, we can refrain from computing the strategy even for some reachable states and use default actions if these states are reached in the actual schedule. Among the many possible extensions of the scheduling problems we mention the following:: 1. Job-shop problems where some steps can be executed on di?erent machines with di?erent speeds. 2. Problems where the identity of the next step to be executed depends on the result of the current step. Such situation occur, for example, in computer programs. 3. Problems where some of the structure of the tasks depends also on the previous choices of the scheduler. For example, if machines are distributed geographically, di?erent choices of machines will imply di?erent steps of transportation. Likewise, in task graph scheduling, communication should be added between tasks that do not execute on the same machine. 4. Problems with more complex timing constraints for which the laziness results do not hold. For example, problem with relative deadlines or synchronization constraints in task graph scheduling. We believe that, regardless of the current applicability of our techniques to real-life industrialsize problems, the framework developed in this thesis adds a new perspective from which scheduling problems can be viewed, understood and solved.

106

Bibliography

[AM02] Y. Abdeddaim and O. Maler, Preemptive Job-Shop Scheduling using Stopwatch Automata, in J.Katoen and P.Stevens (Eds.), TACAS’02, 113-126, LNCS 2280, Springer 2002. Y. Abdedda¨ and O. Maler, Job-Shop Scheduling using Timed Automata in ?m G. Berry, H. Comon and A. Finkel (Eds.), Proc. CAV’01, 478-492, LNCS 2102, Springer 2001. R. Alur, S. La Torre and G.J. Pappas, Optimal Paths in Weighted Timed Automata, Proc. HSCC’01, 49-64, LNCS 2034, Springer 2001. K. Altisen, G. Goessler, A. Pnueli, J. Sifakis, S. Tripakis and S. Yovine, A Framework for Scheduler Synthesis. Proc. RTSS’99, 154-163, IEEE, 1999. E. Asarin and O. Maler, As Soon as Possible: Time Optimal Control for Timed Automata, Proc. HSCC’99, 19-30, LNCS 1569, Springer, 1999. E. Asarin, O. Maler, A. Pnueli and J. Sifakis, Controller Synthesis for Timed Automata, Proc. IFAC Symposium on System Structure and Control, 469-474, Elsevier, 1998. E. Asarin, O. Maler and A. Pnueli, Symbolic Controller Synthesis for Discrete and Timed Systems, Hybrid Systems II, LNCS 999, Springer, 1995. R. Alur and D.L. Dill, A Theory of Timed Automata, Theoretical Computer Science 126, 183-235, 1994. R. Alur, C. Courcoubetis, and D.L. Dill, Model Checking in Dense Real Time, Information and Computation 104, 2-34, 1993. D. Applegate, and W. Cook, A Computational Study of the Job-Shop Scheduling Problem, ORSA 149-156, Journal on Computing, Spring, 3(2), 1991. J. Adams, E. Balas, and D. Zawack, The Shifting Bottleneck Procedure for JobShop Scheduling, 391-401, Management Science, March, 34(3), 1988. S .Ashour, A Decomposition Approach for the Machine Scheduling Problem, 109122,International Journal of Production Research 6(2), 1967.

[AM01]

[ATP01] [AGP99] [AM99] [AMPS98]

[AMP95] [AD94] [ACD93] [ABC91] [ABZ88] [A67]

[BFH+ 01a] G. Behrmann, A. Fehnker, T.S. Hune, K.G. Larsen, P. Pettersson and J. Romijn, E?cient Guiding Towards Cost-Optimality in UPPAAL, Proc. TACAS 2001, 174188, LNCS 2031, Springer, 2001.

109

BIBLIOGRAPHY

[BFH+ 01b] G. Behrmann, A. Fehnker T.S. Hune, K.G. Larsen, P. Pettersson, J. Romijn and F.W. Vaandrager, Minimum-Cost Reachability for Linearly Priced Timed Automata, Proc. HSCC’01, 147-161, LNCS 2034, Springer 2001. [BS99] R. Boel and G. Stremersch, VHS case study 5: Modelling and Veri?cation of Scheduling for Steel Plant at SIDMAR, Draft, 1999.

[BDM+ 98] M. Bozga, C. Daws, O. Maler, A. Olivero, S. Tripakis, and S. Yovine, Kronos: a Model-Checking Tool for Real-Time Systems, Proc. CAV’98, LNCS 1427, Springer, 1998. [BB96] E.A. Boyd, and R. Burlingame, A Parallel Algorithm for Solving Di?cult JobShop Scheduling Problems, Operations Research Working Paper, Department of Industrial Engineering, Texas A & M University, College Station, Texas 778433131, USA, 1996. P. Baptiste, C. Le Pape, and W.P.M Nuijten, Constraint-Based Optimization and Approximation for Job-Shop Scheduling, AAAI-SIGMAN Workshop on Intelligent Manufacturing Systems, 14 th International Joint Conference on Arti?cial Intelligence, Montr?al, Qu?bec, Canada, Aug 19, pp. 5-16, 1995. e e P. Brucker, B. Jurisch, and B. Sievers, A Branch and Bound Algorithm for the JobShop Scheduling Problem, 109-127, Discrete Applied Mathematics, vol 49, 1994 . E. Balas, Machine Scheduling via Disjunctive Graphs: An Implicit Enumeration Algorithm, 941-957, Operations Research, vol 17, 1969 . E.H. Bowman, The Schedule-Sequencing Problem, 621-624, Operations Research, vol 7, 1959. F. Cassez and K.G. Larsen, On the Impressive Power of Stopwatches, in C. Palamidessi (Ed.) Proc. CONCUR’2000, 138-152, LNCS 1877, Springer, 2000. S. Campos, E. Clarke, W. Marrero, M. Minea and H. Hiraishi, Computing Quantitative Characteristics of Finite-state Real-time Systems, Proc. RTSS’94, IEEE, 1994. Y. Caseau and F. Laburthe, Improved CLP Scheduling with Task Intervals, in Van Hentenryck, P. (ed) ICLP94 Proceedings of the Eleventh International Conference on Logic Programming, MIT Press, 1994. C. Chu, M.C. Portmann, and J.M. Proth, A Splitting-Up Approach to Simplify JobShop Scheduling Problems, 859-870, International Journal of Production Research 30(4), 1992. K. Cerans, Algorithmic Problems in Analysis of Real Time System Speci?cations, Ph.D. thesis, University of Latvia, Riga, 1992. Z. Chaochen, C.A.R. Hoare and A.P. Ravn, A Calculus of Durations, Information Processing Letters 40, 269-276, 1991. C. Courcoubetis and M. Yannakakis, Minimum and Maximum Delay Problems in Real-time Systems, Proc. CAV’91, LNCS 575, 399-409, Springer, 1991. 110

[BPN95]

[BJS94]

[B69] [B59] [CL00] [CCM+ 94]

[CY94]

[CPP92]

[C92] [CHR91] [CY91]

BIBLIOGRAPHY

[CP90] [C82] [DY96] [DR94]

J. Carlier and E. Pinson, A Practical Use of Jackson’s Preemptive Schedule for Solving the Job-Shop Problem, Annals of Operations Research 26, 1990. J .Carlier, The One-Machine Sequencing Problem, 42-47, European Journal of Operational Research, vol 11, 1982. C. Daws and S. Yovine, Reducing the Number of Clock Variables of Timed Automata, Proc. RTSS’96, 73-81, IEEE, 1996. F. Della Croce, R. Tadei, and R. Rolando, Solving a Real World Project Scheduling Problem with a Genetic Approach, Belgian Journal of Operations Research, 65-78, Statistics and Computer Science, 33(1-2), 1994 . E. Dijkstra, A note on two problems in connexion with graphs, Numerische Mathematik 1, 269-271, 1959. R.P. Dilworth, A decomposition theorem for partially ordered sets, Ann. Math. 51 (1950), 161-166. A. Fehnker, Scheduling a Steel Plant with Timed Automata, Proc. RTCSA’99, 1999. S. French, Sequencing and Scheduling - An Introduction to the Mathematics of the Job-Shop, Ellis Horwood, John-Wiley & Sons, New York, 1982. M.L. Fisher, Optimal Solution of Scheduling Problems using Lagrange Multipliers: Part I, 1114-1127, Operations Research, vol 21, 1973. M.L. Fisher, Optimal Solution of Scheduling Problems using Lagrange Multipliers: Part II, Symposium on the Theory of Scheduling and its Applications, Springer, Berlin, 1973. H. Fisher, and G.L Thompson, Probabilistic Learning Combinations of Local JobShop Scheduling Rules, in J.F. Muth, and G.L Thompson, 225-251, (eds) Industrial Scheduling, Prentice Hall, Englewood Cli?s, New Jersey, Ch 15, 1963. M. R. Garey and D. S Johnson, Computers and Intractability, A Guide to the Theory of NP-Completeness, W. H. Freeman and Company, 1979. B. Gi?er, and G.L. Thompson, Algorithms for Solving Production Scheduling Problems, 487-503, Operations Research, 8(4), 1960. T. Henzinger, X. Nicollin, J. Sifakis, and S. Yovine, Symbolic Model-checking for Real-time Systems, Information and Computation 111, 193–244, 1994. D.J. Hoitomt, P.B. Luh, and K.R. Pattipati, Practical Approach to Job-Shop Scheduling Problems, 1-13, IEEE Trans Rob Autom, Feb, 9(1), 1993. A.S. Jain and S. Meeran, Deterministic Job-Shop Scheduling: Past, Present and Future, European Journal of Operational Research 113, 390-434, 1999. J. R. Jackson, Scheduling a Production Line to Minimize Maximum Tardiness, Research Report 43, Management Sciences Research Project, UCLA, 1955. Y. Kesten, A. Pnueli, J. Sifakis and S. Yovine, Decidable Integration Graphs, Information and Computation 150, 209–243, 1999. 111

[D59] [D50] [F99] [Fr82] [F73a] [F73b]

[FT63]

[GJ79] [GT60] [HNSY94] [HLP93] [JM99] [J55] [KPSY99]

BIBLIOGRAPHY

[KSSW95]

K. Kr¨ger, N.V. Shakhlevich, Y.N. Sotskov, and F. Werner, A Heuristic Decompou sition Algorithm for Scheduling Problems on Mixed Graphs, 1481-1497, Journal of the Operational Research Society, vol 46, 1995. O. Maler, On the Problem of Task Scheduling, Draft, February 1999. P.D. Martin, A Time-Oriented Approach to Computing Optimal Schedules for the Job-Shop Scheduling Problem, Ph. D. Thesis, School of Operations Research & Industrial Engineering, Cornell University, Ithaca, New York 14853-3801, August 1996. O. Maler, A. Pnueli and J. Sifakis. On the Synthesis of Discrete Controllers for Timed Systems, Proc. STACS’95, 229-242, LNCS 900, Springer, 1995. J. McManis and P. Varaiya, Suspension Automata: A Decidable Class of Hybrid Automata, in D.L Dill (Ed.), Proc. CAV’94, 105-117, LNCS 818, Springer, 1994. A.S. Manne, On the Job-Shop Scheduling Problem, 219-223, Operations Research, vol 8, 1960. P. Niebert, S. Tripakis S. Yovine, Minimum-Time Reachability for Timed Automata, IEEE Mediteranean Control Conference, 2000. P. Niebert and S. Yovine, Computing Optimal Operation Schemes for Chemical Plants in Multi-batch Mode, Proc. HSCC’2000, 338-351, LNCS 1790, Springer, 2000. W.P.M. Nuijten, and C. Le Pape, Constraint-Based Job Shop Scheduling with ILOG SCHEDULER, Journal of Heuristics, March, 3(4), 271-286, 1998. W.P.M. Nuijten, and E.H.L. Aarts, A Computational Study of Constraint Satisfaction for Multiple Capacitated Job Shop Scheduling, European Journal of Operational Research, vol 90, 269-284, 1996. C. Le Pape and P. Baptiste, A Constraint-Based Branch-and-Bound Algorithm for Preemptive Job-Shop Scheduling, Proc. of Int. Workshop on Production Planning and Control, Mons, Belgium, 1996. C. Le Pape and P. Baptiste, An Experimental Comparaison of Constraint-Based Algorithms for the Preemptive Job-shop Sheduling Problem, CP97 Workshop on Industrial Constraint-Directed Scheduling, 1997. E. Pesch, U.A.W. Tetzla?, Constraint Propagation Based Scheduling of Job Shops, INFORMS Journal on Computing, Spring, 8(2), 144-157, 1996. M. Perregaard, and J. Clausen, Parallel Branch-and-Bound Methods for the JobShop Scheduling Problem, Working Paper, University of Copenhagen, Copenhagen, Denmark, 1995. B. Roy, and B. Sussmann, Les Probl`mes dOrdonnancement avec Contraintes Dise jonctives, Note D.S. no. 9 bis, SEMA, Paris, France, D?cembre, 1964. e I. Sabuncuoglu, and M. Bayiz, A Beam Search Based Algorithm for the Job Shop Scheduling Problem, Research Report: IEOR-9705, Department of Industrial Engineering, Faculty of Engineering, Bilkent University, 06533 Ankara, Turkey, European Journal of Operational Research, 1997. 112

[M99] [Ma96]

[MPS95] [MV94] [M60] [NTY00] [NY00]

[NP98] [NA96]

[PB96]

[PB97]

[PT96] [PC95]

[RS64] [SB97]

BIBLIOGRAPHY

[V91] [WH92] [YI99]

S. Van De Velde, Machine Scheduling and Lagrangian Relaxation, Ph. D. Thesis, CWI Amsterdam, The Netherlands, 1991. H. Wong-Toi and G. Ho?mann, The Control of Dense Real-Time Discrete Event Systems, Technical report STAN-CS-92-1411, Stanford University, 1992. K. Yu-Kwong, A. Ishfaq, Benchmarking and Comparison of the Task Graph Scheduling Algorithms. Journal of Parallel and Distributed Computing 59(3), 381422 , 1999. S. Yovine, Kronos: A Veri?cation Tool for Real-time Systems, Int. J. of Software Tools for Technology Transfer 1, 1997.

[Y97]

113

- Philippe FLAJOLET...................... Directeur de thèse
- APPLICATIONS à COMPOSANTS Directeur de thèse
- Directrice de thèse
- Directeur de th`ese
- Directeur de thèse Monsieur JEAN-LUC MINEL
- en Génie Logiciel Céline Directeur de thèse
- Directeur de Thèse P. COIRAULT Co-encadrement L. RAMBAULT
- TH èSE
- Thèse de doctorat
- Composition du jury de thèse
- 清水河县亿富达油业有限责任公司加油站工程项目
- 日本史上有名的武器并称
- SOD-MDA研究生实验
- 公路工程试验检测人员业务考试应试题集及模拟试卷-桥梁部分
- 般+若+心+经

更多相关文章：
更多相关标签：