Pre-processing techniques for resource allocation in the heterogeneous case

Pre-processing techniques for resource allocation in the heterogeneous case 1 Vicente Valls a,*, M. Angeles Perez b, M. Sacramento Quintanilla b a Dpto. de Estadistica e Investigaci�on Operativa, Facultad de Matem�aticas, Universitat de Val�encia, Dr. Moliner, 50. 46100 Burjassot, Valencia, Spain b Dpto. Econom�ıa Financiera y Matem�atica, Facultad de Ciencias Econ�omicas y Empresariales, Universitat de Val�encia, Avda. Blasco Iba~nez, 30. 46010 Valencia, Spain Received 1 May 1996; received in revised form 1 June 1997 Abstract The Heterogeneous Resource Allocation Problem (HRAP) deals with the allocation of resources, whose units do not all share the same characteristics, to an established plan of activities. Each activity requires one or more units of each resource which possess particular characteristics, and the objective is to find the minimum number of resource units of each type, necessary to carry out all the activities within the plan, in such a way that two activities whose processing overlaps in time do not have the same resource unit assigned. The HRAP is an NP-Complete problem and it is possible to optimally solve medium-sized HRAP instances in a reasonable time. The objective of this work is to develop pre- processing techniques that enable an HRAP to be transformed into an equivalent HRAP of smaller size, thus increasing the size of HRAPs that can be solved exactly. Ó 1998 Elsevier Science B.V. All rights reserved. Keywords: Resource allocation; Preprocessing; Macroactivities 1. Introduction The complexity of certain activity planning problems having limited resources requires that their solu- tion is carried out in two stages. In the first stage the problem is simplified by assigning only some of the resources; as a result, a processing plan for the activities is obtained. In the second stage, the resources (of- ten only one resource) that were not considered in the first stage are assigned to the plan already estab- lished. European Journal of Operational Research 107 (1998) 470–491 * Corresponding author. E-mail: [email protected]. 1 This research was partially supported by the Generalitat Valenciana under contract GV-3310/95. 0377-2217/98/$19.00 Ó 1998 Elsevier Science B.V. All rights reserved. PII S 0 3 7 7 - 2 2 1 7 ( 9 7 ) 0 0 3 4 0 - 8 This problem of assigning an additional resource to planned tasks has been treated in various settings: assignment of machines to planned works (Arkin and Silverberg, 1987; Ruhe, 1991), assignment of drivers to routes (Fischetti et al., 1987), assignment of teachers to classes (Brittan and Farley, 1971; de Werra, 1971; Neufeld and Tartar, 1974; Defrenne, 1978; de Werra, 1985), assignment of courses to planned sessions (de Werra, 1985), assignment of courses to planned exam sessions (Korman, 1979; de Werra, 1985), assignment of homogeneous workers to established work-shifts (Baker, 1974; Ritzman et al., 1976; Marsten et al., 1979; Morris and Showalker, 1983; Bechtold et al., 1991; Li et al., 1991; Loucks and Jacobs, 1991), assignment of heterogeneous workers to tasks with known start and end times (Ford and Fulkerson, 1962; Valls et al., 1996a, b) etc. The majority of these works present problems that fall within the category of NP-Hard problems; only in some specific cases (Ford and Fulkerson, 1962; Arkin and Silverberg, 1987) in which the resource to be assigned is homogeneous, i.e. the resource units are identical, is the problem polynomial. There are various criteria to determine whether a resource should be considered in the first or second stage. Sometimes the resources which are considered the most important (the most costly, the most dicult to acquire, etc.) are considered in the first stage, leaving the resources of secondary importance for the sec- ond stage. A case in point, for example, would be the di€erent importance of the machine and worker re- sources in the planning of a machine workshop. At other times, resources whose deferral would make the problem solvable are left for the second stage. This would be the case, for example, for the scheduling of projects with limited resources when one of the renewable resources is heterogeneous. That is to say, when the units of the resource are di- vided into types in such a way that a certain activity requires units of type i or type j, without distinction, for its completion, while another activity can be carried out by units of type i but not of type j. Take for example a lorry resource, classified into types according to the maximum load that it can transport. A light load could be carried by any type of lorry, while a heavy load could only be carried by lorries of high tonnage. Usually, in the second stage only a single heterogeneous resource is assigned to an established plan in which a determined structure can be identified. The resource units have certain characteristics, but they do not all share the same characteristics. For its completion, each activity requires a resource unit that pos- sesses a determined characteristic. The objective is to find the minimum number of resource units necessary to carry out all the activities of the plan in such a way that two activities whose processing overlaps in time do not have the same resource unit assigned. More generally, we can consider the assignment of whatever number of heterogeneous resources to a pre-determined plan, in such a way that each activity can require possibly more than one unit of each re- source, and with the objective of minimising the total number of resource units used. This problem is known as the Heterogeneous Resource Allocation Problem (HRAP), where there can be considered to be two versions of the same problem depending on the finite or infinite availability of the resource units (Valls et al., 1996b). All the results presented in this paper are valid for both versions of the problem. The HRAP will be defined more precisely in Section 2. If the problem is homogeneous, Ford and Fulkerson (1962) present a polynomial procedure to assign the minimal number of resource units to meet a fixed schedule of tasks. However, Valls et al. (1996a) show in the context of a machine workshop, that the HRAP is NP-Complete, and they present a branch and bound algorithm able to solve small and medium size HRAP instances. Roughly speaking one can say that prob- lems up to 100 activities are solvable (in less than 1500 s) whereas only very few problems with more than 120 activities can be solved (consuming tens of thousands of CPU seconds). So there is a computational ‘‘barrier’’ somewhere between 100 and 120 activities that even a small reduction in the number of activities could cross. Furthermore, Valls et al. (1996b) present a heuristic algorithm for the Restricted Vertex Col- ouring Problem based on tabu thresholding able to obtain good solutions of HRAP instances up to 300 activities in just few minutes. V. Valls et al. / European Journal of Operational Research 107 (1998) 470–491 471 The objective of this work is to develop pre-processing techniques that enable an HRAP to be trans- formed into another equivalent HRAP of smaller size, thus not only increasing the size of HRAPs that can be solved exactly but also decreasing by an order of magnitude the time needed to solve big problems. For simplicity, we will limit the discussion to the case in which each activity requires a single resource unit. In Section 5 we will indicate how the results can be applied to the general case. The rest of the paper is organised as follows. In Section 2 we define the HRAP and introduce definitions and the notation to be used throughout the paper. In Section 3 we present some criteria to identify sets of activities that can be eliminated from the original problem P in such a way that the optimal solution to P can be obtained from an optimal solution to the reduced problem. In Section 4 we present di€erent tech- niques to cluster activities into macroactivities, in this way introducing a new HRAP of smaller size equiv- alent to the original P. In Section 5 we o€er some concluding remarks. Finally, in Appendix A we present the proofs of the theorems. 2. The heterogeneous resource allocation problem The HRAP can be described as follows: let us consider a Plan characterised by the set of activities A that make it up, and the starting and finishing times of each activity a, sa and fa, respectively. It is assumed, without loss of generality, that mina2A sa ˆ 0. Each activity must be carried out by a single resource, but not all the resource units can perform all the activities. Because the set of resources R is heterogeneous, it is partitioned into k types, T1; . . . ; Tk; where each type Ti has a set of activities Ai it can be assigned to. In other words Ai is the set of activities each resource of type Ti can operate and 9i; j such that Ai \ Aj 6ˆ [. We can consider two versions of the problem, Bounded_HRAP or Unbounded_HRAP, in the context of finite or infinite resources units of each type: if a type Tk exists with a finite number of units, the problem is Bounded. The objective is to find the minimum number of resource units necessary to carry out all the ac- tivities within the plan, such that two activities whose processing overlaps in time do not have the same resource unit assigned. In this context, given a set of resource units Q � R and a set of activities S � A, we define a Resource Allocation (RA) of Q to S as the assignment, to each activity within S, of a resource unit of the set Q, such that the resource unit is capable of processing the activity, and the same unit is not assigned to two activities that overlap within the schedule. A subset Q of R is a solution if an RA exists of Q to the ac- tivities in A. Clearly, in Q there can be various resource units of the same type, and the same solution Q can have various RAs associated with it. A solution Q is optimal if there is no other solution with fewer resource units. Example 1. Let us consider the Plan represented by the Gantt chart of Fig. 1. A heterogeneous resource is assumed, made up of two resource types T1 and T2, such that: A1 ˆ f5; 6; 7; 8; 9; 10; 11g and A2 ˆ f1; 2; 3; 4; 10; 11g. It is also assumed that R contains as many units of each type as are nec- essary. A unit of type T1 and two units of type T2 define a solution Q (Q ˆ fT1; T2; T2g), since it is a subset of R and the following RA can be made of Q to the set of activities within the Plan: assign a type T1 resource to the activities 5–9; a type T2 to activities 10, 2, 3, 4, and a type T2 to activities 1, 11. This RA is not unique, since we could have assigned a type T1 to 5, 10, 6, 7, 8, 9; a type T2 to 11, 2 and a type T2 to 1, 3, 4, obtaining a new RA of Q to the plan activities. Q ˆ fT1; T2g � R is also a solution, since in the associated RA T1 processes the activities 5, 10, 6, 7, 8, 9 and T2 the activities 1, 11, 2, 3, 4. Besides, as there are two concurrent activities, each solution will have to use at least two resource units, and so fT1; T2g is an optimal solution. 472 V. Valls et al. / European Journal of Operational Research 107 (1998) 470–491 Throughout the remainder of this work we will use the following notation: P is the HRAP defined by the set of activities A and the set of resources R; Lk, Uk, are lower and upper bounds for the units of each type of resource Tk, respectively; and L and U are lower and upper bounds on the total number of resources, res- pectively. In Valls et al. (1996a) and Quintanilla (1994) di€erent techniques are described to obtain lower and upper bounds for an HRAP. The concepts defined as follows will also be used: Definition 1 (L_Bounded_Types). L Bounded Types ˆ fTk such that Lk > 0g. (Resource types such that in each solution there is at least one unit of each type). Definition 2 (Levelk…I†). Given a time interval I and a type Tk, we define Levelk…I† ˆ max jSj such that S � Ak and \ a2S ‰sa; fa‰ ! \ I 6ˆ [ ( ) : (Maximum number of activities within Ak that are concurrent within I). Definition 3 (T …a†). Let a 2 A, we define T …a† ˆ fTk such that a 2 Akg. (T …a† is composed of those resource types that are able to process the activity a). Definition 4 (OBk). OBk ˆ fa 2 A such that T …a† ˆ Tkg. (OBk is composed of the activities that can only be processed by Tk). Definition 5 (Closure of an activity: CI…a†). Let a 2 A, we define CI…a† ˆ fb 2 A such that ‰sa; fa‰\‰sb; fb‰6ˆ [ and T …a† \ T …b† 6ˆ [g. (CI…a† is composed of a, and the activities that overlap with it and share a resource type). Definition 6 (Reduced closure of an activity: CI�…a†). Let a 2 A, we define CI�…a† ˆ CI…a† ÿ fag. (CI�…a† is composed of the activities that overlap with a and share a resource type). Definition 7 (Makespan). makespan ˆ maxa2A fa. Definition 8 (Overlapping of activities). Let S ˆ fa1; a2; . . . ; ang � A. We say that the activities overlap if Tn iˆ1 sai ; fai ‰‰ 6ˆ [. (n activities overlap if there is an instant in which the n activities are being processed). Fig. 1. Plan. V. Valls et al. / European Journal of Operational Research 107 (1998) 470–491 473 3. Reduction of activities In this section, the objective is to search for subsets of activities that can be eliminated from the problem P, while guaranteeing that the optimal solution to the original problem can be obtained directly from the optimal solution to the reduced problem P0. A first result shows that, if a set of activities C has the same reduced closure and all the resource types that can process one of them can also process the rest, all but this activity within C can be eliminated from P. Theorem 1. Let C � A such that CI�…u† ˆ CI�…v† 8u; v 2 C and 9a 2 C such that T …a† � T8c2C T …c†. Let P 0 be the HRAP defined by the set of activities …A–C† [ fag and the set of resources R. If Q0 is an optimal solution to P 0, then Q0 is also an optimal solution to P. Theorem 2 deals with the reduced problem P0 that is obtained by eliminating certain of the activities that could be processed by Tk such that, during the scheduled activity interval of each of them, there are no more than Lk activities that can be processed by Tk. If there were not Lk overlapping activities from OBk in P0, then Lk fictitious activities would be added to P0 to guarantee that each solution of the new problem con- tains at least Lk units of type Tk. Theorem 2. Let Tk 2 L Bounded Types; let C ˆ fa 2 Ak such that Levelk…‰sa; fa‰†6 Lkg. If 9S ˆ fa1; a2; . . . ; aLkg � OBk \ …Aÿ C† such that TLk iˆ1 sai ; fai ‰‰ 6ˆ [, let A0 ˆ Aÿ C. In the other case, we define a new set of activities S ˆ fa1; a2; . . . ; aLkg with ‰sai ; fai ‰ˆ ‰makespan;makespan‡ 1‰ and T …ai† ˆ fTkg8i ˆ 1; . . . ; Lk. Let A0 ˆ …Aÿ C† [ S. Let P 0 be the HRAP defined by the set of activities A0 and the set of resources R. If Q0 is an optimal solution to P 0, then Q0 is also an optimal solution to P. Finally, the question of whether it is possible to eliminate any set of activities C that can be processed only by Tk is examined. Theorem 3 shows that the answer is yes if no two of them overlap at any moment within their sequence and there is no activity a that could be processed by Tk and that is in process at any instant t in which no activity in C is in process. The last theorem of this section shows that, if the reduced problem P0 is constructed by eliminating the activities within C and a unit of type Tk from R, the optimal solution to the original problem P is obtained by adding a single resource unit of type Tk to the reduced problem optimal solution. Theorem 3. Let C � OBk such that sc; fc \ sd ; fd ‰‰‰‰ ˆ [ 8c; d 2 C and S c2C sc; fc ˆ ‰0;‰‰ makespan‰ÿS t1; t2 = 9= a 2 Ak;‰‰f : sa; fa \ t1; t2 6ˆ [‰‰‰‰ :g. Let P 0 be the HRAP defined by the set of activities A–C and the set of resources Rÿ frg, where r is a unit of type Tk. If Q0 is an optimal solution of P 0 then Q0 [ frg is an optimal solution of P. The application of these theorems allows us to obtain an optimal solution to P from an optimal solution to the reduced problem. In the proofs of Theorems 1–3, it is shown how to construct an associated RA. We also point out that the three theorems can be applied iteratively until no further activities can be eliminated. 4. Clustering activities into a single activity: Macroactivity This section takes as its objective the reduction of the number of activities, examining criteria that allow the grouping of various consecutive activities that can be processed by the same types of resources into a 474 V. Valls et al. / European Journal of Operational Research 107 (1998) 470–491 single ‘‘macroactivity’’; and demonstrating that, in the search for the optimum solution, it is possible to substitute a set of macroactivities for a set of activities. To reach this objective, a partition of the set of activities A in sequences will be constructed. A sequence will be formed by a set of activities that do not overlap with one another, and that can be processed by exactly the same types of resources. Associated with the partition into sequences, a partition of the time interval [0, makespan[ into periods will be sought fulfilling the following condition: to each solution of problem P, an RA can be associated in which the state of the resource units stays constant in all the partition periods, with the understanding that a resource unit changes state when it changes sequence, moves from a resting state to process an activity, or returns from an active to a rest- ing state. In this way two activities that are scheduled on the same sequence and in the same period could be as- signed to the same resource unit. Then, we can continue clustering activities on the same sequence until the end of an activity coincides with the end of the period (a macroactivity). This procedure represents the process of partitioning A into sequences, together with the partitioning of [0, makespan[ into periods. Finally, the HRA problem P0 is constructed by replacing the set of activ- ities A by the set of macroactivities within the problem P. These macroactivities are defined by the se- quences and by the partition into periods. It is shown that any optimal solution of P0 is also an optimal solution of P. 4.1. Construction of the partition of A into sequences Let C1;C2; . . . ;Cz be the partition of A given by the activities that can be processed by exactly the same types of resources. If no two activities overlap in any member of the partition, then C1;C2; . . . ;Cz is the set of sequences. Otherwise, let ni be the maximum number of activities that overlap in Ci. Thus, a partition of Ci can be constructed in sequences C1i ;C 2 i ; . . . ;C ni i (Ford and Fulkerson, 1962) such that two activities of C j i do not overlap, 8j ˆ 1; . . . ; ni. C11 ;C21 ; . . . ;Cn11 ;C12 ;C22 ; . . . ;Cn22 ; . . . ;C1z ;C2z ; . . . ;Cnzz is the set of sequences. This par- tition may not be unique. In the remainder of this work we assume that a partition S1; S2; . . . ; Sm into sequences has been selected. Definition 9 (S…a†). S…a† is the sequence that a belongs to. Definition 10 (T …S†). Let S be a sequence. We define T …S† ˆ fTk such that if S ˆ S…a† then a 2 Akg. …T …S† is composed of those resource types that are able to process the activities within S†. Example 2. Let us consider the PLAN and the set of workers shown in Example 1. In this case, activities 1–4 can be carried out by T2, activities 5–9 can be carried out by T1, and 10 and 11 can be carried out by T1 and T2. Thus, C1; . . . ;Cz ˆ f1; 2; 3; 4g; f5; 6; 7; 8; 9g; f10; 11g. Furthermore, each one of the sets is a sequence, and there are no two activities overlapping in any of them. Then in this case we have a unique partition into sequences: S1 ˆ f1; 2; 3; 4g, S2 ˆ f5; 6; 7; 8; 9g, S3 ˆ f10; 11g. On the other hand, if all the activities of Fig. 1 could be processed by T1 and T2, then we would have a unique set C1 ˆ f1; 2; 3; 4; 5; 6; 7; 8; 9; 10; 11g, with n1 ˆ 2. A possible decomposition of C1 into sequences would be S1 ˆ f1; 11; 2; 3; 4g, S2 ˆ f5; 10; 6; 7; 8; 9g. Another possible decomposition would be S1 ˆ f1; 11; 2; 3; 7; 8; 9g, S2 ˆ f5; 10; 6; 4g. V. Valls et al. / European Journal of Operational Research 107 (1998) 470–491 475 4.2. Construction of the partition of [0, makespan[ into periods Definition 11 (initial partition). The Initial Partition is the partition into periods of [0, makespan[ which coincide with the start or end times of each sequence including the start and end times of inactive periods within a sequence (see Fig. 2). Definition 12 (Admissible partition). A partition fP1; P2; . . . ; Phg of the interval [0, makespan[ is admissible if to each solution of problem P and RA can be associated fulfilling: If a, b are activities such that S…a† ˆ S…b† and if P is a period of the partition such that ‰sa; fa‰\P 6ˆ [ and ‰sb; fb‰\P 6ˆ [ then activities a and b have the same resource unit assigned. Definition 13 (Macroactivity). Given a partition of the makespan, a macroactivity is a maximal subset of activities (a1; a2; . . . ; ak) fulfilling the following conditions: 1. All activities in a macroactivity belong to the same sequence S. 2. sai ˆ faiÿ1 8i ˆ 2; . . . ; k. 3. sa1 is the start of a period, fak is the end of a period. 4. If jT …S†j 6ˆ 1, the start of a period coincides with the start of no activity but the first …a1†. Given a partition of [0, makespan[ into periods, the set of macroactivities is unique and constitutes a partition of A. Definition 14 (MAC). MAC is the set of macroactivities. Definition 15 …m…a††. m…a† is the macroactivity that a belongs to. Example 3. Let us consider again the PLAN and the set of resources shown in Example 1. Fig. 2 shows the set of sequences and the initial partition fP1; P2; . . . ; P8g. We can see the fixed assign- ments (i.e. the activities that can only be processed by one type of resource) marked in grey and black. The macroactivities associated with the Initial Partition are: 1, 2-3, 4, 5, 6-7-8-9, 10-11. The optimal solution is made up of a resource unit of each type. The resource in type T1 is the only one free to process activity 10, and the resource unit in type T2 is the only one free to process activity 11. There- fore, activities 10 and 11 that are scheduled in the same period (P4) and belong to the same sequence …S3† require two di€erent resource units (the Initial Partition is not admissible). Hence, at the moment 10 and 11 cannot be grouped into a single macroactivity to solve the HRAP. Fig. 2. Initial partition. 476 V. Valls et al. / European Journal of Operational Research 107 (1998) 470–491 Thus, in this example, an admissible partition must be a refinement of the initial partition; we will show the procedure to obtain it, below. Clearly, an admissible partition must be either the Initial Partition or a refinement of the Initial Parti- tion, given that in this partition at least one sequence goes from being active to inactive or vice versa from one period to the next, and so at least one resource unit will change its work-state. The following procedure forms an admissible partition of the interval [0, makespan[. Partitioning procedure 1.- Let Partition ˆ fP0; P1; P2; . . . ; Phg be the Initial Partition. Set flagˆ 0. 2.- (Subdivision of a period): 8P ˆ ‰t1; t2‰2 Partition, If f9a; b 2 A such that: (1) (Condition on a) 1.1 t1 < fa < t2. 1.2 a is scheduled in two or more periods. (2) (Condition on b) 2.1. S…a† 6ˆ S…b†. 2.2. T …a† \ T …b† 6ˆ [. 2.3. fa6 Sb < fm…a†. } Then, fPartition ˆ Partitionÿ fPg [ f‰t1; fa‰; ‰fa; t2‰g set flag ˆ 1: } 3.- If flagˆ 1, then set flag ˆ 0 and go to 2. Otherwise STOP. Example 4. In the example of Fig. 2, the period P4 satisfies the conditions to be subdivided …a ˆ 10, b ˆ 6† at the instant f10, giving a new partition made of nine periods. No other period fulfils the condition to be sub-divided. The set of macroactivities will now be 1, 2-3, 4, 5, 6-7-8-9, 10 and 11. Theorem 4. Let P 0 be the HRAP defined by the set of macroactivities associated with the partition obtained through the partitioning procedure and the set of resources R. Q is a solution for P 0 () Q is a solution for P. Corollary 1. Let P 0 be the HRAP defined by the set of macroactivities associated with the partition obtained through the partitioning procedure and the set of resources R. Q is an optimal solution for P 0 () Q is an optimal solution for P. Next we will demonstrate that new conditions can be incorporated into the condition for subdividing a period in such a way that the partition obtained continues to be admissible. The objective is to obtain an admissible partition with the least periods and, therefore, the least macroactivities. Theorem 1 is based on the following idea. In Example 3, activities 1 and 10 are overlapped, activity 1 can be processed only by type T2, and the optimal solution contains a unit of each type …T1 and T2†; then activity a ˆ 10 has to be processed by unit T1. Activity b ˆ 6 starts before the end of m…10† and can only be pro- cessed by type T1. So, the resource unit that processes activity a ˆ 10 has to go on to process b ˆ 6, and it is essential to subdivide the period in which ‘‘a’’ finishes at the instant that this activity ends. So now, if from the start of m…a† until the end of ‘‘a’’ there is no sequence that shares a resource type with S…a†, S…a† can be V. Valls et al. / European Journal of Operational Research 107 (1998) 470–491 477 carried out, from the start of m…a† until the instant ‘‘a’’ finishes, by any resource type and the sub-division will not have to be done. Theorem 5. If in the ‘‘condition on a’’ conditions 1.1–1.3 are considered, where: 1:3 9= n 2 MAC-fm…a†g such that ‰sn; fn‰\‰sm…a†; fm…a†‰6ˆ [ and T …n† \ T …a† 6ˆ [: then Theorem 4 and Corollary 1 continue to be true. If in the process of sub-division jT …S…a††j ˆ 1, then the decomposition of S…a† into macroactivities does not depend on the partition into periods considered, and so is unique. Furthermore, throughout the optimal solution, the activities of the same macroactivity of S…a† can be processed by a single resource unit. This makes it unnecessary to sub-divide m…a† at the instant ‘‘a’’ ends. Theorem 6. If in the ‘‘condition on a’’ conditions 1.1–1.4 are considered, where: 1:4: jT …a†j 6ˆ 1 then Theorem 4 and Corollary 1 continue to be true. Theorems 7–9 present conditions that permit the identification of macroactivities that can be eliminat- ed during the solution of the HRAP defined by the macroactivities, given that it is certain that, for which- ever optimal solution to the problem under consideration, there is a resource unit that could process each macroactivity eliminated. If, in the process of sub-division, ‘‘a’’ and ‘‘b’’ are the activities that fulfil the con- dition for sub-division, and if m…a† or m…b† can be eliminated, then it will not be necessary to sub-divide the period. Theorem 7. If in the ‘‘condition on a’’ conditions 1.1–1.5 are considered, and in the ‘‘condition on b’’ conditions 2.1–2.4 are considered, where: 1:5: 9= Tk 2 T …a† \ L Bounded Types such that Levelk…‰sm…a†; fm…a†‰†6 Lk 2:4: 9= Tk 2 T …b† \ L Bounded Types such that Levelk…‰sm…b†; fm…b†‰†6 Lk then Theorem 4 and Corollary 1 continue to be true. Definition 16 (Closure of a macroactivity: CI…m†). Let m be a macroactivity, then we define CI…m† ˆ fu 2MAC such that ‰sm; fm‰\‰su; fu‰6ˆ [ and T …m† \ T …u† 6ˆ [g. (CI…d† is composed of d and the macroactivities that overlap with it and share the same resource type). Theorem 8. If in the ‘‘condition on a’’ conditions 1.1–1.6 are considered, and in the ‘‘condition on b’’ conditions 2.1–2.5 are considered, where: 1:6: X Lk k=Tk2T …a†\L Bounded Types < u 2 CI…m…a††=T …u† \ L Bounded Types 6ˆ [f gj j; 2:5: X Lk k=Tk2T …b†\L Bounded Types < u 2 CI…m…b††=T …u† \ L Bounded Types 6ˆ [f gj j; then Theorem 4 and Corollary 1 continue to be true. 478 V. Valls et al. / European Journal of Operational Research 107 (1998) 470–491 Theorem 9. If in the ‘‘condition on a’’ conditions 1.1–1.7 are considered, and in the ‘‘condition on b’’ conditions 2.1–2.6 are considered, where: 1:7: 9u 2 CI…m…a†† such that su 2Šsm…a†; fm…a†‰ or [ u2CI…m…a†† T …u† 6� T …a†; 2:6: 9u 2 CI…m…b†† such that su 2Šsm…b†; fm…b†‰ or [ u2CI…m…b†† T …u† 6� T …b†; then Theorem 4 and Corollary 1 continue to be true. Theorem 10 presents another situation in which the sub-division of a period is not necessary. Be- fore the theorem, we introduce a series of definitions to help to formalise the new condition that can be imposed: Definition 17 …P16 P2†. Given two periods P1 ˆ ‰i1; j1‰ and P2 ˆ ‰i2; j2‰; we say that P16 P2 if j16 i2. Definition 18 …SA…P ††. Given a period P , we define SA…P † ˆ fsequences S such that 9a 2 A=S…a† ˆ S and ‰sa; fa‰\P 6ˆ [g. (SA…P † is the set of sequences that are in process in P). Definition 19 …Z…P ††. Given a period P , we define: Z…P † ˆ fS 2 SA…P † such that jT …S†j > 1g. (Z…P † is the set of sequences of SA…P † that can be processed by more than one type of resource). Definition 20 (RP : sequences linked by resource in a period). Given a period P and S; S0 2 Z…P †, we say that S RP S0 () 9S1 ˆ S; S2; S3; . . . ; Sj ˆ S0 2 Z…P † such that T …Si† \ T …Si‡1† 6ˆ [. (SRP S0 if S and S0 belong to Z…P † and are connected by a succession of sequences from Z…P † in such a way that each one shares a resource type with its successor). Definition 21 …Z…P ; S††. Given a period P and S 2 Z…P†, we define Z…P ; S† ˆ fS0 2 Z…P † such that SRP S0g. (Z…P ; S† is the set of sequences linked by resource in P to S). Definition 22 …Z…P ; S††. Given a period P and S 2 Z…P †, we define Z…P ; S† ˆ fS0 2 SA…P † such that T …S0† \ Ss2Z…P ;S† T …s†� � 6ˆ [g. …Z…P ; S† is the set of sequences that do not belong to SA…P †, and that do not share a resource type with any other sequence of Z…P ; S††. Theorem 10. If in the ‘‘condition on a’’ conditions 1.1–1.7 are considered, in the ‘‘condition on b’’ conditions 2.1–2.6 are considered, and also the following condition: 9= P2 ˆ ‰t3; t4‰P P ˆ ‰t1; t2‰ such that f9c 2 A such that sc 2 ‰t2; t3Š and S…c† 2 Z…P ; S…a†† or 9c 2 A such that S…c† 2 Z…P ; S…a††; sc < t4 and fc > t4g then Theorem 4 and Corollary 1 continue to be true. 5. Final remarks In this work we present a series of results which make it possible to reduce the set of activities of an HRAP for the case in which each activity requires a single unit of a single heterogeneous resource. In doing so, we first present some criteria to identify sets of activities that can be eliminated from the original prob- V. Valls et al. / European Journal of Operational Research 107 (1998) 470–491 479 lem P, in such a way that the optimal solution to P can be obtained from the optimal solution to the re- duced problem. Then we present di€erent techniques to cluster activities into macroactivities, in this way introducing a new HRAP of smaller size equivalent to the original P. Nevertheless, all the results are applicable to the general case. If, in an HRAP, an activity a requires various units of a single heterogeneous resource, it is possible to decompose a into as many activities as there are units required. Each one of the new activities will be carried out in the interval ‰sa; fa‰, and will need a resource unit belonging to T …a†. The optimal solution to the HRAP thus defined will be an op- timal solution to the original problem. In addition, if there are di€erent heterogeneous resources (for ex- ample, lorries, workers, machines, etc.), the minimisation of the total number of resource units used is equivalent to minimising the number of units of each resource, since the original problem can be decom- posed into as many sub-problems as there are heterogeneous resources. Each sub-problem will be as- signed a di€erent resource and it will be defined by the set of activities that requires one or more units of this resource. Each optimal solution to the original problem will directly coincide with the union of the optimal solutions of the separate sub-problems (there being one optimal solution for each sub- problem). There are some comments worth noting regarding the application of these results. To transform an in- stance of the HRAP into a smaller equivalent one, it is first necessary to apply the theorems of Section 3 repeated iteratively while the hypothesis remains true, eliminating activities and their corresponding re- source units. The resulting instance must then be decomposed into sequences, thus obtaining, by the par- titioning procedure, a set of macroactivities. The partitioning procedure considers if some period P fulfils the conditions to be sub-divided and, for this, it must find an ‘‘a’’ or ‘‘b’’ associated with the period P fulfilling the ‘‘conditions on a and b’’, respec- tively. If a period has not been sub-divided, it is not considered any more; otherwise, each one of the new periods must be studied. Note that given an activity ‘‘a’’ which fulfils the ‘‘condition on a’’, there can exist more than one activity ‘‘b’’ fulfilling the ‘‘condition on b’’. However, it is evident that in the process of sub-division, it is necessary only to keep in mind those ac- tivities ‘‘b’’ that fulfil the ‘‘condition on b’’ and that, moreover, they are the first activities of a macroactiv- ity. Consequently, if activity ‘‘b’’ does not fulfil the condition, neither will the subsequent activities in the macroactivity. Thus, the partitioning procedure depends on the partition into sequences, on the order in which the pe- riods are studied, and on the choice of activity ‘‘a’’, if there are various activities that satisfy the ‘‘condition on a’’ in the same period. The application of Theorems 1 and 2 of Section 3 can be done simultaneously in one pass along the activities whereas Theorem 3 requires another pass. In both passes, simple ‘‘bookkeeping’’ operations have to be carried out. The same applies to the partitioning procedure. Given the simplicity of the re- quired calculations, it is apparent that the computational e€ort for the pre-processing procedure will be a small fraction of the CPU time that is now necessary to solve problems with more than 120 activ- ities. To get a flavour about the power of this approach we have applied these pre-processing techniques to four HRAP instances with 25, 49, 85 and 87 activities respectively from the test problems described in Valls et al. (1996a). The reduction in the number of activities was of 68%, 18.36%, 20% and 5.74% respectively. Obviously, these results apply only to the four problems tested and to a specific implementation of the pre- processing techniques but they seem to indicate that significant reductions on problem size could be ob- tained. The authors are currently working to determine the best implementation strategies and to measure the e€ect of problem parameters on size reduction. 480 V. Valls et al. / European Journal of Operational Research 107 (1998) 470–491 Appendix A Definition A.1 …W …a††. Let a 2 A, and W an RA, then we define W …a† as the resource unit that is assigned to a in W . Definition A.2 …Qk†. Let Q � R. Qk ˆ fr 2 Q such that r is of type Tkg. Definition A.3 …qk†. Let Q � R. qk ˆ jQkj. A.1. Proof of Theorem 1 For Q0 to be a solution of P 0, there exists a resource allocation W 0 of Q0 to the activities of A0 ˆ …Aÿ C† [ fag. We are going to prove by reductio ad absurdum that the assignment W of Q0 to the activities of A defined according to: W …x† ˆ W 0…x† 8x 2 A0; W …x† ˆ W 0…a† 8x 2 C ÿ fag is an RA and thus Q0 is a solution of P. As T …a† � Tc2C T …c†, W 0…a† is a resource unit of a type capable of processing all the activities of C ÿ fag. Thus, the assumption that W is not an RA implies that 9b; c 2 A such that ‰sb; fb‰\‰sc; fc‰6ˆ [ and W …b† ˆ W …c†. As W 0 is an RA and W …x† ˆ W 0…x† 8x 2 A0, two activities of A0 that overlap with one another cannot have the same resource unit assigned in W . Therefore, b and c cannot simultaneously belong to A0. Two activities of C ÿ fag have the same reduced closure and, therefore, do not overlap since if they did, each one of them would belong to the reduced closure of the other, and both reduced closures would not be equal. Therefore b and c cannot simultaneously belong to C ÿ fag. As A ˆ A0 [ …C ÿ fag† and A0 \ …C ÿ fag† ˆ [, then b 2 C ÿ fag and c 2 A0 (or vice versa): If b 2 C ÿ fag; W …b† ˆ W 0…a†. If c 2 A0; W …c† ˆ W 0…c†. Then, W 0…c† ˆ W …c† ˆ W …b† ˆ W 0…a†, so W 0 cannot be an RA given that a and c overlap …c 2 CI�…b† ˆ CI�…a††. Thus, Q0 is a solution of P. Furthermore, as P0 was obtained by eliminating a set of activities from P, every optimal solution of P will contain at least as many resource units as the optimal solution of P0, and so Q0 is an optimal solution of P. � A.2. Proof of Theorem 2 For Q0 to be a solution of P0, there exists a resource allocation W 0 of Q0 to the activities of A0. Let Ck ˆ fx 2 A0 such that W 0…x† is of type Tkg. To construct A0 and for Q0 to be a solution of P0, in A0 there are at least Lk activities of Ck overlapping, then q0k P Lk. As W 0 is an RA of Q0 to the activities of A0, there are at most q0k activities overlapping in Ck. Furthermore, as Levelk…‰sa; fa‰†6 Lk 6 q0k 8a 2 C, there are at most q0k activities overlapping in Ck [ C. V. Valls et al. / European Journal of Operational Research 107 (1998) 470–491 481 Therefore, the results of Section 9, Chapter 2 of the book of Ford and Fulkerson (1962), guarantee that there exists an RA, W 00, of Q0k to the activities of Ck [ C. Thus, the assignment of Q0 to A defined accord- ing to: W …x† ˆ W 00…x† 8x 2 Ck ÿ S; W …x† ˆ W 0…x† 8x 2 Aÿ Ck is and RA of Q0 to A. Then Q0 is a solution of P. As every solution of P is a solution of P0, and P and P0 have the same objective function, then Q0 is an optimal solution of P. � A.3. Proof of Theorem 3 For Q0 to be a solution of problem P0, there exists a resource allocation W of Q0 to the activities of A0. Let Q ˆ Q0 [ frg. Let W be the assignment of Q to the activities of A defined according to: W …x† ˆ W 0…x† 8x 2 Aÿ C; W …x† ˆ r 8x 2 C: Evidently, W is an RA of Q to the activities of A, and so Q is a solution of P; furthermore the condition is fulfilled whereby the optimal value of P6 the optimal value of P0 ‡ 1. We will see that Q is optimal. Let Q00 be a solution of problem P and W 00 an RA of Q00 to the activities of A. The maximum number of activities in A that overlap and are assigned to type Tk is q00k . The activities of C will be assigned to type Tk, and as S c2C‰sc; fc‰ˆ ‰0;makespan‰ÿ t1; t2 = 9= a 2 A; sa; fa \ t1; t2 6ˆ [‰‰‰‰‰‰f g, the maximum number of activities in A–C that overlap and are assigned to type Tk is q00k ÿ 1. Therefore, applying the results of Ford and Fulk- erson (1962), we obtain a solution of P0 with jQ00j ÿ 1 resource units, and the optimal value of P06 optimum value of Pÿ 1. Therefore, the optimal value of P ˆ the optimal value of P0 ‡ 1, and Q is an optimal solution of P. � Lemma A.1. At every instant t, the number of activities that are in process in t is the same as the number of macroactivities that are in process in t. This is evident, since the macroactivities are sets of activities that are processed consecutively and with- out interruption. � Lemma A.2. Let Q be a solution of P. Then, there exists an RA of Q to the activities of A such that, in the sequences that can be processed by a single resource type, all the activities of the same macroactivity have the same resource unit assigned. Given that Q is a solution of P, there exists a resource allocation W of Q to the activities of A. From W we are going to construct a resource allocation W 0 of Q to the activities of A that satisfies the required prop- erty. Let X ˆ fm 2MAC such that jT …m†j ˆ 1g. Given Qk 6ˆ [, let: Xk ˆ fx 2 X=T …x† ˆ fTkgg (macroactivities of X that can only be processed by type Tk). Ck ˆ fa 2 …AÿOBk†=W …a† 2 Tkg 482 V. Valls et al. / European Journal of Operational Research 107 (1998) 470–491 (set of activities to which W assigns a unit of type Tk, but which could be processed by another type). pk ˆ maxfjCj such that C � …Xk [ Ck† and \ c2C ‰sc; fc‰6ˆ [g (pk ˆ maximum number of elements of Xk [ Ck that are processed simultaneously). So, applying Lemma A.1 pk ˆ maxfjCj such that C � …OBk [ Ck† and \ c2C ‰sc; fc‰6ˆ [g: (pk ˆ maximum number of elements of OBk [ Ck that are processed simultaneously). As W is an RA of Q to the activities of A, then pk 6 qk. Therefore, the results of Ford and Fulkerson (1962) guarantee that a resource allocation W 00k of Qk to the activities of Xk [ Ck exists, that satisfies the required property. Then, the assignment of Q to A defined according to: W 0…x† ˆ W 00k …x† 8x=m…x† 2 Xk or x 2 Ck; W 0…x† ˆ W …x† 8x=m…x† 62 X and x 62 Ck is an RA of Q to A that satisfies the required property. � A.4. Proof of Theorem 4 If Q is a solution of P0, Q is, by nature, a solution of P. Let Q be a solution of P. We will prove that Q is a solution of P0; i.e. there exists an RA of Q to the activities of A that possesses the following property: all the activities of a macroactivity have the same resource unit assigned. Given that Q is a solution of P, there exists a resource allocation W of Q to the activities of A fulfilling the previous Lemma. From W we will construct a resource allocation W 0 of Q to the activities of A that satisfies the required property. Consider the following partition of the set of macroactivities: MAC ˆ X [ Y [ Z;where: X ˆ fm 2MAC such that jT …m†j ˆ 1g; Y ˆ …fm 2MAC included in a single period …‰sh; fh‰� P †g [ fm 2MAC made up of a single activityg† ÿ X ; Z ˆMAC ÿ X ÿ Y : W 0 is constructed in the following way: 1. The activities belonging to macroactivities of X receive the same assignment in W 0 as in W . 2. Reassignment to the elements of set Y . 8m 2 Y : Let i…m† be the last activity of m. Reassign all the activities of the macroactivity m with the assignment which i…m† had in W . 3. Reassignment to the elements of set Z. 8m 2 Z: Let i…m† be the first activity of m that is scheduled in various periods. Reassign all the activities of the macroactivity m with the assignment which i…m† had in W . V. Valls et al. / European Journal of Operational Research 107 (1998) 470–491 483 Since, in the construction of W 0, only the units of Q have been used, and each macroactivity has the same resource unit assigned, it will only be necessary to prove that W 0 does not assign the same resource unit to two macroactivities that overlap with one another. We will prove it by reductio ad absurdum. We assume that there exist two macroactivities h; t such that: 1. ‰sh; fh‰\‰st; ft‰6ˆ [. 2. W 0…h† ˆ W 0…t†. As W is an RA and the macroactivities of X receive in W 0 the same assignment as in W ; h and t cannot be- long to X simultaneously. Three cases are identified: Case A: h 2 Y and t 2 Y . We will see that we arrive at a contradiction by proving that the activities, i…h† and i…t†, overlap with each other and have the same resource unit assigned in W : Given that h; t 2 Y and ‰sh; fh‰\‰st; ft‰6ˆ [, there exists an interval P ˆ ‰t1; t2‰ such that fh ˆ ft ˆ t2 from which ‰si…h†; fi…h†‰\‰si…t†; fi…t†‰6ˆ [. Furthermore, following (ii) and given that W 0 assigns the same resource unit to h…t† as W assigns to i…h†…i…t††, then W assigns the same resource unit to i…h† as to i…t†. Case B: …h 2 X and t 2 Y † or …h 2 Y and t 2 X †. We will see that we arrive at a contradiction by proving that two activities, one of h and the other of t, overlap with each other and have the same resource unit assigned in W . We assume that h 2 X and t 2 Y . The other case is analogous. If t is made up of a single activity, it will have the same resource unit assigned in W and W 0. As h 2 X , h has a single resource unit assigned that also coincides in W and W 0. Then, by (i) t and an activity of h over- lap with one another, and by (ii), they have the same resource unit assigned in W . If t is made up of more than one activity, by definition of set Y , it will be scheduled in a single period. So, t has the same resource unit assigned in W 0 as the last activity of t has assigned in W . As h and t mutually overlap, part of h will be scheduled in the same period as t. Therefore at least one activity of h and the last activity of t will overlap and, by (ii), will have the same resource unit assigned in W. Case C: h 2 Z or t 2 Z. In this case, we arrive at a contradiction by proving that a period of the partition exists that fulfils the condition to be sub-divided, but which is impossible given that the partition into pe- riods has been obtained by applying the partitioning procedure. If h or t belong to X , let i…h†…i…t†† be the first activity of h (of t). In the other case, let i…h† and i…t† be the activities considered for the re-assignment of h and t. By (ii), W assigns the same resource unit to i…h† and i…t†, and so i…h† and i…t† cannot mutually overlap. We assume, without loss of generality, that fi…t†6 si…h†. We will prove, by reductio ad absurdum that t 2 Z: If t 2 Y ; i…t† is the last activity of t, and fi…t† is the final instant of a period. It is not possible that fi…t† ˆ si…h† since, in this case, i…h† would be the first activity of the macroactivity h, and so h and t would not overlap. Thus, as h and t do overlap with each other, i…h† cannot be the first activity of h that is sched- uled in at least two periods. Therefore, h 62 Z. If t 2 X , all the activities of t have the same resource unit assigned in W 0. Furthermore, as i…t† and i…h† have the same resource unit assigned in W 0, the last activity of t does not overlap with i…h†. Thus, as h and t overlap, i…h† cannot be the first activity of h that is scheduled in at least two periods. Therefore, h 62 Z. Then, if t 2 Y or t 2 X , h 62 Z, which is impossible since we are in case C. Let ‘‘a’’ be the last activity of the macroactivity t that is scheduled in at least two periods, and that fulfils fa6 si…h†. Activity a exists since i…t† is scheduled in two periods and, furthermore, fi…t†6 si…h†. Let b be the first activity of the macroactivity h that satisfies fa6 sb. The activity b exists now that i…h† fulfils fa6 si…h†. We will see that period P ˆ ‰t1; t2‰ such that t1 < fa6 t2 fulfils the condition to be sub-divided. First we note that h and i…h† begin in the same period. The proof is clear from the definition of the set Y in the case where h 2 Y , or from the definition of i…h† for the set X and Z in the case where h 2 X or 484 V. Valls et al. / European Journal of Operational Research 107 (1998) 470–491 h 2 Z. As, in addition, h and t overlap and fi…t†6 si…h†, part of t will be scheduled in the period in which h starts. 1. Condition on a: 1.1. t1 < fa < t2. From the definition of P, it is only necessary to show that fa 6ˆ t2. If it were to happen that fa ˆ t2, the macroactivity m…a† ˆ t 2 Z would end in t2 (from the definition of macroactivity and the set Z), i.e. ft ˆ t2 ˆ fa. Furthermore, si…h†P fa ˆ t2, and bearing in mind that h and i…h† start in the same period, h and t would not overlap with one another. 1.2. a is scheduled in two or more periods, from the definition of a. 2. Condition on b: 2.1. S…a† 6ˆ S…b† given that a 2 t; b 2 h and, from (i), ‰Sh; fh‰\‰St; ft‰6ˆ [. 2.2. T …a† \ T …b† 6ˆ [ given that, from (ii), h and t have the same resource unit assigned in W 0 and a 2 t; b 2 h. 2.3. fa6 sb < fm…a†. From the definition of b; fa6 Sb. As sh6 sb6 Si…h†, b starts in the same period as h and i…h†. Since part of t ˆ m…a† is scheduled in the same period too, by necessity sb < fm…a†. � A.5. Proof of Corollary 1 This is evident, since P and P0 have the same objective function. � A.6. Proof of Theorem 5 The proof is similar and follows the same steps as Theorem 4, and so we will expound only the points in which the proofs di€er. The new assignment of the elements of set Z is 3. 8m 2 Z: Z1: If 9n 2 MACÿfmg such that ‰Sn; fn‰\‰sm; fm‰6ˆ [ and T …n† \ T …m† 6ˆ [, then i…m† is defined as the first activity of the macroactivity m that is scheduled in various periods and 9n 2 MACÿfmg such that ‰sn; fn‰\‰si…m†; fi…m†; ‰6ˆ [ and T …n† \ T …m† 6ˆ [. (The existence of i…m† is guaranteed by m being a macroac- tivity of set Z, and by all the macroactivities occupying a set of one or more complete periods). Z2: In the opposite case, let i…m† be any one of the activities that contains m. Reassign the assignment that i…m† had in W to all the activities of the macroactivity m. Cases A and B are analogous to the earlier proof. Let us look at case C: Case C: h 2 Z or t 2 Z. In this case, we arrive at a contradiction by also proving the existence of a period of the partition that fulfils the condition to be sub-divided. The macroactivities h and t cannot be in case Z2, by their own definition. Assuming, without loss of generality, that fi…t†6 Si…h†, it is also true that t 2 Z: If it is assumed that t 2 Y or that t 2 X , bearing in mind that t overlaps with h and that T …h† \ T …t† 6ˆ [, the same reasoning of Theorem 4 would bring us to conclude that i…h† cannot be the first activity of h that is scheduled in at least two periods, and that 9n 2 MAC-fhg such that ‰Sn; fn‰\‰Si…h†; fi…h†‰6ˆ [ and T …n† \ T …h† 6ˆ [, then h 62 Z, which is impossible as we are in case C. If a, b and P are defined as in Theorem 4, P fulfils the condition to be sub-divided: First note that h and i…h† begin in the same period. It is true in case that h 2 X [ Y , as it was shown in the proof of Theorem 4. If h 2 Z and it is assumed that in Šsh; fi…h†‰ there is an instant of change of period, as V. Valls et al. / European Journal of Operational Research 107 (1998) 470–491 485 h and t overlap with one another and fi…t†6 si…h†, there will be an activity prior to i…h† in h scheduling it in at least two periods and overlapping it with t, which contradicts the definition of i…h†. Therefore, h and i…h† start in the same period also in this case. Furthermore, following the reasoning of Theorem 4, part of t will be scheduled in the period in which h starts. Conditions 1.1, 1.2, 2.1–2.3 are fulfilled by analogy with the way they are fulfilled in Theorem 4. Fur- thermore, putting n ˆ t fulfils condition 1.3 given that ‰st; fi…t†‰� ‰St; fa‰ˆ ‰sm…a†; fa‰. � A.7. Proof of Theorem 6 The proof is totally analogous to the proof of Theorem 5, given that a 2 t 2 Z, and therefore, jT …a†j > 1. � A.8. Proof of Theorem 7 Lemma A.3. Let Tk 2 L Bounded Types. Let a 2 Ak such that Levelk…‰sa; fa‰†6 Lk. Let Q be a solution of P and W an RA of Q to the activities of Aÿ fag. Thus, there exists an RA of Q to the activities of A in which all the activities of Aÿ fag have the same resource type assigned as in W, and a has a resource of type Tk assigned. The proof is similar to the proof of Theorem 2. � The proof of the theorem is the same as that carried out in Theorem 6, only substituting the set MAC by the set MACÿM1, where M1 ˆ fm 2MAC such that 9Tk 2 T …m† \ L Bounded Types and Levelk…‰sm; fm‰†6 Lkg and bearing in mind that in case C, the period P fulfils the condition to be subdivided. The exception is if P were to satisfy conditions 1.5 or 2.4, but in this case m…a† ˆ t and m…b† ˆ h belong to the set M1 and would not be considered. All the macroactivities of set M1 satisfy the hypothesis of Lemma A.3, therefore if the macroactivities are considered as if they were activities, it is possible to add the macroactivities of M1 to W one-by-one, assigning the corresponding type Tk to them. In this way we would obtain an RA satisfying the require- ments demanded by the theorem. � A.9. Proof of Theorem 8 Lemma A.4. Let a 2 A such that T …a† \ L Bounded Types 6ˆ [ and P LK k=Tk2T …a†\L Bounded Types P fb 2 CI j…a†=T …b† \ L Bounded Types 6ˆ [gj j. Let Q be a solution of P and W an RA of Q to the activities of Aÿ fag. Thus, there exists a resource Tk with Tk 2 T …a† such that if the assignment of this resource unit to the activity a is added to W, the result is an RA of Q to the activities of A. Let A0 ˆ Aÿ fag. As a belongs to its closure and is not assigned in W , some resource unit r of the set Q \ T …a† \ L Bounded Types in W will not be assigned to any activity in ‰sa; fa‰. Then the assignment of Q to A defined according to: W 0…x† ˆ W …x† 8x 2 A0; W 0…a† ˆ r is an RA of Q to the activities A satisfying the requirements set out in the lemma. � 486 V. Valls et al. / European Journal of Operational Research 107 (1998) 470–491 The proof of the theorem is the same as that carried out in Theorem 6, only substituting the set MAC by the set MACÿM1 ÿM2, where: M1 ˆ fm 2MAC such that 9Tk 2 T …m† \ L Bounded Types and Levelk…‰sm; fm‰†6 Lkg; M2 ˆ m 2MAC such that X Lk k=Tk2T …m†\L Bounded Types P jfu 2 CI…m†=T …u† \ L Bounded Types 6ˆ [gj 8 M2 ˆ m 2MAC such that X Lk k=Tk2T …m†\L Bounded Types 8 Let b be the first activity of S scheduled in P :…b can start before P :† ÿ Remove from A0 the set of activities fx 2 A0 such that S…x† ˆ S…b†; sx P sb; and fx6 t4g ÿ Add to A0 a new activity a such that sa ˆ sb; fa ˆ t2: ÿ Set W 0…a† ˆ W …b†: go to 2: We will see that W 0 is an RA of Q to the activities of A0. We assume that W 0 is not an RA, and so there exist two activities x, y of A0 such that: (i) ‰sx; fx‰\‰sy ; fy ‰6ˆ [; (ii) W 0…x† ˆ W 0…y†. We will prove that, accordingly, there exist two mutually overlapping activities of A that have the same resource unit assigned in W . The activities x and y cannot both belong to A since it would mean W …x† ˆ W 0…x† ˆ W 0…y† ˆ W …y†, which is impossible if W is an RA. Let h…c† be defined in the following way: If c 2 A0 \ A; h…c† ˆ c. If c 2 A0 ÿ A then c replaces a set of consecutive activities of A, and h…c† is the first of these activities. It is true that W 0…c† ˆ W …h…c†† 8c 2 A0. Therefore, W …h…x†† ˆ W 0…x† ˆ W 0…y† ˆ W …h…y††, and as W is an RA, it is true that ‰sh…x†; fh…x†‰\‰sh…y†; fh…y†‰ˆ [. We assume, without loss of generality, that fh…x†6 sh…y†. As sy ˆ sh…y† and ‰sx; fx‰\‰sy ; fy ‰6ˆ [, it is true that x 62 A. Let P ˆ ‰t1; t2‰ such that sy 2 P . Let ‰t3; t4‰ be defined such that fh…x† 2 ‰t3; t4‰. Then, as x 62 A, fx ˆ t4. If fh…x†6 sh…y†, this implies t46 t2. Moreover, since ‰sx; fx‰\‰sy ; fy ‰6ˆ [ then fx ˆ t4 ˆ t2, and therefore fh…x† 2 ‰t1; t2‰ and sh…y† 2 ‰fh…x†, t2‰�Št1; t2‰. jT …h…y††j ˆ 1; if it were greater than 1, since sh…y† 2 ‰fh…x†; t2‰� P ; T …h…x†† \ T …h…y†† 6ˆ [, S…h…y†† 2 Z…P ; S…h…x††† and x 9=A; h…y† would have been eliminated in the process of grouping A0, and there- fore h…y† would not exist. Let c be the first activity of A that is scheduled in S…h…y†† and in the period P, then as sh…y† 2Št1; t2‰; h…y† and c belong to the same macroactivity, following the definition of W, W …h…y†† ˆ W …c† and therefore, W …h…x†† ˆ W …c†. Furthermore, h…x† and c are in process at the instant t1. Thus c and h…x† are members of A, overlap with one another, and W …c† ˆ W …h…x††, which contradicts the assumption that W is an RA. Therefore W 0 is an RA of Q to the activities of A0. Let MAC …MAC0† be the set of macroactivities associated with the partition into periods and with the set of activities A…A0†. A proof analogous to that of Theorem 9 allows the armation that there exists a resource allocation W 00 of Q to the activities of A0 that possesses the following property: all the activities of a macroactivity of MAC0 have the same resource unit assigned. In the proof, it is sucient to replace the set MAC by the set MAC0 and to bear in mind that, in case C, period P fulfils the condition to be sub-divided, but from the condition introduced in Theorem 10 it is clear that, on the contrary, activity ‘‘a’’ would have disap- peared from A0 in the grouping process. Thus, if MAC ˆMAC0, let W 000 ˆ W 00 and the theorem is proved. In the opposite case, W 000 is defined by: 8x 2 A \ A0; W 000…x† ˆ W 00…x†; 8x 2 A; x 62 A0; x belongs to a set of consecutive fa1; a2; . . . ; ang � A, that have been substituted by an a…x† 2 A0. Let W 000…x† ˆ W 00…a…x††. From the grouping process it is deduced that fan always coincides with the end of some period and jT …fan†j > 1, therefore, in W 000 each macroactivity has a single resource unit assigned. V. Valls et al. / European Journal of Operational Research 107 (1998) 470–491 489 We will prove, by reductio ad absurdum that the number of activities of MAC assigned, to the same resource type does not exceed the number of units of this type in Q. We assume that a particular type does not fulfil this condition. Let t 2 ‰0;makespan‰ be the earliest instant such that jfm 2MAC=t 2 ‰sm; fm‰ and W 000…m† is of type Tkgj > qk. From the definition of t, t is the start of some period. Let P3 be this period. Let SEC…t; Tk† ˆ fSequences S such that in t; S is processed by a unit of type Tkg. As W 00 is an RA, some of the activities that are scheduled in t and are assigned resources of type Tk must belong to A but not to A0. Let a be the activity belonging to A0 that starts first and that has been grouped with some of the activities that are carried out in t, and that are processed by a resource unit of type Tk. Let P ˆ ‰t1; t2‰ be the period in which a ends. Then P 6 P3 and P 6ˆ P3. Let b be the activity that starts first out of those grouped with a. If P2 ˆ ‰t3; t4‰ is the period associated with P and the activity b in the grouping process, then from the definition of P3; P36 P2. Let S 2 SEC…t; Tk†. If S 62 SA…P †, then since, by definition a and b are the first activities, there will exist a c 2 A such that sc 2 ‰t2; t3Š and S…c† 2 Z…P ; S…b††. This contradicts the existence of activity a. Therefore, S 2 SA…P †. We will prove that in t1 the sequences belonging to SEC…t; Tk† have a resource unit of type Tk assigned in W 000. This contradicts the definition of t: If S 2 SEC…t; Tk† and jT …S†j ˆ 1, then clearly S in t1 has a resource unit of type Tk assigned. If S 2 SEC…t; Tk† and jT …S†j > 1, it implies S 2 Z…P3; S…b††, then the activities that are processed in P3 in the sequence S have been grouped with the first activity of S scheduled in P , and reassigned with the same resource unit, so that since in P3 a unit of Tk would have been assigned, S in t1 has a unit of type Tk as- signed. Then W 000 is an RA of Q the macroactivities of MAC such that the number of macroactivities that are pro- cessed simultaneously and assigned the same resource type in the solution, do not exceed the actual number of resources of that type available. Therefore, based on the results of Ford and Fulkerson (1962), there ex- ists an RA of Q to the activities of A in which all the activities of a macroactivity have the same resource unit assigned. � References Arkin, M., Silverberg, B., 1987. Scheduling jobs with fixed start and end times. Discrete Applied Mathematics 18, 1–8. Baker, D., 1974. Scheduling a full-time workforce to meet cyclic stang requirements. Management Science 20 (12), 1561–1568. Bechtold, S., Brusco, M., Showalker, M., 1991. A comparative evaluation of labor tour scheduling methods. Decision Science 22, 683– 699. Brittan, J., Farley, F., 1971. College timetable construction by computer. The Computer Journal 14 (4), 361–365. de Werra, D., 1971. Construction of school timetables by flow methods. Infor 9 (1), 12–22. de Werra, D., 1985. An introduction to timetabling. European Journal of Operational Research 19, 151–162. Defrenne, A., 1978. The timetabling problem: A survey. Cahiers Centre Etud. Resh. Oper 20 (2), 163–169. Fischetti, M., Martello, S., Toth, P., 1987. The fixed job schedule problem with spread-time constraints. Operations Research 37 (3), 395–403. Ford, L.R., Fulkerson, D.R., 1962. Flows in Networks, Princeton University Press, pp. 64–67. Korman, S., 1979. The graph colouring problem. In: Christofides, N., Mingozzi, A., Toth, P., Sandi, C. (Eds.), Combinatorial Optimization, Wiley, New York, pp. 211–235. Li, C., Robinson, E., Mabert, V., 1991. An evaluation of tour scheduling heuristics with di€erences in employee productivity and cost. Decision Sciences 22, 700–718. Loucks, J., Jacobs, F., 1991. Tour scheduling and task assignment of a heterogeneous work force: A heuristic approach. Decision Sciences 22, 719–738. Marsten, R., Muller, M., Killion, C., 1979. Crew planning at flying tiger: A successful application of integer programming. Management Science 25 (12), 1175–1183. 490 V. Valls et al. / European Journal of Operational Research 107 (1998) 470–491 Morris, J., Showalker, M., 1983. Simple approaches to shift, days-o€ and tour scheduling problems. Management Science 29 (8), 942– 950. Neufeld, G., Tartar, J., 1974. Graph coloring conditions for the existence of solutions to the timetable problem. Communications of the ACM 17 (8), 450–453. Quintanilla, M.S., 1994. T�ecnicas Exactas y Heur�ısticas para la Asignaci�on de una Plantilla de Trabajadores a una Planificaci�on Establecida. Ph.D. Thesis, Departamento de Estad�ıstica e Investigaci�on Opertiva, Universidad de Valencia, Spain. Ritzman, L., Krajewski, L., Showalter, J., 1976. The disaggregation of aggregate manpower plans. Management Science 22 (11), 1204– 1214. Ruhe, G., 1991. Algorithmic Aspects of Flows in Networks. Kluwer Academic Publishers, pp. 174–184. Valls, V., P�erez, M.A., Quintanilla, M.S., 1996a. A graph colouring model for assigning a heterogeneous workforce to a given schedule. European Journal of Operational Research 90, 285–302. Valls, V., P�erez, M.A., Quintanilla, M.S., 1996b. A modified tabu thresholding approach for the generalised restricted vertex colouring problem. In: Osman, I.H., Kelly, J.P. (Eds.), Metaheuristic Theory and Applications. Kluwer Academic Publishers, pp. 537–553. V. Valls et al. / European Journal of Operational Research 107 (1998) 470–491 491