Design and development of CSP techniques for finding robust solutions in job-shop scheduling problems with Operators

UNIVERSIDAD POLITÉCNICA DE VALENCIA DEPARTAMENTO DE SISTEMAS INFORMÁTICOS Y COMPUTACIÓN DESIGN AND DEVELOPMENT OF CSP TECHNIQUES FOR FINDING ROBUST SOLUTIONS IN JOB-SHOP SCHEDULING PROBLEMS WITH OPERATORS Master Thesis in Artificial Intelligence, Pattern Recognition and Digital Imaging September 2012 Supervised by: Dr. Miguel Á. Salido Gregorio Dr. Federico Barber Sanchís Presented by: Joan Escamilla Fuster DESIGN AND DEVELOPMENT OF CSP TECHNIQUES FOR FINDING ROBUST SOLUTIONS IN JOB-SHOP SCHEDULING PROBLEMS WITH OPERATORS Joan Escamilla Fuster Master Thesis in Artificial Intelligence, Pattern Recognition and Digital Imaging Departamento de Sistemas Informáticos y Computación Valencia, 2012 Contents 1 Introduction 1 1.1 Introduction............................. 1 1.2 Motivation.............................. 2 2 Constraint Satisfaction Problems 5 2.1 Introduction............................. 5 2.2 ModellingaCSP .......................... 5 2.3 Example of a CSP: Map Colouring Problem . . . . . . . . . . . . 6 2.4 SolvingaCSP............................ 7 2.4.1 Consistency Techniques . . . . . . . . . . . . . . . . . . 7 2.4.2 Search techniques . . . . . . . . . . . . . . . . . . . . . . 8 2.4.3 Hybrid techniques . . . . . . . . . . . . . . . . . . . . . 9 2.5 Robustness and stability . . . . . . . . . . . . . . . . . . . . . . 10 3 Job-Shop Scheduling Problem With Operators 13 3.1 Introduction to Job-Shop Scheduling Problem . . . . . . . . . . . 13 3.2 Problem Description . . . . . . . . . . . . . . . . . . . . . . . . 13 3.3 Techniques to solve Job-Shop Scheduling Problem . . . . . . . . 14 3.4 Extension with operators . . . . . . . . . . . . . . . . . . . . . . 17 3.5 Robustness in Job-Shop Scheduling Problem . . . . . . . . . . . 18 4 Modelling JSO(n, p)as a CSP 21 4.1 Introduction............................. 21 4.2 A modelling Phase . . . . . . . . . . . . . . . . . . . . . . . . . 21 4.3 SolvingPhase............................ 24 5 HeuristicAlgorithmsforFindingRobustSolutionsinJob-ShopScheduling Problem with Operators 27 5.1 Introduction............................. 27 5.2 First Step: Modeling and Solving a Constraint Satisfaction and Optimization Problem . . . . . . . . . . . . . . . . . . . . . . . . . 27 5.3 Second Step: A Post-process Procedure . . . . . . . . . . . . . . 28 5.4 Third Step: Distributing Buffer Algorithm . . . . . . . . . . . . . 29 5.5 Anexample............................. 30 i 6 Evaluation 33 6.1 JSO(n, p)CSP model Evaluation . . . . . . . . . . . . . . . . . 33 6.2 Evaluation of heuristic algorithm for robust solutions in JSO(n, p)35 7 Conclusions and Future Work 41 7.1 Conclusions............................. 41 7.2 Futurework............................. 42 7.3 Related publications . . . . . . . . . . . . . . . . . . . . . . . . . 42 ii List of Figures 2.1 An example colouring problem . . . . . . . . . . . . . . . . . . . 6 3.1 Disjunctive graph for a job-shop scheduling problem. . . . . . . . 14 3.2 A feasible solution via a direct graph. . . . . . . . . . . . . . . . 15 4.1 Partial instance of a job-shop problem represented in XCSP. . . . 22 5.1 A scheduling problem: an optimal and a robust solution. . . . . . 31 6.1 Set of solutions for an instance given . . . . . . . . . . . . . . . . 36 6.2 Computational time to calculate the step 1 and the step 2 + step 3 . 38 iii iv List of Tables 3.1 Example of a job-shop problem . . . . . . . . . . . . . . . . . . . 14 6.1 Avg. Makespan and Computational time (pi= [1,10]) . . . . . . 34 6.2 Avg. Makespan and Computational time (pi= [1,50]) . . . . . . 34 6.3 Avg. Makespan and Computational time (pi= [1,100]) . . . . . . 34 6.4 Avg. Makespan and Robustness . . . . . . . . . . . . . . . . . . 37 6.5 Avg. Robustness with large incidences (pi= [1,100]) . . . . . . . 39 v 4 Chapter 2 Constraint Satisfaction Problems 2.1 Introduction Constraint Programming is a software technology used to represent and solve large and complex problems from many real life areas. Many of these problems can be modeled as constraint satisfaction problems and solved using constraint programming techniques. Examples include scheduling, planning, temporal reasoning, design engineering, packing problems, cryptography, diagnosis, etc. The complexity of this type of problem is NP [27]. A CSP is composed with a set of variables where each one can take values of a specific domain. There is a set of constraints that limit the number of values that each variable can take. The objective is to select a value to each variable satisfying the set of constraints. The resolution of a CSP has two phases: The first one is to model the problem using the correct syntax and the second part is to solve the problem using one of the different techniques. 2.2 Modelling a CSP A constraint satisfaction problem (CSP) is a triple (X, D, C)where: • X ={x1, x2, ..., xn}is a set of nvariables. • D ={d1, d2, ..., dn}is a set of domains, such that each variable xi∈Xhas a finite set of possible values di. • C ={c1, c2, ..., cm}is a finite set of constraints which restrict the values that the variables can simultaneously take. A constraint can be defined in intensional or extensional form although both can be equivalent. 5 •Intensional constraints: Constraints are represented as mathematic or logical function. Example. x1≤4is a unary intensional constraint. •Extensional constraint: Constraints are represented as a set of valid or invalid tuples. Example. The set of tuples {(0),(1),(2),(3),(4)}is the extensional representation of the constraint x1≤4by means of valid tuples, considering the domain d1:{0..10}for x1. 2.3 Example of a CSP: Map Colouring Problem The Map Colouring problem tries to colour the areas in map using a number of colours but with the condition that the neighbouring areas have different colours. The map colouring problem can be represented as a graph colouring problem to color the vertices of a given graph using predefined number of colours in such a way that connected vertices get different colours. It is very easy to model this problem as a CSP. There are as many variables as vertices, and the domain for each variable contains the colours to be used. If there is an edge between the vertices represented by variables xand y, then there is an inequality constraint referring to these two variables, namely: x6=y. Figure 2.1: An example colouring problem Graph colouringisknowntobeNP-complete, soonedoesnotexpect apolynomialtime algorithm to be found for solving this problem. It is easy to generate a large number of test graphs with certain parameters, which are more or less difficult to be coloured, so the family of graph colouring problems is appropriate to test algorithms thoroughly. Furthermore, many practical problems, like ones from the field of scheduling and planning, can be expressed as an appropriate graph colouring problem [37]. 6 Figure 2.1 shows an example of map colouring problem and its graph representation. The map is composed on four regions/variables x, y, z, w to be coloured. Each regioncan be coloured in three different colours: red (r), green (g) or blue (b). So the domain of each variable is r,g,b. Each edge represents the binary constraint which restricts that two adjacent regions must be coloured with different colours. There are five constraints because there are five edges. A possible solution is the assignation (x=r), (y=g), (z=g) and (w=b). 2.4 Solving a CSP A CSP can be solved by assigning values to each variable, the solution space can be seen as a search tree. In each level, a variable is instantiated and the successors of a node are the variable values of this level. Most algorithms for solving CSPs search systematically through the possible assignments of values to variables. Such algorithms are guaranteed to find a solution or to prove that the problem is insoluble. Prune is only used if the partial search tree contains not solution. The disadvantage of these algorithms is that they may take a very long time to find a solution. 2.4.1 Consistency Techniques Consistency techniques were introduced for improving the efficiency of search techniques. The number of possible combinations can be huge, while only very few are consistent. By eliminating redundant values from the problem definition, the size of the solution space decreases. Reduction of the problem can be done once, as a pre-processing step for another algorithm, or step by step, interwoven with the exploration of the solution space by a search algorithm. Local inconsistencies are single values or combination of values for variables that cannot participate in any solution because they do not satisfy some consistency property [27]. For instance, if a value aof variable xiis not compatible with all the values in a variable xjthat is constrained with xi, then ais inconsistent and this value can be removed from the domain of the variable xi. In the following paragraphs we introduce the most well-known and widely used algorithms for binary CSPs. •A CSP is node-consistent if all the unary constraints hold for all the elements of the domains. The straightforward node-consistency algorithm (NC), which removes the redundant elements by checking the domains one after the other, has O(dn)time complexity, where d is the maximum size of the domains. Thus, enforcing this consistency ensures that all values of the variable satisfy all the unary constraints on that variable. •A CSP is arc-consistent [27] if for any pair of constrained variables xi,xj, for every value ain Dithere is at least one value bin Djsuch that the assignment (xi,a) and (xj,b) satisfies the constraint between xiand xj. Any value in the domain Diof variable xithat is not arc-consistent can be 7 removed from Disince it cannot be part of any solution. Arc-consistency has become very important in CSP solving and it is in the heart of many constraint programming languages. The optimal algorithms to make the CSP arc-consistent require time O(ed2), where e is the number of constraints (arcs in the constraint network) and d is the size of domains. Arc-consistency can also be easily extended to non-binary constraints. •A CSP is path-consistent [30], if for every pair of values aand b for two variables xiand xj, such that the assignments of ato xiand b to xjsatisfies the constraint between xiand xj, there exist a value for each variable along any path between xiand xjsuch that all constraints along the path are satisfied. When a path-consistent problem is also node-consistent and arc-consistent, then the problem is said to be strongly path-consistent. Consistency techniques can be exploited during the forward checking stage of search algorithms in the following way. Each time some search decision is done (for example, a value is assigned to the variable), the problem is made arc consistent (arc consistency is typically used during search due to it is low time and space complexity). If failure is detected (any domain becomes empty) then it is not necessary to instantiate other variables and backtracking occurs immediately. 2.4.2 Search techniques Most algorithms for solving CSPs search systematically through the possible assignments of values to variables. Such algorithms are guaranteed to find a solution, if one exists, or to prove that the problem is insoluble. The disadvantage of these algorithms is that they may take a very long time to do so. The actions of many search algorithms can be described by a search tree. Generate and Test. The generate-and-test (GT) method originates from the naive approach to solving combinatorial problems. First, the GT algorithm guesses the solution, and then it tests whether this solution is correct, that is, whether the solution satisfies the original constraints. In this paradigm, each possible combination of the variable assignments is systematically generated and tested to see if it satisfies all the constraints. The first combination that satisfies all the constraints is the solution. The number of combinations considered by this method is the size of the Cartesian product of all the variable domains. The main disadvantage is that it is not very efficient because it generates many assignments of values to variables which are rejected in the testing phase. In addition, the generator leaves out the conflicting instantiations and generates other assignments independently of the conflict. Visibly, one can get far better efficiency if the validity of the constraint is tested as soon as its respective variables are instantiated. 8 Backtracking. A simple algorithm for solving a CSP is backtracking search (BT) [5]. Backtracking works with an initially empty set of consistent instantiated variables and tries to extend the set to a new variable and a value for that variable. If successful, the process is repeated until all variables are included. If unsuccessful, another value for the most recently added variable is considered. Returning to an earlier variable in this way is called a backtrack. If that variable doesn’t have any further values, then the variable is removed from the set, and the algorithm backtracks again. The simplest backtracking algorithm is called chronological backtracking because at a dead-end the algorithm returns to the immediately earlier variable in the ordering. In the BT method, variables are instantiated sequentially and as soon as all the variables relevant to a constraint are instantiated, the validity of the constraint is checked. If a partial solution violates any of the constraints, backtracking is performed to the most recently instantiated variable that still has alternatives available. Clearly, whenever a partial instantiation violates a constraint, backtracking is able to eliminate a subspace from the Cartesian product of all variable domains. 2.4.3 Hybrid techniques In section 2.4.2 some search techniques to solve CSPs have been presented. In section 2.4.1 some consistency techniques that delete inconsistent values from the variable domain have been presented. Therefore, consistency techniques can be used as a pre-process step where inconsistencies can be detected and removed. Otherwise, consistency techniques can be used in the search process. Some of these hybrid techniques are based on look-back and look-ahead techniques. •Look-Back Algorithms: BT can suffer from thrashing; the same dead end can be encountered many times. If xiis a dead end, the algorithm will backtrack to xi−1. Suppose a new value for xi−1exists, but that there is no constraint between xiand xi−1. The same dead end will be reached at xi again and again until all values of xi−1have been explored. Look-back algorithms try to exploit information from the problem to behave more efficiently in dead-end situations. Like BT, look-back algorithms perform consistency checks backward (between the current variable and past variables). Backjumping (BJ) [10] is an algorithm similar to BT except that it behaves in a more intelligent manner when a dead end (xi) is found. Instead of BT to the previous variable (xi−1), BJ backjumps to the deepest past variable xj, j,ithat is in conflict with the current variable xi. It is said that variable xjis in conflict with the current variable xiif the instantiation of xjprecludes one of the values in xi. Changing the instantiation of xjmay make it possible to find a consistent instantiation of the current variable. Thus, BJ avoids any redundant work that BT does by trying to reassign variables between xjand 9 the current variable xi. Conflict-directed BJ [33], backmarking [11], and learning [9] are examples of look-back algorithms. •Look-Ahead Algorithms: As we have explained, look-back algorithms try to enhance the performance of BT by more intelligent behavior when a dead end is found. Nevertheless, they still perform only backward consistency checks and ignore the future variables. Look-forward algorithms make forward checks at each step of the search. Let us assume that, when searching for a solution, the variable xiis given a value which excludes all possible values for the variable xj. In case of uninformed search, this will only turn out when xjwill be considered to be instantiated. Moreover, in case of BT, thrashing will occur: the search tree will be expanded again and again until xj, as long as the level of BT does not reach xi. Both anomalies could be avoided by recognizing that the chosen value for xicannot be part of a solution as there is no value for xj, which is compatible with it. Lookahead algorithms do this by accepting a value for the current variable only if, after having looked ahead, it could not be seen that the instantiation would lead to a dead end. When checking this, problem reduction can also take place by removing values from the domain of the future variables that are not compatible with the current instantiation. The algorithms differ in how far and thorough they look ahead and how much reduction they perform. Forward-checking (FC) [16] is one of the most common look-forward algorithms. It checks the satisfiability of the constraints, and removes the values which are not compatible with the current variable’s instantiation. At each step, FC checks the current assignment against all the values of future variables that are constrained with the current variable. All values of future variables that are not consistent with the current assignment are removed from their domains. If a domain of a future variable becomes empty, the assignment of the current variable is undone and a new value is assigned. If no value is consistent, then BT is carried out. Thus, FC guarantees that at each step the current partial solution is consistent with each value in each future variable. Thus, FC can identify dead ends and prune the search space sooner. 2.5 Robustness and stability The concepts of robustness and stability in constraint satisfaction have been mixed and there is a misunderstanding between the two concepts. Some researchers talk about stability and others about robustness. But, what is the difference between stable and robust? It is the first question that comes to mind, especially for researchers who work with quantitative models or mathematical theories. In general, a solution is stable in a dynamic system, if by means of a few changes in the solution we can obtain a new solution that is similar to the original one. However the robustness concept is broader than the stability concept. Ro10 bustness is a measure of feature persistence in systems that compel us to focus on perturbations because they represent changes in the composition or topology of the system. The perturbations are small differences in the actual state of the system [21]. Taking into account all these concepts, we can classify the nature of the solutions as: •The stability (also called flexibility) of a solution is the ability of a solution to share as many values as possible with a new solution if a change occurs [17]. It is measured in terms of similarity of the new solution with the original one. •The robustness of a solution is the measure of the persistence of the solution after modifications in the original solution. Thus, a solution is robust if it has a high probability of remaining valid faced with changes in the problem. It is measured in terms of the persistence of the solution. Sometimes the robustness is related with the information of the problem. Normally, in a problem that no information is given, the probability of something goes wrong or the probability that something cannot be finished in the predicted time is equal in all the cases. However sometimes there is information about the problem because there are some historic as previous experiments where some probabilistic cases can be used, or the help of an expert can be used. When there is no information usually the probability that something happens has to be proportional. 11 12 Chapter 3 Job-Shop Scheduling Problem With Operators 3.1 Introduction to Job-Shop Scheduling Problem Job-shop scheduling problems (JSP) are among the most intensive combinatorial problems studied in literature. An instance with ten jobs to be processed on ten machines, formulated in 1963, was open for more than 25 years. It was finally solved by a branch-and-bound algorithm. Very simple special cases of the jobshop problem are already strongly NP-hard. After a short review of these old challenges, we consider practical applications in flexible manufacturing, multiprocessor task scheduling, robotic cell scheduling, railway scheduling, air traffic control which all have an underlying job-shop structure. Methods to solve these problems and new challenges in connection with them are indicated. 3.2 Problem Description The job-shop scheduling problem can be defined as follows. We are given a set {J1,...,Jn} of njobs that require, for their processing, a set of mresources or machines {R1, . . . , Rm}. Each job Jiconsists of a sequence of vitasks (θi1,...,θivi). Each task θil has a single resource requirement Rθil , an integer duration pθil and a start time stθil to be determined. A feasible schedule is a complete assignment of starting times to tasks that satisfies the following constraints: (i) the tasks of each job are sequentially scheduled, (ii) each machine can process at most one task at any time, (iii) no preemption is allowed. The objective is finding a feasible schedule that minimizes the completion time of all the tasks, i.e. the makespan. In this framework, it is useful to represent the job-shop scheduling problem in terms of a disjunctive graph G= (V, A, E)[2], where Vis the set of nodes, Ais the set of ordinary arcs (conjunctive) and E the set of disjunctive arcs. The nodes of G(V) correspond to operations, the directed arcs (A) to precedence relation, 13 20 Chapter 4 Modelling JSO(n, p)as a CSP 4.1 Introduction In this chapter JSO(n, p)is modelled as a CSP and solved using a look-ahead algorithm (Forward-checking). By using this algorithm, a solution can be obtained, However the main aim of this problem is not to obtain a solution but to obtain an optimized solution. To this end a branch and bound technique has been developed. When a solution is found the algorithm remains looking for more solutions that improve the obtained solutions. When the objective is not only to get a solution of the problem but an optimized solution it is named Constraint Satisfaction and Optimization Problem (CSOP). 4.2 A modelling Phase In this approach, we proposed to model the JSO(n, p)as a Constraint Satisfaction and Optimization Problem (CSOP) [4]. The CSOP model for a JSO(n, p)is characterized by the following elements: •A set of variables x1, ..., xnassociated with the start time of tasks and with the operator responsible for carrying out each task. These variables take valuesin finite domains D1, ..., Dnthat may be constrained byunaryconstraints over each variable. In these problems, time is usually assumed discrete, with a problem-dependent granularity. •A set of constraints c1, ..., cmamong variables defined on the Cartesian product Di×... ×Djand restrict the variable domains. •The objective function is to minimize the makespan. Three main constraints appear in this kind of job-shop problems: 1. Precedence constraints: The tasks θij of each job Jimust be scheduled according to precedence constraints, i.e., there exists a partial ordering among 21 the tasks of each job and may be represented by a precedence graph or treelike structure [38]. 2. Capacity constraints: Resources cannot be used simultaneously by more than one task. Thus, two different tasks θij and θik cannot overlap unless they use different resources. 3. Operator constraints: An operator can not handle more than one task at a time. To modeling the JSO(n, p)as a CSOP we have used the syntax XCSP [36]. The Extensible Markup Language presents a simple and flexible text format and it gives the facility to use some functions and structures defined in Abscon [26]. In the figure 4.1, it can be seen an example of a representation of a job-shop partial instance represented in XCSP. Figure 4.1: Partial instance of a job-shop problem represented in XCSP. In the modeling phase, we have applied two different filtering techniques to reduce the variable domains. The first technique developed (Algorithm 1) calculates initials values of each tasks and reduces the domain size of the involved variables. These techniques are similar to the filtering techniques presented in chapter 2 (node consistency, arc-consistency).Thus, a solution can be found more efficiently. This 22 algorithm calculates the maximum time interval in which each task can be scheduled. On the one hand, given a θij task, the lowest value of its stθij is the sum of the processing times of the tasks that has to be scheduled before θij from the same job i(cumulativeij), subject to the precedence constraints. On the other hand, the highest value of all the domains for stθij is the sum of all processing times (maxT ime), since this value represents the end of the schedule where the tasks are scheduled linearly. Due to the fact that at least the following tasks from the same job must be scheduled before maxT ime, the highest value for the domain of each task θij can be reduced by subtracting the duration of all the tasks from the same job ithat have to be scheduled after θij (including θij) to maxT ime. Algorithm 1: Calculate initial values to reduce domain Data:J: set of jobs; Result: Relative starts to each task and lineal maxtime maxT ime := 0; cumulativeij := 0,∀θij ∈θ; foreach i∈Jdo cumulativeJob ← {0}; foreach θij ∈θdo maxT ime := maxT ime +pt; cumulativeij ←cumulativeJob; cumulativeJob ←cumulativeJob ∪ {pθij }; return cumulative, maxT ime; The values cumulativeij and maxT ime obtained in Algorithm 1 are used to filter the domains by removing values that cannot take part of feasible solutions. In the second technique to reduce the variable domains (Algorithm 2), the values that cannot be possible are calculated. stθij only should get values that represent the sum of the tasks that can be executed before θij. Algorithm 2: Calculate possible values Data: All tasks Result: New domain of all θ pV aluesjt ← ∅,∀θij ∈θ; foreach i∈Jdo foreach θij ∈θdo tasksBefore ←tasksCanBeBefore(θij ) pV aluesij ←combineDurTasks(tasksBefore) return pV alues For example, if θij is the first task of its job, the possible values are 0 and a set of the combination of the processing times of all the tasks Tthat can be scheduled before θij. In this case, these tasks Tare all the tasks of the other jobs. For the following task (θij+1), its possible values stθij+1 are the same as θij plus the processing time of θij. In the Algorithm 2, tasksCanBeBefore function returns the tasks that can be executed before a given task θij; and, combineDurTask function 23 calculates all the possible values for stθij following the precedence constraints. Thus, by applying these filtering techniques, the variable domains are reduced and the solving phase can be executed in a more efficient way. 4.3 Solving Phase Once a CSOP has been modeled and the domains filtered, it is solved by using a modified algorithm of Forward Checking (FC) (Algorithm 3). When a solution has been found, the algorithm tries to found more solutions with a Branch and Bound technique. Filtering techniques are also used but prune is only used when the set of not analysed solutions cannot improve the best obtained one. For this reason no solution is lost. Instead of applying Maintaining Arc-Consistency, this algorithm performs a filtering procedure that removes the domains in blocks, i.e., it removes several values at a time. This is due to the fact that if a task θij must be scheduled after task θkl, the stθij can take neither the value of the stθkl nor all successive values until the ending time of θkl. Thus, all these values can be removed as a block of values. The values to delete depend on the type of constraint. If this is a precedence constraint, all the values before θkl plus its processing time will be deleted. Otherwise, if it is a capacity constraint, the values between stθkl (included) and its processing time will be deleted. Algorithm 3: Select-value-forward-checking with deletion block while D′ i6=∅do select first element a∈D′ i, and remove afrom Di forall k, i < k ≤ |D′|do if constraint(i,k) = MachineOrJobConstraint then if constraint(i,k)= JobConstraint then remove values if(valk< a +duri) from D′ k else remove values if(valk+durk≥a∧valk< a +duri) from D′ k else forall b∈D′ kdo if not CONSISTENT (ai−1,xi:= a, xk:= b)then remove bfrom D′ k if D′ k=∅then reset each D′ k, i < k ≤nto value before awas selected else return a return null Some heuristic techniques have been applied to improve the speed and efficiently solving the problem. Variable selection and value selection are two critical tasks, and with a good heuristic technique can improve the results. The variable selection is really important because a good solution can be obtained early and it makes more efficient the prune. Also the value selection is important because the 24 values of temporal variables are selected in increase order and the smallest value for each temporal variable is selected. This is due to the fact that if a task can start in a defined domain of time interval, the earliest value will be probably the value that minimizes the makespan. The variable selection heuristic that has given better results is to select the firsts tasks of each job. 25 26 Chapter 5 Heuristic Algorithms for Finding Robust Solutions in Job-Shop Scheduling Problem with Operators 5.1 Introduction In chapter 4 a model to solve JSO(n, p)with a CSP implementation with the objective to get an optimal solution of the problem has been presented. It is wellknown the trade-off between robustness and optimality. This aim would be used to calculate a robust solution without lose a big part of optimality. But this job is really difficult to archive, so a new technique has been developed and it is presented in this chapter. Our technique has been classified in three steps [8]. At the first step, the job shop problem without taking account operators is solved, so that an optimized solution minimizing the makespan is obtained. In the second step this solution is modified to take into account the operators, modifying the problem to aJSO(n, p), but now the aim is to get a solution that present a good trade-off between makespan and robustness. In the third step the solution is modified to redistribute the buffers but maintaining the same makespan. 5.2 First Step: Modeling and Solving a Constraint Satisfaction and Optimization Problem In this approach, we proposed to model the JSP, in the first phase, as a Constraint Satisfaction and Optimization Problem (CSOP) [4]. Due to the post-process performed, the optimal solution is not necessary to archive, since this solution will be changed. However, it is still necessary an optimized solution to try to minimize the makespan. Therefore, a near-optimal solution is looked for by our CSOP solver. 27 Nevertheless any solver can be used applied to obtain an optimized solution. Our CSOP solver is an any-time solver that provides a set of solutions. Each new solution always improves the previous one, until an optimal or a time out is reached. The phases of modeling and solving are similar to those described in Chapter 4 but without take into account the operators. Only precedence and capacity constraints are take into account. To model the problem Algorithm 1 and 2 have been used to calculate the initial values of each tasks and reduce the domain. There techniques can be used in a JSP because they do not take into account operators. In the solving phase the techniques presented in Chapter 4 are also used. The problem is solved using the modified FC (Algorithm 3) explained in Chapter 4. 5.3 Second Step: A Post-process Procedure Once the CSOP has been solved and an optimized solution to the job-shop scheduling problem have been obtained, this solution is used to allocate the required number of operators in order to solve the JSO(n, p). This problem consists on finding a feasible schedule by minimizing makespan and maximizing number of buffers (Nbuf ) to guarantee a certain level of robustness. Note that a feasible schedule for JSO(n, p)is also feasible for the standard job-shop problem and satisfies the restriction that at most pmachines work simultaneously. Therefore, significant cases are those in which p < min(n, m), otherwise our problem becomes a standard job-shop problem [1]. The aim of the Algorithm 4 is to convert a solution without operators in one where the operator constraints are considered. The idea is to set a number of machines (remainingMachines) equal to the number of operators pand try to reschedule the tasks of the other machines (machinesF ewerT asks) within the remainingMachines. The tasks in machinesF ewerT asks must be sorted by their st (tasksT oP ut). Each θij in tasksT oP ut is allocated in the first available gap between two tasks of each machine in remainingMachines. For each machine, the search starts from the previous state (savedState). There are cases where θij must be allocated without a gap between two tasks due to the precedence constraints. For instance, if we found a θik of the same job as θij and θik must be scheduled after θij according to the precedence constraints (k > j), θij is allocated just before θik, being delayed θik. When a task is delayed, other tasks may be also delayed. The computational cost of the algorithm is O(tasksT oP ut ∗ |remainingMachines|). The best state to allocate θij is the state that maximizes the function Nbuf Cmax . This function could be adjusted depending on the requirements of the user, e.g. either only minimizing the makespan or maximizing the number of buffers generated. 28 Algorithm 4: Post-process Data:S: Solution without operators; m: machines; p: operators; Result: A solution considering operators Order the machines by their number of tasks; machinesF ewerT asks ←set of m−pmachines with fewer tasks; tasksT oP ut ←tasks of the machines machinesF ewerT asks; remainingMachines ←m−machinesF ewerT asks; Order tasksT oP ut by Starting Times; actualState ←S; foreach θi∈tasksT oP ut do savedState ←actualState; states ← {}; for r∈remainingMachines do foundGap := IsThereAGap(r); if not foundGap then insert θibefore the next task according to its Job; else insert θiin this gap; Delay the needed tasks according to the restrictions among them; states ←states ∪ {actualState}; actualState ←savedState; actualState ←chooseBestState(states); return actualState; 5.4 Third Step: Distributing Buffer Algorithm The previous step gives us an optimized solution that satisfies all constraints of the JSO(n, p). This solution is an optimized solution in terms of minimizing makespan and maximizing the number of buffers. However, the main goal for a robust solution, in a scheduling problem where no information about incidences is given, is to distribute the amount of available buffers among as many tasks as possible. It is well-known that all tasks involved in a critical path have not any associate buffer, because it will affect the makespan. The rest of tasks can be reassigned to generate a buffer after their ending time. The main goal of this algorithm is to distribute the amount of buffers without affecting this makespan. Thus, we can maximize the number. In this way, the obtained solution is considered more robust due to more tasks have buffer times to absorb small incidences. Figure 5.1(b) shows the solution obtained in the second step and all critical paths. It can be observed that 10 buffers were generated, meanwhile the distributing buffer algorithm was able to find 14 buffers. We remark that our goal is to obtain the maximum number of buffers since no information is given about incidences so that all tasks have the same probability for delaying. This third step is presented in Algorithm 5. This algorithm looks for the tasks θij allocated just before each buffer generated in Algorithm 4, and tries to set them back. A task θij is only set back if it generates a new buffer. In case a new buffer 29 0 2 4 6 8 10 200 205 210 215 220 225 Number of buffers (Nbuf) Makespan (Cmax) Cmax Not Nbuf Not Cmax Not Nbuf Not Cmax Nbuf Cmax Nbuf CSOP Step2 ( ) CSOP Step3 ( ) CP Step2 CP Step3 CP operators Non-Dom Sols Figure 6.1: Set of solutions for an instance given right-down square. In the next experiment the first solution given by the CSOP has been chosen to apply the post-procedure mentioned above because it is the solution that gives the opportunity to get more Nbuf . This first solution is compared against the optimal solution. In all cases, 10 instances were considered from each combination and the average results are shown in the next tables. The sets of instances are identified by the tuple: < m_vmax_pi>. The incidences (Z) to assess the robustness were modeled as a delay in a random task θij from the schedule. For each instance, a set of 100 incidences were generated with a delay (d) that follows a uniform distribution between 1 and a 10% of pi. Tables 6.4(a), 6.4(b) and 6.4(c) show the performance of both techniques to absorb incidences. For each technique, we report the Cmax, the number of buffers generated (Nbuf ) in step 3, and the robustness (R) for instances for each m,vmax and pi. Following Lemma 1, the number of buffers showed in these tables is a lower bound of the number of tasks that are not involved in any critical path. For example, in instances <3_10_10 >the optimal solution had an average of 1.2 buffers in the 10 instances evaluated, meanwhile our technique obtained an average of 10.90 buffers in the same instances evaluated. This indicates that in average 10.90 out of 30 tasks were not involved in any critical path and a disruption in one or some of them could be absorbed and the rest of the tasks would not be involved in the disruption. In all instances the average number of buffers obtained by CSOP+PP was bigger than the ones obtained by CP Optimizer. According to the robustness measure and the number of buffers generated, CSOP+PP procedure always outperformed the solutions given by the CP Optimizer, although the makespan turned out to be increased. For instance, in Table 6.4(a) the instances <3_10_10 >increased up to 32.6% the number of incidences absorbed. 36 Table 6.4: Avg. Makespan and Robustness (a) Maximum delay 1 time units Instance CP Optimizer CSOP+PP Cmax Nbuf R(%) Cmax Nbuf R(%) 3_5_10 42.70 2.00 12.50 55.50 4.40 29.20 3_7_10 57.90 1.10 6.80 71.20 7.80 38.60 3_10_10 65.20 1.20 4.60 87.00 10.90 32.60 5_5_10 39.40 0.20 1.20 51.20 4.90 32.90 5_7_10 53.90 0.70 3.10 71.50 7.50 35.90 5_10_10 60.60 0.60 1.70 78.60 8.10 25.50 7_5_10 31.00 0.90 5.40 42.60 5.20 31.10 7_7_10 44.70 0.50 2.30 61.44 5.60 29.40 7_10_10 70.40 0.50 1.50 99.00 8.20 26.90 (b) Maximum delay 5 time units Instance CP Optimizer CSOP+PP Cmax Nbuf R(%) Cmax Nbuf R(%) 3_5_50 201.10 2.20 12.90 232.50 6.60 39.80 3_7_50 267.20 2.20 7.20 317.30 8.80 34.00 3_10_50 353.30 3.50 8.60 450.00 12.60 35.30 5_5_50 184.30 1.20 2.70 252.20 5.70 27.70 5_7_50 253.50 1.10 1.60 340.20 8.30 31.80 5_10_50 363.00 0.90 0.30 467.10 11.60 31.70 7_5_50 177.10 1.10 2.50 237.80 5.80 27.90 7_7_50 252.00 0.40 0.40 380.20 6.20 29.10 7_10_50 363.90 1.00 1.00 512.60 10.40 28.50 (c) Maximum delay 10 time units Instance CP Optimizer CSOP+PP Cmax Nbuf R(%) Cmax Nbuf R(%) 3_5_100 389.00 2.20 12.70 459.00 7.40 41.00 3_7_100 561.40 4.40 16.70 680.90 9.70 38.50 3_10_100 768.70 2.90 4.40 948.90 12.70 34.60 5_5_100 349.00 1.10 2.70 438.90 6.40 34.20 5_7_100 495.00 0.80 0.40 643.90 8.30 33.90 5_10_100 698.20 0.70 1.00 932.10 12.40 35.00 7_5_100 391.40 1.00 2.30 500.80 6.30 37.10 7_7_100 516.00 0.40 2.00 695.80 6.70 27.80 7_10_100 744.80 0.70 0.50 1043.20 10.20 30.00 37 Figure 6.2: Computational time to calculate the step 1 and the step 2 + step 3 It can be seen that for CSOP+PP the greater pi, the greater robustness values since the buffers generated could have bigger sizes, e.g., the instances with m= 5 and vmax = 10 increased their robustness degree obtaining an average of 25.5% for pi= 10;31.7% for pi= 50; and 35% for pi= 100. In the figure 6.2 are presented the computational times to calculate the step 1, CSOP in this case, and the computational time to calculate the post procedure step 2 and step 3. The axis yrepresent the time in second and the axis xrepresent each set of instances. In the graphics can be observed that the computational time of the step 1 is dependent of the durations of task and the number task by job. But for the post procedures the computational time is only dependent of the number of task 38 because the computational time for the post procedures remains stable in the three graphics. Table 6.5 presents how large delays in the incidences affect the schedules. As dincreases, the average of incidences absorbed are reduced, reaching the case that the CP Optimizer obtained an average robustness about 0% for most instances with pi= 100. Even, CP Optimizer was unable to absorb any incidence in instances of <7_10_100 >, whereas the CSOP+PP obtained an average of 6.9% the number of incidences absorbed for large delays. Table 6.5: Avg. Robustness with large incidences (pi= [1,100]) Instance CP Optimizer CSOP+PP d d d d d d [1,20] [1,50] [1,100] [1,20] [1,50] [1,100] 3_5_100 9.90 6.10 3.10 35.20 20.80 11.90 3_7_100 8.90 6.40 3.30 34.90 22.40 12.00 3_10_100 3.80 1.90 1.30 29.10 17.10 9.50 5_5_100 1.90 1.40 0.50 26.90 12.00 8.30 5_7_100 0.20 0.00 0.00 28.60 14.80 8.50 5_10_100 1.00 0.50 0.30 26.70 16.80 10.80 7_5_100 1.90 0.50 0.40 25.00 11.30 6.70 7_7_100 0.80 0.10 0.10 20.10 10.60 5.60 7_10_100 0.00 0.00 0.00 23.50 13.80 6.90 39 40 Chapter 7 Conclusions and Future Work 7.1 Conclusions Job-shopschedulingproblemisarepresentationofahypotheticalproblemofscheduling, the extension with operators give more difficulty to the problem but JSO(n, p) can be closer to the reality. Most of the job-shop solving techniques try to find the optimality of the problem for minimizing the makespan, minimizing tardiness, minimizing flow-time, etc. But with the developed techniques, the solution also try to improve the robustness of the solution. A robust solution can resist small modifications and remains being correct. The developed technique tries to obtain a solution that take into account both makespan and robustness. The JSP with operators is really hard to solve efficiently. At the beginning of this work, the objective was to obtain a solution to the problem with operators by minimizing the makespan, then to obtain a robust solution from the previous optimized solution. A technique for solving the problem was developed but the results were not so goods. For this reason, some techniques were developed to improve the solver and reduce the difficulty of the problem but the problem remained intractable. In this way, the idea of solving the problem in several parts appeared. The technique is composed into three steps. The first step consists in solving a problem without take into account the operators, this step can be done for any job-shop problem solving technique. In this case in the step one the problem has been modelled as a CSP, the output of this step is a correct solution of the problem minimizing the makespan. The advantage if the technique is separated into three steps is that the first step can be only calculated one time. This can be an advantage if the plan of some problems is going to use periodically. The first step can be calculated only one time where the makespan is minimized and in the second step can be controlled the trade-off between robustness and optimality desired by the client. In the second step the problem is modified to take into account operators and the solution is obtained desiring to improve the robustness. In the third step the robustness is increased because the number of buffers is also increased. The computational time cost to execute the second and third step is low comparing the 41 time needed to execute the first step. For this reason this steps can be calculated repeatedly without causing a very high computational cost and the most expensive step is calculated only once. 7.2 Future work The previous section shows techniques to obtain solutions that take into account robustness to absorb incidences. Related to this robustness concept, a study of the different robustness measures could be carried out. These robust solutions have the property to absorb incidences but losing optimality against optimal solution. However a good point to take into account is to analyze the trade-off between optimality and robustness. Therefore, a good line of future work is, given an optimal solution, to provide different robust solutions according to the optimality level that the client is willing to lose from the optimal solution given by the first step. The technique developed in this work is specific for this problem (JSO(n, p)) because between the step one and two, there is a change in the problem due to the introduction of a new resource: the operators. This idea of this Master Thesis about simplifying the problem to model and solve it easier and more efficient can be used in other problems in the real world. Therefore, another future work could be designing a general technique to apply it for more schedule problems. 7.3 Related publications In this section, it is shown a list of published publications to conferences. •Carlos Mencía, MaríaR.Sierra, MiguelA.Salido, JoanEscamillaandRamiro Varela. Combining Global Pruning Rules with Depth-First Search for the Job Shop Scheduling Problem with Operators. In 19th International Workshop on Experimental Evaluation of Algorithms for Solving Problems with Combinatorial Explosion, RCRA 2012. •Joan Escamilla, MarioRodriguez-Molins, MiguelA.Salido, MaríaR.Sierra, Carlos Mencía and Federico Barber. Robust Solution to Job-Shop Scheduling Problems with Operators. In 24th International Conference on Tools with Artificial Intelligence, ICTAI 2102 (CORE B). 42 Bibliography [1] A. Agnetis, M. Flamini, G. Nicosia, and A. Pacifici. A job-shop problem with one additional resource type. Journal of Scheduling, 14(3):225–237, 2011. [2] E. Balas. Machine sequencing via disjunctive graphs: an implicit enumeration algorithm. Operations research, pages 941–957, 1969. [3] I. Barba, C. Del Valle, and D. Borrego. A constraint-based job-shop scheduling model for software development planning. Actas de los Talleres de las Jornadas de Ingeniería del Software y Bases de Datos, 3(1), 2009. [4] J.C. Beck. A schema for constraint relaxation with instantiations for partial constraint satisfaction and schedule optimization. PhD thesis, University of Toronto, 1994. [5] J.R. Bitner and E.M. Reingold. Backtrack programming techniques. Communications of the ACM, 18(11):651–656, 1975. [6] EA Boyd and R. Burlingame. A parallel algorithm for solving difficult jobshop scheduling problems. Operations Research Working Paper, Department of Industrial Engineering, Texas A&M University, College Station, Texas, pages 77843–3131, 1996. [7] APG Brown and ZA Lomnicki. Some applications of the" branch-and-bound" algorithm to the machine scheduling problem. Operations Research, pages 173–186, 1966. [8] J. Escamilla, M. Rodriguez-Molins, M. A. Salido, M. R. Sierra, C. Mencía, and F. Barber. Robust solution to job-shop scheduling problems with operators. In 24th IEEE International Conference on Tools with Artificial Intelligence, 2012.(ICTAI 2012). IEEE. [9] D. Frost and R. Dechter. Dead-end driven learning. In Proceedings of the National Conference on Artificial Intelligence, pages 294–294. JOHN WILEY & SONS LTD, 1994. [10] J. Gaschig. Performance measurement and analysis of certain search algorithms. Technical report, DTIC Document, 1979. 43 [11] J. Gaschnig. A general backtrack algorithm that eliminates most redundant tests. In Proceedings of the Fifth International Joint Conference on Artificial Intelligence, pages 457–457, 1977. [12] F. Glover. Future paths for integer programming and links to artificial intelligence. Computers & Operations Research, 13(5):533–549, 1986. [13] F. Glover. Tabu search-part ii. ORSA Journal on computing, 2(1):4–32, 1990. [14] F. Glover et al. Tabu search-part i. ORSA Journal on computing, 1(3):190– 206, 1989. [15] J.F. Gonçalves, J.J. de Magalhães Mendes, and M.G.C. Resende. A hybrid genetic algorithm for the job shop scheduling problem. European journal of operational research, 167(1):77–95, 2005. [16] R.M. Haralick and G.L. Elliott. Increasing tree search efficiencyforconstraint satisfaction problems. Artificial intelligence, 14(3):263–313, 1980. [17] E. Hebrard, B. Hnich, and T. Walsh. Super csps. Technical report, Technical report, 2003. [18] J.H. Holland. Adaptation in natural and artificial systems. Number 53. University of Michigan press, 1975. [19] E. Ignall and L. Schrage. Application of the branch and bound technique to some flow-shop scheduling problems. Operations Research, pages 400–412, 1965. [20] A.S. Jain and S. Meeran. Job-shop scheduling using neural networks. International Journal of Production Research, 36(5):1249–1272, 1998. [21] E. Jen. Stable or robust? whats the difference? Complexity, 8(3):12–18, 2003. [22] H. Kitano. Towards a theory of biological robustness. Molecular Systems Biology, 3(137), 2007. [23] S. Kobayashi, I. Ono, M. Yamamura, et al. An efficient genetic algorithm for job shop scheduling problems. In Proceedings of the 6th International Conference on Genetic Algorithms, pages 506–511. Morgan Kaufmann, San Francisco. CA, 1995. [24] M. Laguna, J.W. Barnes, and F.W. Glover. Tabu search methods for a single machine scheduling problem. Journal of Intelligent Manufacturing, 2(2):63– 73, 1991. [25] M. Laguna and F. Glover. Integrating target analysis and tabu search for improved scheduling systems. Expert Systems with Applications, 6(3):287– 297, 1993. 44 [26] C. Lecoutre and S. Tabary. Abscon 112 toward more robustness. 2008. [27] A.K. Mackworth. Consistency in networks of relations. Artificial Intelligence, 8(1):99–118, 1977. [28] C. Mencía, M. R. Sierra, M. A. Salido, J. Escamilla, and R. Varela. Combining global pruning rules with depth-first search for the job shop scheduling problem with operators. In 19th RCRA International Workshop on Experimental Evaluation of Algorithms for Solving Problems with Combinatorial Explosion, 2012. [29] R. Mencía, M. R. Sierra, C. Mencía, and R. Varela. Genetic algorithm for jobshop scheduling with operators. In Proceedings of IWINAC 2011(2). LNCS 6687, pages 305–314. Springer, 2011. [30] U. Montanari. Networks of constraints: Fundamental properties and applications to picture processing. Information sciences, 7:95–132, 1974. [31] W. Nuijten and C. Le Pape. Constraint-based job shop scheduling with iilog scheduler. Journal of Heuristics, 3(4):271–286, 1998. [32] F. Pezzella and E. Merelli. A tabu search method guided by shifting bottleneck for the job shop scheduling problem. European Journal of Operational Research, 120(2):297–310, 2000. [33] P. Prosser. Hybrid algorithms for the constraint satisfaction problem. Computational intelligence, 9(3):268–299, 1993. [34] M.G.C. Resende. A grasp for job shop scheduling. In INFORMS Spring Meeting, 1997. [35] A. Rizk, G. Batt, F. Fages, and S. Solima. A general computational method for robustness analysis with applications to synthetic gene networks. Bioinformatics, 25(12):168–179, 2009. [36] O. Roussel and C. Lecoutre. Xml representation of constraint networks: Format xcsp 2.1. 2009. [37] Z. Ruttkay. Constraint satisfaction-a survey. CWI Quarterly, 11(2-3):163– 214, 1998. [38] N. Sadeh and M.S. Fox. Variable and value ordering heuristics for the job shop scheduling constraint satisfaction problem. Artificial Intelligence, 86(1):1–41, 1996. [39] M. Sierra, C. Mencía, and R. Varela. Optimally scheduling a job-shop with operators and total flow time minimization. In Advances in Artificial Intelligence: 14th Conf. of the Spanish Association for Artificial Intelligence, Caepia 2011, LNAI 7023, pages 193–202. Springer, 2011. 45