Selective Routing Problem with Synchronization

Selective Routing Problem with Synchronization Jorge Riera-Ledesma ∗ Departamento de Ingeniería Informática y de Sistemas, Universidad de La Laguna, La Laguna, Spain Juan-José Salazar-González Departamento de Matemáticas, Estadística e Investigación Operativa, Universidad de La Laguna, La Laguna, Spain Abstract We introduce a new optimization problem arising in the management of a multi-object spectrograph in a telescope. The eld of view of the spectrograph is divided in 55 contiguous and parallel spatial bands. Each band is associated with two opposite sliding bars that can be positioned to observe an astronomical object. The observation of an object requires the synchronized conguration of the bars in several contiguous bands to form a slitlet in the position of the object. A multi-slit pattern for the bars permits the simultaneous observation of several objects requiring bars of dierent bands. Each astronomer using this spectrograph propose a list of objects to observe. Since the instrument is quite demanded, the manager of the telescope imposes a time limitation to the astronomers, so they need to select a subset of objects from their lists. This paper describes and solves the selection problem. The problem must also nd a sequence of congurations for the bars in each band to maximize the total priority of the selection, subject to some synchronization issues and the time limitation. We show three mathematical formulations. One of them is a set-partitioning model where a master problem manages the synchronization constraints and a subproblem generates columns satisfying the time limitation. We propose two branch-and-price-and-cut algorithms for solving the set-partitioning model, and discuss an extensive computational experiment showing the performance of the algorithms on two families of instances. Keywords: routing, orienteering problem, synchronization, branch-and-price-and-cut, scheduling 1. Introduction The Gran Telescopio Canarias (GTC), also known as GRANTECAN, is presently the largest optical telescope in the world, and one of the Spanish Unique Scientic and Technical Infrastructures ∗ Corresponding author Email addresses: [email protected] (Jorge Riera-Ledesma), [email protected] (Juan-José Salazar-González) Preprint submitted to C&OR July 2020, Revised in February 2021, Revised in June 2021 Figure 1: Three photos of the device with the 55 pairs of bars in dierent congurations. (ICTS) 1 . It is a 10m class telescope located at the Observatorio del Roque de los Muchachos in the island of La Palma (Canary Islands, Spain). The Regional Government of the Canary Islands, the Spanish Government, European Funds, and also non-European partners ( Instituto de Astronomía de la Universidad Nacional Autónoma de México and the University of Florida , among others) actively support the GTC. A dening aspect of this scientic infrastructure is its ability to deliver cutting-edge data through new instruments. One of the most recent instruments in GTC is the Near Infrared Multi-Object Spectrograph (EMIR) 2 , operational since 2017. It is a wide-eld near-infrared camera-spectrograph imager which is able to observe objects in a spectroscopic view eld of 4×6.64 square arcminutes. One of the novel aspects of EMIR is the use of a cryogenic robotic unit that permits the remote conguration of a multi-slit pattern in its eld of view, where the GTC forms the image of the sky. This device is called Cold Slit Unit (CSU) and is composed by 55 pairs of opposite sliding bars that can be moved in one direction to create a slitlet. Thus, the eld of view is divided into 55 bands, each one associated with two retractable opposite bars of height h arcseconds. The value h is xed by the device. The width w of the slitlet created by a pair of bars is selectable by the astronomer according to the observing conditions and to the required spectral resolution. Figure 1shows three photos of the CSU in EMIR. On a regular basis, normally each semester, the interested astronomers around the world submit their observing proposals to a committee at GTC that distributes the available observing time of each instrument according to their scientic merits. EMIR has a large over-subscription factor, which forces the successful proposals to be customarily readjusted by the applicants to be doable within the awarded time slot. This task implies (a) Selecting about three view elds for the EMIR to cover objects in the submitted proposal: each view eld is characterized by a telescope pointing (which denes the center of the view eld) and the orientation of the CSU; the awarded observing time should be split among these 1 http://www.ciencia.gob.es/portal/site/MICINN/ICTS 2 http://www.gtc.iac.es/instruments/emir/ 2 view elds, thus forcing a time limitation on each one. (b) Selecting a subset of objects from the proposal to observe in each selected view eld within its time limitation: the order of observations aects the reconguration time of the CSU. To help the astronomers performing this task, the EMIR instrument team has designed and made available to the user community a graphical tool called Optimized Slits Positioner (OSP) 3 . It is a Guided User Interface that can overlay the EMIR view eld with the CSU in an astronomical image. The user must locate manually the GTC pointing over the image, rotate the CSU to the best position angle, and set a slit pattern for the bars on top of the desired objects in the view eld. While the OSP oers some capabilities to automatize the slit pattern for the bars, the other actions depend solely on the astronomer ability. There is no algorithm in OSP to solve the above task, which is a quite complicated optimization problem, combining a continuous optimization task in (a) with a combinatorial optimization decision in (b). Salazar-González [30] describes a heuristic approach to solve (a) only. Our paper is the rst scientic attempt to describe an exact algorithm to solve (b) for a given view eld and time limitation decided in (a). This algorithm could be inserted in OSP, so the astronomer will only need to decide about the view elds and time limitations to maximize the scientic return within the awarded observing time. In this paper we assume that the eld of view in the sky is given, and it contains a set of objects of interest to the astronomer. Considering the time awarded to the astronomer, not all the objects can be observed. The optimization problem in this paper is to select a subset of objects and the sequence of the observations that can be performed within the awarded observation time. Some objects in the eld of view may need the slitlet created by the bars of several contiguous bands. The bands allocated to each object and the slit width depend on the characteristics of the object (brightness and density) and the position in the eld of view. Each band consists of three horizontal areas as illustrated in Figure 2: an upper dead zone of length d1 arcseconds, a central area, and a lower dead zone of length d2 arcseconds. The values d1 and d2 are set by the need of avoiding the non-uniform bar edges in these locations due to the mechanical design of the bars, that have to adjust and slid smoothly over the bottom and top bars adjacent to each one. An object located in the central area of a band can be observed by the single slit of the two bars of that band. When an object is located at the upper or lower dead zone of a band, for technical reasons, observing this object requires the slit created by the bars of (at least) two contiguous bands. Figure 2(a) shows the three areas dividing a band, with an object in the central area. The two opposite bars set up a slit focusing the object. Figure 2(b) shows two contiguous bands 3 http://www.iac.es/proyecto/emir/pages/observing-with-emir/observing-tools/osp.php 3 w d2 d1 h (a) (b) Figure 2: Details on the bands, slits, and dead zones with an object falling in a dead zone. To observe that object, the bars in the two bands must be appropriately congured to generate a slit surrounding the object. As mentioned, some objects could need three or more contiguous bands to be observed. Since the bars can be independently congured, EMIR can perform many simultaneous observations (up to 55), but the synchronization of the bars needed for each observation is fundamental for an ecient management of the telescope. In addition, moving a bar is quite time consuming, so reconguration times in the CSU are long in EMIR. The ecient use of the telescope time imposes a carefully planning to maximise the scientic return in the available and limited observing time. Given a eld of view and a time limitation, this paper deals with the problem of selecting objects from a list and conguring the CSU bars. The list of objects (candidates to be observed) with priorities are also inputs. The aim is to process as many prioritized observations as possible. We call this optimization problem the Selective Routing Problem with Synchronization (SRPS) as it has characteristics of the Selective Travelling Salesman Problem, also known as Orienteering Problems (OP) and well known in the context of Vehicle Routing Problems (VRPs) (see e.g. [32]). The remaining of the paper has the following structure. Section 2gives a denition of this new optimization problem. A small numerical example complements this denition. Section 3makes a bibliographic contextualization of the SRPS as a synchronization problem and relates it to OPs and other similar problems. Section 4introduces three Mixed Integer Programming (MIP) models for the SRPS. The rst one is a compact MIP model based on variables using three indices. It linearizes the synchronization constraints using large positive coecients to activate/deactivate the conditional constraints. Our computational experiment shows an unsatisfactory performance of the branch-andcut algorithm performed by a state-of-the-art MIP solver on this model. For this reason, our paper proposes a second model avoiding the use of the large coecients, and eliminating invalid solutions with inequalities that exploit the combinatorial structure of the problem. Based on a Dantzig-Wolfe 4 decomposition (Dantzig and Wolfe [10]) of the second model, the paper introduces a third model of set-partitioning type and with a subproblem managing the time limitation constraint. This third model gives rise to two branch-and-price-and-cut algorithms described in Section 5. Section 6shows and discusses extensive computational results on two families of benchmark instances. The paper ends with a conclusion section. The reader can nd a mathematical connection between the three models in the Appendix. 2. Problem setting SRPS can be seen as a job scheduling problem where the pair of bars of each band represents a congurable processor, and each potential observation represents a job whose processing might require the synchronized conguration of several processors. Using standard terminology in Job Scheduling, the processors are non-identical in the sense that the processors to perform each job are a priori known. Not all jobs must be performed, and each one is associated with a prot. Then, SRPS looks for a selection of jobs and a sequence of congurations for each processor to maximize the sum of the prots of the selected jobs within a time limitation. Performing a subset of jobs consumes setting times of the implied processors, waiting times associated with the synchronization, and processing times for the selected jobs. We now describe the input parameters, characterize a feasible solution, and illustrate the whole problem with a small example. 2.1. Input parameters Let J={1, . . . , n} be the set of potential jobs. No job in J is compulsorily required to be performed. Processing a job j produces a positive revenue bj , associated with its priority. Each observation associated with a job j∈J requires a processing time of pj units. Setting up a processor k from job i to job j consumes a transition time cij . For convenience of notation, let tij =pi+cij . For modeling purposes, we also consider jobs 0 and n+ 1 that are an initial and a nal dummy jobs, respectively, and represent a safety status of the processors (in the astronomic application they represent parking the pair of bars of each band in the middle of the eld of view). Let pj=bj= 0 for j∈ {0, n + 1} , and V=J∪ {0, n + 1} . Let K={1, . . . , m} be the set of congurable nonidentical parallel processors. Each job j requires a subset Kj⊆K of processors to be performed. All processors in Kj need to be simultaneously in specic congurations during at least pj time units to perform j . Similarly, we denote by Jk⊆J the set of jobs that require the processor k to be performed. Let Vk=Jk∪ {0, n + 1} . Let Gk= (Vk, Ak) be the transition graph for the processor k , where Ak is the set of arcs among all vertices in Vk , except the ones leaving n+ 1 or entering 0 . Let G= (V, A) be the aggregated 5 graph where A is a set of triplets (i, j, k) such that k∈K and (i, j)∈Ak . Note that G is a multigraph since two vertices may be linked by several arcs. Each triplet a= (i, j, k)∈A is associated with a length ta equal to the time tij . Finally, let L be the given time limitation to perform the selected jobs. We assume that L≥t0j+tj,n+1 for all j∈Jk and k∈K . 2.2. Feasible solutions We characterize a feasible solution for the SRPS by one elementary path Pk⊂Ak from 0 to n+ 1 in Gk for each processor k∈K . The path Pk represents the sequence of jobs that processor k must process starting and nishing at the parking positions. Not all jobs need to be visited by a path, but when a path visits a job j then all paths Pk with k∈Kj must visit j . Also, there must exist a value sj for each j∈V satisfying: si−sj≤ −tij k∈K, (i, j)∈Pk (1) sn+1 −s0≤L. (2) The value sj represents the starting time to perform j and, together with constraints (1), it guarantees the synchronization of the processors when performing that job. That is, all processors involved in the processing of a specic job j may reach the conguration to start processing j at dierent times, but they all need to start the process of j at the same time sj . Inequality (2) limits the overall processing time. The set of inequalities (1) and (2) is known as System of Dierence Constraints (see Ahuja et al. [1]). The SRPS aims at nding the paths Pk and the values sj maximizing the sum of the prots associated with the selected jobs. From that perspective, SRPS can also be seen as a vehicle routing problem where the jobs are customers and the processors are vehicles. 2.3. An example This section presents the input parameters and a feasible solution for a small SRPS instance. Figure 3represents an input consisting of ve potential observations focused by a device with three bands. Objects 1 , 4 and 5 , located in middle areas, require the bars of exactly one band to be observed. Objects 2 and 3 fall in dead areas, so they need to be observed by the bars of the surrounding bands: the bars of bands 1 and 2 are required to observe the object 2 , while the object 3 requires the bars of bands 2 and 3 to be observed. More precisely, in this instance J={1,2,3, 4,5} , K={1,2,3} , J1={1,2} , J2={2,3,5} , J3={3,4} , K1={1} , K2={1,2} , K3={2,3} , K4={3} and K5={2} . Let us assume that the transition costs cij are given by the horizontal distance between the objects, with processing times and prot values equal to one unit for all the objects. Figure 4 depicts all valid transitions for the bars of each band to observe the objects. Each one is the 6 3 2 1 1 2 3 4 5 Figure 3: Example with ve objects and three bands transition graph Gk introduced above, and each arc represents changing the pair of bars of band k from one conguration to another. 0 1 2 n+ 1 (a) G1 0 2 3 5n+ 1 (b) G2 0 3 4 n+ 1 (c) G3 Figure 4: Transition graphs for the example in Figure 3 When the time limit is L= 11 , there is a feasible solution for this instance that allows the observation of the ve objects. This solution starts setting up the bars of the bands 1, 2 and 3 to observe the objects 1, 5 and 4, respectively. Then, the bars in bands 2 and 3 are set up to observe the object 3. Finally, the bars of bands 1 and 2 are congured to observe the object 2. All bars start at conguration 0 and nish at conguration n+ 1 . Figure 5shows the elementary paths on the transition graphs. 0 1 2 n+ 1 (a) P1 0 2 3 5n+ 1 (b) P2 0 3 4 n+ 1 (c) P3 Figure 5: Elementary paths for the example in Figure 3 The vector s= [0,1,8,6,4,2,11] contains valid scheduling time values, according to (1) and (2). Figure 6helps to understand the validity of this solution. Observe the existence of idle times for some bars due to the need of synchronization. 7 c01 p1c12 p2c2,n+1 c05 p5c53 p3c32 p2c2,n+1 c04 p4c43 p3c3,n+1 t K 1 2 3 L s1s5s4s3s2 Figure 6: Diagram associated with a feasible solution for the example in Figure 3 3. Literature review The previous section suggests that SRPS is closely related to vehicle routing problems investigated in the literature. This section details some of these relations. 3.1. Orienteering problems OPs represent a family of vehicle routing problems taking into account practical situations where serving a customer is optional, generating a prot if the service is done within a time limitation. We refer the reader to the survey by Gunawan et al. [20] for an extensive revision of this family of problems and their practical applications. Relaxing the SRPS by removing the synchronization constraints results in m independent instances of the well-known OP (see e.g. Tsiligirides [31], Golden et al. [18]). The OP aims at selecting a subset of customers and designing a route with a total time duration not longer than a given time limitation, to maximize the total collected prot. It is a combination of the Cycle Problem and the Knapsack Problem where the total time duration of the cycle does not have to be minimized but is constrained. Although this relaxed version of the SRPS involves a set of vehicles to serve some customers, it should not be confused with the Team Orienteering Problem (TOP) (see e.g. Butt and Cavalier [6], Chao et al. [7]). The TOP is an extension of the OP which also considers multiple routes to serve the customers, but where a customer must be served by one vehicle only. In other words, TOP does not include any synchronization issue and there is not pre-assignment of vehicles to customers. Still, SRPS coincides with TOP when each object requires only one pair of bands to be observed. 3.2. Synchronization problems According to Drexl [15], the SRPS is a case of exact operation synchronization , that means that two vehicles must start executing their operations at their respective locations at the same time. The literature for vehicle routing problems with this characteristic describes exact approaches mainly using arc-variable based formulations making use of time variables representing the beginning 8 of execution for each job. Unfortunately, these formulations are implicitly non-linear, and their linearization requires the use of a bigM value; see e.g. Desrosiers et al. [11], Lim et al. [27], Li et al. [26], Dohn et al. [14], Cortés et al. [9] and Gelareh et al. [17]. An alternative to avoid the bigM drawback is the use of column-generation or branch-andprice approaches. Examples of this technique appear in Ioachim et al. [21], solving the problems of a eet assignment and vehicle routing with schedule synchronization constraints, or in Bélanger et al. [5], approaching the problem of a periodic airline eet assignment with time windows, spacing constraints, and time-dependent revenues. Both articles use the labeling algorithm proposed by Ioachim et al. [22]. 3.3. Manpower allocation problems Manpower allocation problems describe an exact operation synchronization family of problems which arises in several contexts where performing each job requires the cooperation between teams, possibly with dierent skills. The allocation of technicians to service jobs, where solving each specic job requires a combination of technicians with individual skills, is an example of this family of problems. Although these problems share characteristics in common with SRPS like the exact operation synchronization, they also dier in other characteristics like the structure of the routes, the objective functions, and the requirement of processing all jobs. Lim et al. [27] introduce the Manpower Allocation Problem as a multi-criteria problem, and proposes a simulating-annealing algorithm to solve it heuristically. Li et al. [26] cite an application where technicians are dispatched from a central oce to various locations in the Port of Singapore to service jobs that may require multiple technicians. Luo et al. [28] describe an application in the movie industry where some scenes shot at dierent locations require routing lm crews, such as actors, camera operators, lighting technicians, and make-up artists. Dohn et al. [14] introduce another application related to airport management: after arriving at the airport, the aircraft stops at dierent locations and ground crew members of dierent responsibilities are deployed to deal with various jobs, such as baggage handling, aircraft cleaning, aircraft de-icing service, aviation fueling service, and aircraft maintenance check. The literature also mentions examples arising in the home care sector, where specialized workers travel between the patient homes, which demands collaborative work. 4. Formulation We now introduce three mathematical formulations to describe the SRPS. They are built on the following two families of variables. For each processor k∈K and each arc (i, j)∈Ak , the binary 9 5.1. Pricing algorithms A pricing Sub-Problem (SP) performs a dynamic column-generation approach to overcome the exponential number of variables λk r in the model SRPS-3. This approach leads to an iterative procedure where, at each iteration, new columns enlarge a restricted master problem. The master problem starts solving an initial LP-relaxation with some λ variables. Then, at each iteration, the SP aims at generating routes r∈Ωk with negative reduced cost ¯ck r from the values of the dual variables obtained from the restricted master problem. One route is computed for each processor k , thus up to |K| routes can be generated at each iteration. Each new route r is associated with a new variable λk r for the restricted master problem in the next iteration. The SP where Ωk includes only elementary routes is called SRPS-SP-E, and the one where Ωk also includes non-elementary routes is called SRPS-SP-N. They require implicitly generating all negative reduced cost paths r , from 0 to n+ 1 , with length not greater than L , within each graph Gk , for all k∈K . The usual procedure to approach these subproblems is to formulate them as constrained shortest path problems, and solving them with a dynamic programming (DP) approach based on labeling algorithms (see e.g. Irnich and Desaulniers [23]). The SRPS-SP-E is the so-called Elementary Shortest Path Problem with Resource Constraints (ESPPRC). Unfortunately, solving SRPS-SP-E using a DP algorithm may become unaordable as the size of the problem grows because the ESPPRC is strongly NP -hard (see e.g. Irnich and Villeneuve [24]). That is why solving a relaxed version of the ESPPRC, as the SRPS-SP-N, becomes an inviting alternative. Our DP implementation for solving SRPS-SP-N makes use of a relaxed structure called ng  route. The ng route relaxation, introduced in Baldacci et al. [4], makes use of the sets Ni⊆V for vertex i (according to some criterion), such that i∈Ni and |Ni| ≤ ∆(Ni) , where ∆(Ni) is a parameter (e.g., ∆(Ni) = 5 , for all i∈V , and Ni contains i and the four nearest customers to i ). These sets Ni allow us to associate with each sub-path generated during the pricing algorithm with a set of forbidden successors. This adaptation of the ng route relaxation solves the pricing problem SRPS-SP-N considering a superset of routes Ω0k from the set of routes Ωk . The set Ω0k satises the feature that none of the routes in Ω0k\Ωk can be used in a feasible integer solution of the master problem. Thus, an optimal solution of the master problem on Ω0k has the same value as an optimal solution of the problem on Ωk , but the LP-relaxation from the latter is stronger than that from the former. 5.2. Separation algorithms We describe now how to dynamically generate the set of MIS elimination constraints (17) and (18) for our BPC algorithms BPC-SRPS-E and BPC-SRPS-N. Let (˜x, ˜y) be a solution from the 16 LP-relaxation of a restricted master problem, also described by its associated multigraph ˜ G . If (˜x, ˜y) is an integer solution, we can trivially nd circuits in ˜ G with the algorithm in Johnson [25] to separate constraints (17). If there are no cycles in such an integer solution, to separate constraints (18), one can nd longest paths with the algorithm in Dijkstra [13] to compute the shortest path from 0 to n+ 1 in ˜ G weighting each arc (i, j, k) with −tij . If (˜x, ˜y) is a non-integer solution, nding circuits or paths leading to violated inequalities (17) or (18), respectively, is much harder but still aordable. To detect and nd cycles we look for minimum-weighted circuits in ˜ G assigning a weight 1−˜xk ij to each arc (i, j, k) . To detect violating paths longer than L , we look for minimum-weighted paths from 0 to n+1 weighting each arc (i, j, k) by −˜xk ijtij . To reduce the complexity when (˜x, ˜y) is not integer, we propose the following heuristic approach: Fix µ= 1 , solve the linear program (13)(16), let ˜γ be an optimal solution, and compute ˜ G as the graph resulting from removing from G the arcs associated with null values of ˜γ . If the problem is infeasible, we look for violating cycles in ˜ G by using the Johnson's algorithm. If we nd a violating cycle, we add the associated inequality (17) to the master problem. Otherwise, we check all paths from 0 to n+ 1 in ˜ G , evaluating the violation of any potential constraint (18) for each path with length greater than L . 5.3. Branching strategy When the pricing procedure in Section 5.1 and the separation procedure in Section 5.2 do not nd any new element to add to the current restricted master problem, but its solution (˜x, ˜y) contains fractional values, our BPC algorithms resort to the branching phase. In this phase two restricted master problems are created by xing a variable yj to 0 and 1, respectively, if ˜yj is fractional, and by xing a xk ij variable if ˜yj is integer for all j∈J and ˜xk ij is fractional. When several variables are at fractional values, the closest to 1/2 is selected for the branching; ties with yj variables are broken by choosing the one with largest priority bj , and ties with xk ij variables are broken by choosing the one with largest transition cost cij . 6. Computational experiments This section analyzes the performance of the implementations for the exact algorithms BPCSRPS-E and BPC-SRPS-N. It also compares these algorithms against giving the compact model SRPS-1 to IBM ILOG CPLEX 12.10. Although it is well known the weakness of the linear programming relaxation of the compact model, the section shows computational results to precisely measure this negative behaviour, while justifying the need of a more sophisticated alternative approach. For 17 this purpose, we have performed a test campaign on benchmark instances. The description of the test set and a discussion on the obtained results are also presented here. We coded the approaches in C ++ on a Linux platform with Ubuntu Desktop 20.04 LTS, running on an Intel(R) Core i5 6600 3.3 GHz with 8 GB RAM. Our implementations of the BPC algorithms are based on an ad hoc branch-and-bound scheme which uses IBM ILOG CPLEX 12.10 as LP solver. 6.1. Test instances To evaluate the performances of the approaches, we have created two families of instances. It is quite accepted that stars in the sky are located like random points on a plane; this should not be confused with the fact each star has a light intensity and therefore stars in the real universe also show clustering. For that reason, there is no lost of generality by using random data for evaluating our implementations rather than using real-world catalogues of stars. The rst family contains 240 instances generated to simulate real-world data from the telescope application motivating our research, where the bars move on a line and therefore the transition times depend on one coordinate of the objects. The transition time in the second family involves the two coordinates of objects, as one could expect in a vehicle routing context arising on a plane. To measure the impact of the synchronization, each family is divided in four classes according to the number of bands (processors) required to observe (process) each target (job). This section details how the instances were generated. Our rst step was to built ve catalogues, each one containing of 500 targets randomly-generated in the 240.0×398.4 square arcseconds eld of view of EMIR. We characterize each target i by a tuple (ui, vi, pi, bi) . The horizontal coordinate value ui and the vertical value vi have been randomly selected in the continuous intervals [−120.0,120.0] and [−199.2,199.2] , respectively. The processing time pi is an integer number uniformly generated in the interval [1,200] . The value of the prize bi has been randomly selected in the set {1,10,100} . We have characterized the initial and nal congurations (i.e. the dummy targets 0 and n+ 1 ) by the tuple (0,0,0,0) . We do not use each catalogue as one instance but a source of instances for the two families. Aiming at a realistic design, the transition times in the rst family of instances are dened as the horizontal movement of the sliding bar, i.e. dij =|ui−uj| . The transition times in the second family of instances are dened by the Euclidean distance between the points, i.e. dij = p(ui−uj)2+ (vi−vj)2 . The rst family is denoted by H and the second family by E . We consider |K|= 55 pairs of bars, each one k covering the targets in position (ui, vi) with 398.4×(k−1)/55 −199.2≤vi<398.4×k/55 −199.2 for k= 1,...,55 . We create Vk for each instance and band k∈K according to four classes. The instances in Class g (for g∈ {1,2,3,4} ) have g bands assigned to each target, i.e. |Kj|=g for all j∈V\{0, n+1} . The bands assigned to a 18 target in position (ui, vi) are selected minimizing the distance vi to the center of the band. By doing so, the instances in Class 1 do not require synchronization. Hence, these instances help to analyze the behaviour of our algorithms on the problem without synchronization, which in a sense is similar to the classical OP. On the other hand, the synchronization requirements has a larger impact on the instances in Class 4, which are the most dicult to solve. The instances in the telescope application belong to Family H and combine characteristics of the four classes. For each catalogue of targets, we have generated instances with dierent sizes. We have chosen these sizes according to a preliminary computational experience, aiming at evaluating the behavior of the algorithms ranging from easy to hard instances. Thus, the number n of targets for Class 1 is in the set {425,450,475,500} , for Class 2 in the set {100,110,120,130} , for Class 3 in the set {55,60,65,70} , and for Class 4 in the set {45,50,55,60} . The n targets for each instances are randomly selected from the 500 targets of the catalogue. As done in Fischetti et al. [16] for the OP, we dene the time limitation for each instance of the family E as L=α·max{zT SP (Vk) : k∈K} , where α is a given parameter in {0.25,0.50,0.75} and zT SP (Vk) is the length of the optimal TSP route on Vk . The time limitation for each instance of the Family H is dened by L=d2·α·(max{uj|j∈V} − min{uj|j∈V})e for α∈ {0.25,0.50, 0.75} . Summarizing, our benchmark consists of eight groups of instances, denoted with a letter ( H or E ) for the family and a number ( 1, 2, 3, 4 ) for the class. Each group contains a number of instances equal to ve (one from each catalogues) times four values of n and times three values of α , i.e. a group consists of 60 SRPS instances. The benchmark, as well as its description and generation code, are available as a supplementary material in this publication. 4 6.2. Tables description We have conducted experiments solving the above instances with the approaches described in this paper. Details are shown on ve tables. Each line of a table shows the average results of solving the ve instances (one from each catalogue) for a given family, class, n and α . We have established a time limit of one CPU hour to solve each instance. When this time limit has been elapsed, the execution of the algorithm stops and the quality of the integer gap and the number of solved branching nodes are measured to get an estimation on the future behavior of the algorithm. Table 1shows the behavior of the software IBM ILOG CPLEX 12.10 solving the compact model on the rst family of instances described in Section 6.1, i.e. the instances with distances on a line. Note that the commercial software uses sophisticated primal heuristic procedures, strong branching, 4 Also available at https://github.com/RieraULL/OPS-Benchmark 19 general-purpose cuts, and pre-solving procedures, and we used the default settings. The rst four columns show: n , number of targets; |Vk| , average number of targets associated to a band (not including the two dummy nodes); value of the parameter α ; and |V∗| , average number of targets observed in a feasible solution (possibly optimal) for these input instances. We also show the average computational time in CPU seconds to process the root node of the branching tree (Column RT ), and to process the overall algorithm (Column OA ). Column Gap (%) shows the average integer gap at the end of the root node (RT) and at the end of the execution (OA) . We compute the integer gap as 100×(Bd−Bp)/Bp , where Bd and Bp are the values of the dual and primal bounds, respectively. The primal bound is the objective value of the best integer feasible solution, and the dual bound is the optimal value of the best LP relaxation. The last columns of the tables show the number of branching nodes (#nod) , and the number of instances solved to optimality within the time limit of one hour ( X ) . Tables 25summarize the result of the experiments showing details on the BPC algorithms. These tables include the previous columns, and also the number of variables generated by the BPC algorithms (#col) , the number of Inequalities (17), the number of Inequalities (18), and number of branching nodes (#nod) . Note that #col shows the number generated λk r variables, and to get the nal number of columns in the model one must add the number of xk ij and yi variables. In a similar way, (17) and (18) show the number of generated inequalities, and to get the nal number of rows in the model one must add the number of equations (4)(7), (19) and (21). 6.3. Discussion Table 1conrms the drawback of having a bigM value in the model SRPS-1 to activate/deactivate the conditional constraints associated with the synchronization. Indeed, the dual bounds obtained during the LP-relaxation become extremely weak, leading to an endless branching process. Those instances showing an important impact of the time limitation constraints yield a large integer gap at the root node. This is the case of the instances with α= 0.25 , showing integer gaps, in some cases ( H2 with n= 130 ) of about 46% on average. However, even with a better integer gap at the end of the root node, the instances involving larger values of the time limitation L became harder. Indeed, only a few of these instances were solved to optimality. We do not show results solving instances E through model SRPS-1 because they are very similar to the ones on the instances H . The BPC algorithms reach tighter bounds and therefore better integer gaps. The better behaviour of these decomposition approaches versus solving the compact model is quite obvious on Group H1 . Tables 2-5show very few cases reaching gaps of over 1% at the end of the root node. All cases have nished the computation of the root node in less than a second, so the BPC algorithms used as an heuristic approach on these instances provide solutions with good features, which is a 20 Table 1: Compact model SRPS-1 solved by IBM ILOG CPLEX 12.10 CPU (sec.) Gap (%) n|Vk|α|V∗| RT OA RT OA #nod X Group H1 425 16.6 0.25 224.4 1.0 1 hour 31.84 21.44 1372237 0 0.50 366.8 0.8 1 hour 4.44 4.35 1825989 0 0.75 414.8 0.7 1 hour 0.13 0.13 4227632 0 450 17.0 0.25 231.8 1.0 1 hour 39.88 33.38 1108651 0 0.50 382.8 0.8 1 hour 6.51 6.46 1871202 0 0.75 438.6 0.7 1 hour 0.25 0.25 3443596 0 475 17.2 0.25 242.3 1.2 1 hour 38.68 32.57 883122 0 0.50 401.4 0.9 1 hour 6.13 6.08 1456411 0 0.75 460.2 0.7 1 hour 0.41 0.41 3303323 0 500 17.6 0.25 248.8 1.2 1 hour 45.97 40.82 759719 0 0.50 418.6 1.0 1 hour 7.55 7.50 1358782 0 0.75 482.2 0.8 1 hour 0.69 0.69 2573756 0 Group H2 100 9.2 0.25 47.0 0.5 732.4 19.14 1.29 425085 4 0.50 77.8 0.4 2881.6 4.94 2.55 2802659 1 0.75 94.6 0.3 1615.4 0.21 0.09 1725292 3 110 10.0 0.25 49.8 0.4 937.6 25.80 2.09 620185 4 0.50 84.6 0.4 1 hour 5.66 3.81 2302131 0 0.75 103.8 0.4 1 hour 1.35 1.29 3891895 0 120 11.0 0.25 54.4 0.5 2331.0 35.24 12.57 1096238 2 0.50 94.2 0.4 1 hour 6.82 4.95 3580850 0 0.75 112.4 0.4 1 hour 0.65 0.57 3299686 0 130 11.4 0.25 55.6 0.5 2929.6 46.69 16.90 1194113 1 0.50 99.8 0.5 1 hour 6.96 5.31 1979459 0 0.75 120.0 0.4 1 hour 2.04 1.97 3944808 0 Group H3 55 6.6 0.25 22.2 0.1 2.8 13.90 0.00 3570 5 0.50 38.2 0.3 724.8 7.48 1.45 219762 4 0.75 50.0 0.3 1457.9 0.58 0.15 1184713 3 60 7.6 0.25 24.4 0.3 9.0 13.19 0.00 11315 5 0.50 45.6 0.3 1444.2 5.51 1.27 871416 3 0.75 56.6 0.2 944.9 0.43 0.11 1066224 4 65 8.6 0.25 26.2 0.4 9.8 16.29 0.00 8541 5 0.50 48.4 0.4 2306.3 6.45 3.28 1194224 2 0.75 60.4 0.3 1573.4 1.39 1.11 1379223 3 70 9.0 0.25 30.4 0.5 638.3 24.94 0.00 219174 5 0.50 53.4 0.4 1 hour 5.18 2.05 1895638 0 0.75 65.0 0.3 3311.9 1.31 1.07 2767077 1 Group H4 45 7.0 0.25 17.2 0.2 1.9 8.86 0.00 1756 5 0.50 30.2 0.4 792.6 9.15 0.04 556192 4 0.75 39.4 0.3 986.9 0.76 0.02 608451 4 50 7.4 0.25 18.4 0.3 10.6 19.31 0.00 9404 5 0.50 32.8 0.4 1786.7 10.37 2.00 649354 3 0.75 42.4 0.4 2922.2 1.19 0.19 1987362 1 55 8.0 0.25 20.4 0.3 792.7 34.04 0.00 559349 5 0.50 35.0 0.4 1 hour 16.22 8.95 1223472 0 0.75 48.0 0.4 1 hour 2.51 1.84 2149506 0 60 9.2 0.25 23.6 0.4 1713.2 33.53 7.23 770551 3 0.50 39.8 0.4 1 hour 10.67 8.79 1339406 0 0.75 53.0 0.4 1 hour 6.62 6.57 2532200 0 21 Table 2: Algorithms BPC-SRPS-E and BPC-SRPS-N on instances H1 and H2 BPC-SRPS-E BPC-SRPS-N CPU (sec.) Gap (%) CPU (sec.) Gap (%) n|Vk|α|V∗| RT OA RT OA #col (17) (18) #nod X RT OA RT OA #col (17) (18) #nod X Group H1 425 16.6 0.25 230.2 1.1 1.1 0.00 0.00 1769 0 0 1 5 1.5 1.5 0.00 0.00 1465 0 0 1 5 0.50 369.2 24.0 24.0 0.00 0.00 1708 0 0 1 5 35.7 35.7 0.00 0.00 1538 0 0 1 5 0.75 416.0 51.7 51.7 0.00 0.00 1452 0 0 1 5 56.3 56.3 0.00 0.00 1255 0 0 1 5 450 17.0 0.25 239.2 1.8 1.8 0.00 0.00 1904 0 0 1 5 2.2 2.2 0.00 0.00 1746 0 0 1 5 0.50 390.0 64.7 64.7 0.00 0.00 1897 0 0 1 5 47.1 47.1 0.00 0.00 1718 0 0 1 5 0.75 439.8 73.0 73.0 0.00 0.00 1494 0 0 1 5 64.3 64.3 0.00 0.00 1477 0 0 1 5 475 17.2 0.25 246.0 1.8 1.8 0.00 0.00 2019 0 0 1 5 2.3 2.3 0.00 0.00 1892 0 0 1 5 0.50 405.8 44.2 44.2 0.00 0.00 2018 0 0 1 5 55.8 55.8 0.00 0.00 1964 0 0 1 5 0.75 464.0 83.4 83.5 0.00 0.00 1586 0 0 1 5 80.5 80.5 0.00 0.00 1564 0 0 1 5 500 17.6 0.25 261.6 4.2 4.2 0.00 0.00 2231 0 0 1 5 4.4 4.4 0.00 0.00 2060 0 0 1 5 0.50 425.2 129.1 129.1 0.00 0.00 2116 0 0 1 5 132.9 132.9 0.00 0.00 2078 0 0 1 5 0.75 486.0 207.2 207.2 0.00 0.00 1641 0 0 1 5 216.2 216.2 0.00 0.00 1731 0 0 1 5 Group H2 100 9.2 0.25 47.0 0.0 0.0 0.00 0.00 451 1 0 1 4 0.0 0.1 0.41 0.00 358 53 0 5 4 0.50 77.8 0.0 0.5 0.00 0.00 735 119 4 17 5 0.1 0.7 0.05 0.00 548 63 0 28 5 0.75 94.6 0.0 0.0 0.00 0.00 748 0 0 1 5 0.1 0.1 0.00 0.00 588 0 0 1 3 110 10.0 0.25 49.8 0.0 0.2 0.29 0.00 518 34 16 10 4 0.0 0.4 0.67 0.00 407 2 36 20 5 0.50 85.2 0.1 0.8 0.00 0.00 868 266 0 33 5 0.1 4.7 0.47 0.00 681 4 0 148 5 0.75 103.6 0.1 1.1 0.00 0.00 861 265 0 17 5 0.2 1.6 0.03 0.00 733 15 0 33 3 120 11.0 0.25 54.6 0.1 721.0 0.68 0.07 634 64951 36540 24565 4 0.1 721.4 1.38 0.07 510 62990 49093 23373 4 0.50 95.0 0.1 2.5 0.00 0.00 980 401 33 49 5 0.2 723.2 0.22 0.01 876 40511 478 4942 3 0.75 113.6 0.1 4.2 0.00 0.00 983 628 0 65 5 0.4 14.0 0.05 0.00 1028 121 0 65 4 130 11.4 0.25 57.2 0.1 720.6 0.68 0.01 707 45175 30097 31409 4 0.1 722.9 0.76 0.07 563 57353 39048 23997 4 0.50 100.8 0.1 1445.3 0.06 0.06 1104 146873 1788 17124 3 0.2 1450.0 0.32 0.09 1068 129671 1419 15976 3 0.75 121.6 0.2 1449.9 0.61 0.61 1087 33251 0 3302 3 0.7 1453.3 0.18 0.14 1289 13288 0 3046 3 22 Table 3: Algorithms BPC-SRPS-E and BPC-SRPS-N on instances H3 and H4 BPC-SRPS-E BPC-SRPS-N CPU (sec.) Gap (%) CPU (sec.) Gap (%) n|Vk|α|V∗| RT OA RT OA #col (17) (18) #nod X RT OA RT OA #col (17) (18) #nod X Group H3 55 6.6 0.25 22.2 0.0 0.0 0.00 0.00 271 0 0 1 5 0.0 0.0 0.00 0.00 228 1270 0 1 5 0.50 38.2 0.0 1.4 0.01 0.00 529 335 199 119 5 0.0 4.7 0.17 0.00 423 1271 468 373 5 0.75 50.0 0.0 0.0 0.00 0.00 575 0 0 1 5 0.0 0.1 0.04 0.00 438 0 0 3 5 60 7.6 0.25 24.4 0.0 0.0 0.00 0.00 352 1 0 1 5 0.0 0.0 0.00 0.00 288 1 0 1 5 0.50 45.8 0.0 0.4 0.00 0.00 631 152 10 17 5 0.0 1.0 0.37 0.00 493 104 0 41 5 0.75 56.8 0.0 0.0 0.00 0.00 646 0 0 1 5 0.1 0.1 0.09 0.00 552 1 0 3 5 65 8.6 0.25 26.2 0.0 0.0 0.00 0.00 407 2 0 1 5 0.0 0.0 0.00 0.00 335 3 0 1 5 0.50 48.6 0.0 720.9 0.01 0.01 708 108710 2384 11136 4 0.1 720.7 0.59 0.01 579 105331 2106 11266 4 0.75 60.6 0.0 1.2 0.00 0.00 730 434 0 33 5 0.1 1.5 0.01 0.00 653 152 0 33 5 70 9.0 0.25 30.4 0.0 0.1 0.06 0.00 500 17 6 5 5 0.0 0.2 0.60 0.00 394 12 1 12 5 0.50 53.2 0.1 721.9 0.08 0.08 815 123735 16211 18205 4 0.1 722.6 0.13 0.08 695 123492 16203 18207 4 0.75 65.0 0.1 1.6 0.00 0.00 817 512 0 33 5 0.2 1.8 0.02 0.00 822 92 0 33 5 Group H4 45 7.0 0.25 17.2 0.0 0.0 0.00 0.00 316 0 0 1 5 0.0 0.0 0.00 0.00 257 0 0 1 5 0.50 30.2 0.0 0.0 0.00 0.00 607 0 0 1 5 0.0 0.0 0.00 0.00 437 0 0 1 5 0.75 39.4 0.0 0.0 0.00 0.00 671 0 0 1 5 0.0 0.0 0.00 0.00 487 0 0 1 5 50 7.4 0.25 18.4 0.0 0.0 0.00 0.00 368 0 0 1 5 0.0 0.0 0.00 0.00 298 0 0 1 5 0.50 33.0 0.0 0.0 0.00 0.00 691 0 0 1 5 0.1 0.1 0.06 0.00 538 2 0 1 5 0.75 42.4 0.0 0.6 0.00 0.00 762 244 0 17 5 0.1 0.9 0.00 0.00 701 231 0 17 5 55 8.0 0.25 20.4 0.0 0.0 0.00 0.00 440 0 0 1 5 0.0 0.2 0.00 0.00 359 42 8 6 5 0.50 36.0 0.1 4.0 0.01 0.00 823 2180 13 145 5 0.1 2.7 0.12 0.00 698 974 3 81 5 0.75 48.2 0.1 6.3 0.00 0.00 871 1149 0 49 5 0.2 30.6 0.02 0.00 952 973 0 113 5 60 9.2 0.25 23.8 0.0 0.3 0.04 0.00 569 81 20 14 5 0.0 0.4 0.12 0.00 454 221 2 19 5 0.50 40.6 0.1 1378.3 0.12 0.11 1006 322372 1056 26724 3 0.1 1441.9 0.17 0.11 943 312922 498 25099 3 0.75 54.4 0.1 730.7 0.12 0.12 980 28889 0 1873 4 0.3 808.6 0.14 0.04 1223 30372 0 2002 4 23 Table 4: Algorithms BPC-SRPS-E and BPC-SRPS-N on instances E1 and E2 BPC-SRPS-E BPC-SRPS-N CPU (sec.) Gap (%) CPU (sec.) Gap (%) n|Vk|α|V∗| RT OA RT OA #col (17) (18) #nod X RT OA RT OA #col (17) (18) #nod X Group E1 425 16.6 0.25 206.6 2.2 2.2 0.00 0.00 1642 0 0 1 5 1.3 1.3 0.00 0.00 1336 0 0 1 5 0.50 359.2 60.4 60.4 0.00 0.00 1745 0 0 1 5 45.7 45.7 0.00 0.00 1588 0 0 1 5 0.75 414.2 67.4 67.5 0.00 0.00 1473 0 0 1 5 62.9 62.9 0.00 0.00 1325 0 0 1 5 450 17.0 0.25 220.4 2.4 2.4 0.00 0.00 1746 0 0 1 5 2.3 2.3 0.00 0.00 1584 0 0 1 5 0.50 376.6 54.7 54.8 0.00 0.00 1905 0 0 1 5 75.8 75.8 0.00 0.00 1772 0 0 1 5 0.75 437.4 101.3 101.3 0.00 0.00 1566 0 0 1 5 72.1 72.1 0.00 0.00 1472 0 0 1 5 475 17.2 0.25 227.0 2.0 2.0 0.00 0.00 1896 0 0 1 5 2.1 2.1 0.00 0.00 1721 0 0 1 5 0.50 391.0 41.9 41.9 0.00 0.00 1999 0 0 1 5 67.9 67.9 0.00 0.00 2051 0 0 1 5 0.75 460.6 75.5 75.5 0.00 0.00 1600 0 0 1 5 75.9 75.9 0.00 0.00 1604 0 0 1 5 500 17.6 0.25 241.0 3.6 3.6 0.00 0.00 2099 0 0 1 5 5.8 5.8 0.00 0.00 1880 0 0 1 5 0.50 411.6 120.6 120.7 0.00 0.00 2131 0 0 1 5 123.2 123.2 0.00 0.00 2094 0 0 1 5 0.75 482.0 166.3 166.4 0.00 0.00 1601 0 0 1 5 181.0 181.0 0.00 0.00 1813 0 0 1 5 Group E2 100 9.2 0.25 36.8 0.0 0.0 0.0 0.0 321 0 0 1 5 0.0 0.1 0.5 0.0 269 140719 0 10 5 0.50 72.2 0.0 1156.1 0.0 0.0 713 83263 34440 27253 4 0.1 1156.0 0.0 0.0 544 110679 37733 31919 4 0.75 92.2 0.0 1.4 0.0 0.0 738 136 6 17 5 0.1 1.1 0.0 0.0 592 52 0 18 5 110 10.0 0.25 39.0 0.0 0.4 0.0 0.0 376 33 76 36 5 0.0 0.2 0.0 0.0 314 83272 44 17 5 0.50 77.4 0.1 2162.4 0.1 0.1 842 236184 103648 61147 2 0.1 2162.1 0.6 0.1 685 223909 99624 59815 2 0.75 101.6 0.1 1.8 0.0 0.0 872 315 8 33 5 0.1 2.5 0.0 0.0 763 79 0 33 5 120 11.0 0.25 42.8 0.0 2.5 0.2 0.0 464 121 342 201 5 0.1 3.0 0.7 0.0 391 225 328 232 5 0.50 86.8 0.1 1445.7 0.1 0.1 941 141586 24175 22485 3 0.1 1445.0 0.3 0.1 871 120528 23996 19160 3 0.75 111.0 0.1 29.7 0.0 0.0 1006 1191 9 129 5 0.5 24.9 0.0 0.0 1003 397 0 113 5 130 11.4 0.25 45.8 0.1 0.8 0.1 0.0 526 83 78 47 5 0.1 1.9 2.9 0.0 425 81 69 152 5 0.50 92.4 0.1 2163.8 0.2 0.2 1084 241228 41399 42461 2 0.2 2170.2 0.7 0.2 1029 200187 39595 34222 2 0.75 117.8 0.2 1504.6 0.2 0.2 1136 54437 19 5622 3 0.6 1453.7 0.2 0.2 1252 19674 0 4237 3 24 Table 5: Algorithms BPC-SRPS-E and BPC-SRPS-N on instances E3 and E4 BPC-SRPS-E BPC-SRPS-N CPU (sec.) Gap (%) CPU (sec.) Gap (%) n|Vk|α|V∗| RT OA RT OA #col (17) (18) #nod X RT OA RT OA #col (17) (18) #nod X Group E3 55 6.6 0.25 15.6 0.0 0.0 0.00 0.00 181 0 0 1 5 0.0 0.0 0.01 0.01 160 96114 0 1 5 0.50 34.6 0.0 293.4 0.01 0.00 479 92188 16040 19253 5 0.0 298.5 0.02 0.00 356 95994 13569 18943 5 0.75 48.0 0.0 0.4 0.00 0.00 571 238 0 17 4 0.1 0.1 0.04 0.01 460 6 0 2 4 60 7.6 0.25 24.6 0.0 0.0 0.00 0.00 315 0 0 1 5 0.0 0.0 0.02 0.02 208 0 0 1 5 0.50 44.2 0.0 0.3 0.01 0.01 620 251771 1535 21625 5 0.0 0.5 0.37 0.00 461 234452 0 20 5 0.75 42.0 0.0 1889.5 0.01 0.01 494 228775 902 19715 2 0.1 1889.7 0.07 0.04 603 485942 3854 62995 1 65 8.6 0.25 45.0 0.0 1378.5 0.17 0.11 674 382850 48397 47564 3 0.0 0.0 0.02 0.02 245 2 0 1 5 0.50 58.6 0.0 1313.5 0.02 0.02 744 355333 8735 33387 5 0.0 1441.7 0.74 0.11 553 392324 43570 47989 3 0.75 21.8 0.0 0.0 0.00 0.00 297 2 0 1 3 0.1 1313.8 0.03 0.02 647 386446 4459 32900 3 70 9.0 0.25 50.0 0.1 1441.5 0.10 0.10 784 347230 20966 43153 4 0.0 60.6 0.67 0.02 306 6921 8219 4233 5 0.50 63.2 0.1 537.6 0.01 0.01 841 228635 59 17194 4 0.1 1441.8 0.15 0.10 638 310711 22466 39915 3 0.75 24.6 0.0 52.6 0.07 0.00 376 7905 6806 3803 4 0.2 537.9 0.02 0.01 777 228113 59 17178 4 Group E4 45 7.0 0.25 11.8 0.0 0.0 0.00 0.00 212 0 0 1 5 0.0 0.0 0.00 0.00 182 268344 0 1 5 0.50 27.4 0.0 0.0 0.00 0.00 565 0 0 1 5 0.0 0.0 0.00 0.00 414 1 0 1 5 0.75 38.6 0.0 0.0 0.00 0.00 663 0 0 1 5 0.0 0.0 0.00 0.00 465 0 0 1 5 50 7.4 0.25 13.6 0.0 0.1 0.02 0.00 245 19 1 3 5 0.0 0.1 0.02 0.00 212 457935 1 2 5 0.50 29.8 0.1 2152.7 0.16 0.14 668 763800 11078 69775 3 0.1 2176.4 0.49 0.14 525 726263 17990 69133 3 0.75 41.2 0.0 0.0 0.00 0.00 737 0 0 1 5 0.1 0.1 0.05 0.00 667 17 0 4 5 55 8.0 0.25 16.0 0.0 1.0 0.02 0.00 304 443 45 83 5 0.0 1.2 0.02 0.00 261 494 42 92 5 0.50 33.0 0.1 1443.6 0.12 0.12 765 381420 43569 56451 2 0.1 1444.5 0.72 0.12 648 347938 64204 54033 2 0.75 44.8 0.1 2166.9 0.11 0.11 898 298005 1 18942 3 0.1 2194.7 0.40 0.31 948 288261 0 18495 2 60 9.2 0.25 18.8 0.0 0.1 0.02 0.00 414 13 7 4 5 0.0 0.1 0.02 0.00 345 17 7 4 5 0.50 38.0 0.1 2164.7 0.44 0.44 956 611024 9686 53564 4 0.1 2162.7 0.53 0.44 844 658463 4500 52370 4 0.75 51.4 0.1 2864.3 1.64 1.64 958 363250 0 18561 1 0.2 2890.9 1.53 1.49 1190 323703 0 20155 1 25 (A.7): the expressions linking the ow variables xk ij and the time variables sk i and sk j satisfying the precedence constraints on jobs i and j processed by k ; (A.8): the horizon length; (A.9)(A.10): the binary requirements on the xk and yk variables. The domain Dk is a bounded polyhedron and an extreme point of the convex hull of Dk is a path r∈Ωk . For each path r∈Ωk , in coherence with notation in Section 4.3, let us denote by  xk ij,r the characteristic vector being 1 if and only if (i, j)∈Ak is in r ,  yk j,r the characteristic vector being 1 if and only if j∈Jk is processed along r , and  sk ij,r a non-negative number representing the time to process k along r . Any solution (xk, yk, sk) in the convex hull of Dk can be written as X r∈Ωk λk r= 1 (A.13) λk r≥0r∈Ωk (A.14) X r∈Ωk xk ij,rλk r=xk ij (i, j)∈Ωk (A.15) X r∈Ωk yk j,rλk r=yk jj∈Jk (A.16) X r∈Ωk sk j,rλk r=sk jj∈Jk. (A.17) The substitution of the above consideration in Model SPR-1' gives the Dantzig-Wolfe master problem described by DWαβγπ by (A.1) subject to (A.9)(A.17) for all k∈K . For processor k∈K , the reduced cost ¯ck r of variable λk r for each r∈Ωk is ¯ck r= 0 −αk+X (i,j)∈Ak xk ij,rβk ij +X j∈Jk yk j,rπk j+X j∈Jk sk j,rσk j, where βk ij , πk j and σk j are the dual variables of (A.15), (A.16) and (A.17), respectively, of the linear relaxation of DWαβγπ . This means that nding the maximum reduced cost for processor k is equivalent to solve the following minimization subproblem, denoted by SPk αβγπ : αk+ min X (i,j)∈Ak xk ij,rβk ij +X j∈Jk yk j,rπk j+X j∈Jk sk j,rσk j subject to (A.2)(A.10). This subproblem is an elementary time-constrained shortest-path problem with linear node costs (see e.g. Ioachim et al. [22]). The objective function includes 32  a x cost αk given by the master solution;  the dual value βk ij as a rst part of the cost on each arc (i, j)∈Ak of the path;  the dual value πk j as a second part of the cost on each arc entering node j∈Jk ;  the dual value σk j is a cost on each node j∈Jk to pull backward or push forward (depending whether σk j is positive or negative) the value of sk j in the synchronization process. Constraints (A.6) assign zero time to unprocessed jobs, thus sk jσk j= 0 and therefore no impact in the objective function for unprocessed jobs. Another approach to deal with SPR-1' is to reformulate only the x -variables when using the Dantiz-Wolfe Decomposition. In this case, the master problem, denoted as DWαβ , is modeled by (A.1) subject to (A.13)(A.15) and (7)(11). The subproblem, denoted as SPαβ , is again the elementary time-constrained shortest-path problem SPk αβγπ but now with the simpler objective function αk+ min X (i,j)∈Ak xk ij,rβk ij. Note that in this case, since the s -variables are not reformulated, the constraints 0≤sj≤Lyj for all j∈J are unnecessary. Model SPR-3 diers from the master problem DWαβ in the precedence constraints (8) and (9) of the processed jobs described by the set ˜ A for a binary solution (˜x, ˜y) . These constraints are replaced by the combinatorial cuts (17) and (18) in Model SPR-3 to have only binary variables. 33