A Distributed Scheduling Framework. Carla P. Gomes Austin Tate Lyn Thomas. University of Edinburgh University of Edinburgh University ofedinburgh

Please download to get full document.

View again

of 7
2 views
PDF
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
Document Description
A Distributed Scheduling Framework Carla P. Gomes Austin Tate Lyn Thomas Dept. of Articial Intelligence AIAI Dept. of Business Studies University of Edinburgh University of Edinburgh University ofedinburgh
Document Share
Document Transcript
A Distributed Scheduling Framework Carla P. Gomes Austin Tate Lyn Thomas Dept. of Articial Intelligence AIAI Dept. of Business Studies University of Edinburgh University of Edinburgh University ofedinburgh Scotland, United Kingdom Scotland, United Kingdom Scotland, United Kingdom Abstract A distributed problem solving approach to job shop scheduling is described in this paper. The approach views the system as an Organisation. s are assigned dierent roles and functions depending on their position within the structure of the Organisation. In this Organisation, agents of the same level state their interests independently of each other and therefore Conict is likely to occur. A major thesis of the research reported here is that not only is it important to deal with conict but also that conict as a consequence of the scheduling process should be exploited as a way of integrating dierent scheduling perspectives, as a way of allowing agents to express their own interests independently of each other and, thus, as a way of guaranteeing pluralism by providing agents with both empirical knowledge (heuristics, dispatch rules) and theoretical knowledge (optimal algorithms). 1 Introduction Scheduling is dened by [1] as the allocation of resources over time to perform a collection of tasks. The job shop scheduling problem consists of assigning times and individual machines to a set of jobs that have to be performed on a nite set of resources, considering some metrics. Each job, also called order, consists of a set of operations related to each other according to a certain process plan that species a partial ordering among the operations. A distributed problem solving approach to job shop scheduling is described in this paper. Hereafter we will refer to it, as well as the system which embodies it, as explicit. explicit can be compared to a hierarchical organisation with three main levels: the Strategic level, the Presently, Carla O. Pedro Gomes is working for Rome Lab., 525 Brooks Rd. Griss AFB NY , as an independent consultant. level and the Operational level. The overall structure of explicit and an outline of the scheduling process regarding the agents of the systems and their scheduling functions is presented in the next section. A more detailed description of the scheduling process is presented in section 3. Section 3 includes a simple example to illustrate the scheduling process adopted by explicit. Section 4 presents some results concerning the performance of explicit. Section 5 summarises the main features of explicit. A discussion of future research directions is also included in this section. 2 The Overall Structure of the System Figure 1 displays the overall structure of the jobshop scheduling framework. This structure is inspired by das (Distributed Asynchronous System), a system developed at the University of Strathclyde [3], [2]. However, although there are some similarities between explicit and das in terms of the general structure of the system, there are substantial dierences in terms of the processes associated with the dierent agents of the systems, i.e., the functional organisation of the systems, and in terms of the techniques and methods used in both systems 1. At the Strategic Level, the Strategic is responsible for the whole problem, particularly for assigning work to the Level and for detecting and solving conicts that occur from the scheduling decisions performed by the s. At the intermediate level, the Level, there are two categories of s: the Resource s and the Job s. The Job s are responsible for the jobs. There are as many Job s as the number of jobs to be scheduled. The Resource s are responsible for the aggregate resources. An aggregate resource 1 For a detailed comparison between the two systems see [5]. is a set of identical machines capable of performing a certain operation. There are as many Resource s as the number of aggregate resources. o11 o21 o31 o41 Jobs to be scheduled Strategic Conflict Detection Conflict Resolution Work Assignment Plan S Strategic Level r11 o12 o32 o42 o52 r13 r12 o22 r23 r14 r24 Job J Job Resource Resource R Level r21 o13 o23 o33 o14 o34 o44 Time Window Assignment Conflict Propagation Operational s Local Optimisation Operational s O Start Time Assignment Operational Level o24 oij - operation i of job j rij - individual machine i of aggregate resource j operations precedence resource requirement disjunctive arcs Figure 1: The agents of explicit and the schedule generation process Figure 1 also depicts the process of schedule generation. The jobs enter the system via the Strategic. The Strategic sends each job to the corresponding Job for the assignment of time windows to the operations that constitute the job. The Job s assign time windows to their operations independently of each other. This task is performed assuming unlimited resources. The Job s send the results of the time window assignment to the Strategic. Once the Strategic receives the time windows for all the operations of all the jobs, it assigns work to the Resource s. Operations to be performed on the same aggregate resource are sent to the respective Resource with the respective time windows. The Resource s assign individual machines and start times to the operations to be performed on their aggregate resources. Analogously to the Job s, the Resource s perform their scheduling tasks independently of each other. If the system is provided with Operational s, the Resource s assign work to each of their Operational s. Each Operational receives the information concerning the set of operations to be performed on its individual machine. The Operational s are responsible for locally improving the schedules proposed by their superior. The Operational s carry out their scheduling tasks independently of each other. Operational s send their schedules to the Strategic. If the system Figure 2: The representation of the job shop scheduling problem does not include Operational s, the Resource s send their schedules directly to the Strategic. When the Strategic agent gets the times assigned to the operations by dierent RTAs, it is responsible for: (1) identifying the conicts that exist among the schedules proposed by the dierent s (2) generating Plans to solve the detected conicts (3) generating Plans to coordinate the scheduling activity of the s, in particular the redinition of time windows of the operations that have to be rescheduled. This framework is very suitable for parallel implementation since the dierent and Operational s perform their tasks independently of each other and so they can perform their tasks concurrently. 3 Scheduling with Explicit 3.1 Formulation of the problem It is useful to represent the whole problem as a graph G =(O R A E), with node set fo Rg, and ordinary (conjunctive) arc set A and disjunctive arc set E. Figure 2 illustrates this graph. ThenodesetO of G, O = fo ij : i 2 N j j 2 Ng, N the set of indices of the jobs to be scheduled and N j the set of indices of the operations of a given job j, corresponds to the operations of the jobs to be scheduled (represented by a circle in the graph). The node set R of G, R = fr ij : i 2 M j j 2 Mg, M the set of indices of the dierent aggregate resources or machine types and M j the set of indices of the individual machines of a given aggregate resource j, corresponds to the different machines on which the dierent jobs have tobe scheduled (represented by a square in the graph). The arc set A of G, A = f(o ij o lj ):i l 2 N j j2 Ng, corresponds to precedence relations between operations of the same job (represented by full arrows in the graph). The disjunctive arc set E, E = f(o ij r lk ):i2 N j j 2 N l 2 M k k 2 Mg, denotes the alternative machines where a given operation can be performed (represented by dashed arrows in the graph). The set of arcs A decomposes the graph G into subgraphs (O j A j ), where O j = fo ij : i 2 N j j 2 Ng, O = S (O j : j 2 N) and A j = f(o ij o lj ) : i l 2 N j j 2 Ng, A = S (A j : j 2 N). Each subgraph (O j A j ) corresponds to a job j, j 2 N. The set of disjunctive arcs E decomposes the graph G into subgraphs (O k R k E k ), where O k = fo ij : (9 (o ij r lk )) i 2 N j j 2 N l 2 M k k 2 Mg 2, O = S (O k : k 2 M), R K = fr ik : i 2 M k k 2 Mg, R = S (R k : k 2 M), one for each aggregate resource or machine type, M the set of indices of the aggregate resources. The subgraph (O k R k E k ) corresponds to the problem associated with the aggregate resource k 2 M, i.e.,the set of individual machines of a certain type, and the operations that have tobescheduled on it. The job shop scheduling or machine sequencing problem can be dened as follows. Times (start and nish times) and individual machines have tobeas- signed to each operation of a set of jobs, satisfying a set of constraints and considering a certain objective. Referring to the gure 2, the job shop scheduling problem can be stated as how to partition the node set O into subsets such that operations that are members of the same subset are assigned to the same individual machine r ij, with a given start time and nish time, satisfying all the constraints and considering a certain objective (typically the minimisation or maximisation of a certain function). The approach adopted in explicit is \divide and conquer , i.e., the decomposition of the whole problem into smaller and more manageable problems in order to reduce the overall computational complexity of the scheduling problem. Dierent agents are assigned dierent (sub)problems. Each Job is responsible for assigning time windows to the 2 Note that O k denotes the set of operations that are assigned to the same aggregate resource k, while O k is the set of operations that belong to the same job k. operations of its job. The Job responsible for job j is denoted by JTA j. The problem associated with JTA j is represented by the subgraph (O j A j ). Each Resource is responsible for assigning start times and individual machines to the operations to be performed on its aggregate resource. The Resource responsible for the aggregate resource k is denoted by RT A k. The problem associated with RT A k is represented by the subgraph subgraph (O k R k E k ). The Strategic is responsible for the whole problem, in particular for coordinating the scheduling tasks of the and Operational s. 3.2 The Newspaper Example Alan (A), Carla (C), Flavio (F), Ian (I), Nelson (N) and Suresh (S) share a at. Every Saturday they have delivered at their at two copies of the following newspapers: the European (E), the Financial Times (F), the Guardian (G), the Scotsman (S). Each atmate gets up at a certain time and insists on reading all the papers in a particular order (precedence constraints). Each atmate wants to leave the at by agiven time (due-time). Table 1 summarises the data for the example. In this example, each reader represents a job. The availability time for each job corresponds to the time the reader gets up. The duetime of a job corresponds to the latest time the reader wants to leave the at. Operations of a job correspond to the act of reading a newspaper by a reader. The precedence constraints, i.e., the order that each reader wants to read the newspaper, are reected in the order of the columns in table 1. The Financial Times and the Guardian are delivered at 8.3 a.m (51), the European at 8.4 (52) and the Scotsman at 8.45 (525). Newspapers correspond to resources in a job-shop scheduling problem. Each copy of a particular newspaper corresponds to an individual machine 3. The agents for the newspaper problem are: the Strategic (SA), responsible for the whole scheduling problem the Job s (JTAs), one per job (reader), Alan, Carla, etc the Resource s (RTAs), one per type of resource (newspaper), the European, the Financial Times, etc and the Operational s (OAs), one per individual machine i.e., one per copy of a newspaper. 3 This example takes inspiration from [4] R up out 1st 2nd 3rd 4th A F 6 G 3 E 2 S 5 C E 5 G 15 F 1 S 3 F G 5 S 5 E 5 F 6 I S 9 F 1 G 1 E 1 N F 3 S 1 E 4 G 1 S G 75 E 3 F 25 S 1 Table 1: The data for the newspaper reading problem (in minutes) signment problem to assign machines (and start times) to each operation of that level. Operations that cannot be assigned to a machine are delayed to the next level. After solving the \Assignment Based Algorithm , operations have start times and individual machines assigned to them. At this stage RTA sends the operations to the corresponding Operational (OA) responsible for an individual machine. Operational s are responsible for optimising the schedule of the operations assigned to them. Figure 3 illustrates Carla 3.3 Functions, Roles and Algorithms - The Newspaper Example S In this section the scheduling tasks performed by each agent are analysed from a functional point of view. Some of the algorithms assigned to the problem solving agents are also outlined. The scheduling process is illustrated with the newspaper example. At the beginning of the scheduling process all the jobs are in conict since operations do not have start times assigned to them. The Strategic (SA) initiates the scheduling process by sending all the operations to the respective Job a (JTAs) for time window assignment. The Strategic passes all the necessary information to each JTA for time windows assignment. Each JTA assigns time-windows to its operations solving a critical path method problem (see e.g., [8] and [6]) independently of the other JTAs. At this stage the availability of resources is not considered or, in other words, resources are considered unlimited. SA collects all the data from the dierent JTAs and sends the operations' time-windows to the corresponding Resource s (RTAs). The rst time the SA performs this operation all the operations with the respective time-windows are sent to the corresponding RTAs in order to have start times assigned to them. The time suggested by SA for each operation is the earliest start time assigned by the corresponding JTA to that operation. Information on the slack allowed for each operation is also sent to the RTAs. RTAs assign start times to the operations to be performed on their resources independently of each other. In order to assign start times and individual machines to its operations, each RTA solves the \Assignment Based Algorithm (see [5]) which involves the following steps: (1) the generation of a graph of the operations assigned to RTA and the partition of its nodes into levels 4 (2) for each level, RTAsolves an as- 4 The level of a node is the length, in number of arcs, of the Slack Earliest Finish Time Earliest Start Time Ian Nelson Flavio Alan Suresh Level Level 1 Level 2 Level 3 Figure 3: The Resource problem. Graph S sco for the Scotsman the graph corresponding to the problem assigned to RTA responsible for the Scotsman (RT A sco ). Figure 3 also illustrates the dierent levels of the graph. R SA RTA OA # ST FT SLK ST FT ST FT A C F I N S Table 2: The times assigned by the dierent agents to each reader (1st iteration - in minutes ST - Start Time FT - nish Time SLK - slack) Each Operational is responsible for locally optimising the schedule proposed by the Resource. The algorithm provided to each Operational minimises maximum lateness of the jobs longest path from the source node (S) to that node. assigned to it [7] 5. It is an implicit enumeration algorithm that uses a branch-and-bound technique. In the case of the Scotsman, there are two Operational s (OAs): the OA responsible for copy number 1(OA sco1 ) and the OA responsible for copy number 2(OA sco2 ). Since only one reader was assigned to OA sco2, there is no optimisation process for OA sco2. In the new assignment performed by theoa sco1,nelson reads the Scotsman at 585, instead of 67 as proposed by the RTA, and the reader Flavio reads the Scotsman at 595, instead of 59 as proposed by the RTA. Table 2 displays the dierent times assigned to each operation by each agent. The other RTAs (and OAs) associated with the other newspapers schedule their readers using a scheduling process identical to the one described for the Scotsman. SA (Strategic ) detects the conicts generated from the independent assignment of times performed by each RTA. SA is essentially provided with a rule based system in order to perform its role and functions (see [5] for more details). SA is responsible for: (1) identifying the conicts that exist among the schedules proposed by the dierent s (2) generating Plans to solve the detected conicts (3) generating Plans to coordinate the scheduling activity of the s. The role of SA is very crucial but very simple. A conict occurs whenever an operation starts later than the earliest start time that was last assigned to it by the corresponding Job. The idea of conict is that the current schedule might have to be revised, since all the operations of the same job that come after the operation involved in the conict need to have their time windows revised. Nevertheless, the fact that an operation is involved in a conict does not mean that the operation is late. Its new start time might still be within its initial time window. Conict propagation is done starting with the aected operations with the earliest earliest start time. As a result of the conict propagation, SA generates a plan for conict resolution. This plan contains all the operations that are involved in the conict propagation, either because they belong to a job that had some of its time windows changed or because they are assigned to a resource that had to be rescheduled. As an example, regarding the Scotsman, Nelson is in conict since the start time that was assigned to it was 585, rather than the earliest start time proposed to it, 57. Table3shows the new operations' time windows that were obtained by the propagation of conicts, regarding the Scotsman. In this case, the 5 Li = C i ; d i where L i - lateness of job J i, C i - completion time of job J i, d i - due date of job J i. operations that have new time windows are: Carla, Flavio and Nelson. All of the other RTAs have their Reader Start Time Finish Time Slack Alan Carla Flavio Ian Nelson Suresh Table 3: The information sent by the SA to RT A sco (second iteration) operations and respective time windows revised. Once again they perform the assignment of start times and machines to their operations. The process goes on until a schedule without con- icts is reached. That means that all the operations have start times and that the start times correspond to the last earliest start time proposed to that operation by the SA. Due date relaxation is implicit in explicit. If operations cannot start within their initial time windows their due dates are automatically relaxed, as little as possible. That means that if explicit cannot not nd a solution considering the initial due date contraints, a solution is given relaxing some of those constraints. Table 4 summarises the solution for the newspaper problem in terms of start times assigned to each reader for each newspaper. Notice that this solution does not relax any due date. This solution was reached after 6 cycles, 6 assuming a sequential implementation. Reader 1st 2nd 3rd 4th Alan F 51 G 57 E 6 S 615 Carla E 525 G 53 F 57 S 58 Flavio G 6 S 61 E 615 F 62 Ian S 595 F 685 G 686 E 687 Nelson F 54 S 585 E 595 G 6 Suresh G 525 E 6 F 63 S 628 Table 4: The start times for the newspaper reading problem (in minutes) 6 A cycle corresponds to the following scheduling tasks: analysis of the problem (detection of conicts) and revision of time windows (SA and JTAs), assignment of start times to operations by RTAs and OAs. 4 Perfomance of explicit In order to do a preliminary evaluation of explicit a battery of 54 was generated (see [5] for details). Since explicit was tuned to minimize lateness 7,we chose lateness and tardiness 8 as performance measures to evalutate the performance of explicit. In this paper we include graphs displaying the beha
Similar documents
View more...
Search Related
We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks