A Multiobjective Constraint Optimization Model for Multimode Repair Plans

A MULTIOBJECTIVE CONSTRAINT OPTIMIZATION MODEL FOR MULTIMODE REPAIR PLANS I. Barba, C. Del Valle and D. Borrego Dpto. Lenguajes y Sistemas Inform´aticos, Universidad de Sevilla, Spain Keywords: Planning, Scheduling, Constraints, Repair, Multiobjective optimization, Multimode project scheduling. Abstract: This work presents a constraint based model for the planning and scheduling of disconnection and connection tasks when repairing faulty parts. The problem involves the ordering and the selection of tasks from a set of alternatives. The goal of the plan is the minimization of the repair duration and cost. The model considers, apart from thedurations, costs and resources for the tasks,the necessary delays and costs due to auxiliary tasks. The tasks can be executed in several operating modes, each one using a different machine or configuration and possibly different duration and cost. The set of all feasible plans are represented by an extended And/Or graph. 1 INTRODUCTION There is an increasing interest for integrating planning and scheduling since real-world problems involve both of them (Boddy et al., 2004). Some of the applications involving such issues are maintenance and repair planning, where there may be a cascading set of choices which affect different features of the plan, such as duration or cost (Smith et al., 2000). Many problems can involve multiple conflicting objectives (Deb, 2008) that should be considered at the same time. This work presents a CSP (Constraint Satisfaction Problem)model for solving a planningproblemcorresponding to the optimal sequencing of disconnection and connection tasks for repairing faulty components. The objective is the minimization of the total repair time and cost, considering different factors that can have an influence on it. The tasks can be executed in several operating modes (Kolisch and Drexl, 1999), each one using a different machine or configuration, and possibly different duration and cost. The rest of the paper is organized as follows: Section 2 details the considered repair problem, Section 3 states the CSP model for planning the reparation of faulty components and, finally, Section 4 presents some conclusions and future work. 2 REPAIR PLANNING In order to repair a faulty part, a sequence of disconnection tasks must be executed to get it, then a repair action would repair the component, and lastly some connection tasks must reconnect the system. The use of And/Or graphs (Homem de Mello and Sanderson, 1990) allows to represent the set of all feasible plans in a natural way. An important advantage of And/Or graph is that it shows the tasks that can be executed in parallel (Fig. 1). Furthermore, both precedence constraints and those related to the selection of tasks for obtaining a correct plan, can be easily obtained from this representation. A feasible repair plan can be seen as a set of tasks that have to be executed, containing: Connection/Disconnection tasks, that are executed on an established machine with a particular configuration and Auxiliary tasks (set-up operations, that change the configuration of a machine when two successive tasks with different configuration use it; and transportation operations, that transport the subsystems between machines when the machine where the subsystem is obtained is different from the one where is required). The tasks can be executed in more than one operating mode, each one using a different machine or configurationandpossibly differentdurationand cost, and will be representedbydifferentAndnodes(i.e. T′ 2 and T′ 3in Fig. 1). A repair graph is a subgraph of the And/Or graph which only contains the tasks that could be necessary to repair some components. Another important consideration is that a connection (disconnection) task T is reversible if its corresponding disconnection (connection) task T′is feasible. The model supposes two 355 Barba I., Del Valle C. and Borrego D. (2009). A MULTIOBJECTIVE CONSTRAINT OPTIMIZATION MODEL FOR MULTIMODE REPAIR PLANS. In Proceedings of the 6th International Conference on Informatics in Control, Automation and Robotics - Intelligent Control Systems and Optimization, pages 355-358 DOI: 10.5220/0002192003550358 Copyright c SciTePress assumptions: (A1) All tasks are reversible and (A2) Subsystems that do not include the faulty components are not disconnected. Taking into account this, other subsystems different from the ones generated by the disconnection process can appear in the connection process. Moreover, disconnection tasks only handle subsystems that contain the faulty component. Although the disconnection process is linear, the connection can contain tasks that may execute in parallel with others. ABCDE ABCD ACD AC A AD BE B C D E T’3 T’2 T’1 T’7 T’9 T’4 T’5 T’6 T’10 T’8 T’11 Figure 1: A simplified disconnection And/Or graph. 3 THE CSP MODEL Constraint Programming(CP) has been evolved in the last decade to a mature field because, among others, of the use of different generic and interchangeable procedures for inference and search, which can be used for solving different types of problems (Rossi et al., 2006). Once a problem is modelled by a CSP, a generic or specialized CSP solver can be used in order to obtain the required solution. Taking into account (A1) and (A2), the graph can be simplified removing those And nodes below the Or nodes corresponding to subsystems which do not contain the faulty part (Fig. 2). 3.1 Variables of the CSP SelectionVariables. Foreach And node, two boolean variables represent if the connection s(T)and disconnection tasks s(T′)are selected for the solution. Furthermore, for each Or node, two boolean variables represent if the subsystem Sappears in the connection s(S)and disconnection processes s′(S). Resource Variables. For each And node, M(T)and M(T′)represent the machines used, and Cf(T)and Cf(T′)are the necessary configuration on them for the connection and disconnection tasks respectively. On the other hand, the machine where a subsystem is obtained after the corresponding disconnection and connection task, are represented by the variables m′(S)and m(S). Time Variables. For each And node, the durations of the associated tasks Dur(T)and Dur(T′)are established. For the auxiliary operations, ∆cht(M,Cf,Cf′) denotes the time needed for changing the configuration of the machine Mfrom Cf to Cf′, and ∆mov(S,M,M′)denotes the time needed for transporting the subsystem Sfrom machine Mto machine M′. Finally, a temporal delay ∆subst(C)is associated to the reparation of the faulty component. On the other hand, for each And node: its starting and ending times, ti(T)and ti(T′),tf(T)and tf(T′). For each Or node, the times when it is obtained after connection, tOR(S), and disconnection,t′ OR(S). Cost Variables. For each And node: its connection Cost(Ti)and disconnection cost Cost(T′ i). Regarding to the auxiliary operations, Costcht(M,Cf,Cf′) denotes the cost of changing the configuration of the machineMfromCf toCf′, andCostmov(S,M,M′)denotes the cost of transporting the subsystem Sfrom machine Mto machine M′. Furthermore, a cost Costsubst(C)is associated to the reparation of the faulty component. On the other hand, for each And node, the selection of the corresponding task Tmay be associated some additional costs: first, the variable costmov(Ti)represents the possible costs associated to the movement of subsystems; and secondly, the variable costcht(Ti)represents the possible costs of change of configuration. The original And/Or graph has been extended, adding new types of links between And nodes. The new links represent non-precedence constraints: due to the use of shared resources by the tasks and due to the change of configurations in the machines. Fig. 2 shows the extended and simplified repair And/Or graph of a system consisting in ABCDE components when substituting D. A typical objective for such a problem would be the minimization of the elapsed time of the plan, given by the variable (tOR(ABCDE)). Another important issue is the total cost of the complete repair plan. In this work, a multiobjective optimization is pursued, encompassing both of them. ICINCO 2009 - 6th International Conference on Informatics in Control, Automation and Robotics 356 ABCDE ABCD ACD AC A AD BE B C D T’3 T’2 T’1 T’7 T’9 T’4 T’5 T’6 T’10 ABCDE ABCD ACD AC AD BE E T3 T2 T1 T7 T9 T4 T5 T6 T10 T8 T11 M2 C3 M1 C1 M3 C4 M1 C2 M2 C3 M1 C2 M3 C2 M3 C6 M2 C1 M2 C4 M1 C2 M2 C4 M3 C3 M2 C5 M1 C2 M3 C2 M3 C6 M2 C4 M2 C5 M1 C2 Figure 2: The simplified repair And/Or graph with relations (5) and (6) between tasks ... ... (1) (2) (3) (4) (5) (6) Figure 3: Types of Relations 3.2 Types of Constraints Six types of relations are considered (Fig. 3), each one representing a link or component of the extended graph (Fig. 2): Relations of type (1) collect the relation between the informationfrom an Or node and the And nodes below it. Relations of type (2) consider the durations of tasks, and correspond to the relations between its starting and ending times. Relations of type (3) collect the relation between the information from an And node and the Or nodes below it. Relations of type (4) consider the relation between the selection of an Or node and all the And nodes above it. Relations of type (5) are due to the delay needed for a change of configuration in a machine between the executions of two successive tasks using the same machine with precedenceconstraintsamongthem. Relations of type (6) consider the relation between some tasks that use the same resource. Types (1), (2), (3) and (4) come from the relations between the nodes included in the original And/Or graph, while types (5) and (6) come from the use of (same or different) resources by the different tasks, and they are related to new links between tasks in the extended And/Or graph. Taking into account the variables of the proposed model, selection, resource, time and cost constraints are considered. A previous work (Del Valle et al., 2009) includes the first three kinds of constraints. Selection Constraints. Collect the relations between the boolean variables that represent if the tasks are selected for the solution and the subsystems appears in the repair process. A special case is for the complete system and for the faulty component, which always will be part of the solution. The constraints of type (1) include the selection of disconnection tasks T′and connection tasks Twith that of subsystems: s′(S)⇔XORT′ i∈succ(S)(s(T′ i)) and s(S)⇔ XORTi∈succ(S)(s(Ti)). Related to relations of type (3), the selection of the two Or nodes if the And node is selected: s(T′)⇒s′(S1)∧s′(S2)and s(T)⇒ s(S1)∧s(S2). The constraints of type (4) include the selection of tasks T′and Twith that of subsystems: s′(S)⇔XORT′ i∈pred(S)(s(T′ i)) and s(S)⇔ XORTi∈pred(S)(s(Ti)). Resource Constraints. Consider the relations between the machines used in the tasks, and those where the subsystems are obtained after them. Related to relations (1), the machine mwhere a subsystem is generated after a connection task is the machine used by this task: s(Ti)⇒m(S) = M(Ti). Related to relations of type (3), the machine m′where a subsystem is generated after a disconnection task is the machine used by this task: s(T′ i)⇒m′(S1) = m′(S2) = M(T′ i). Time Constraints. Time constraints collect the relations between the start and the end times of the tasks, and the time when the subsystems are obtained. Related to relations of type (1), these constraints establish the disconnection t′ OR and connection times tOR of Or nodes related to the start times of the disconA MULTIOBJECTIVE CONSTRAINT OPTIMIZATION MODEL FOR MULTIMODE REPAIR PLANS 357 nection tasks or the end times of the connection tasks: s(T′ i)⇒ti(T′ i)≥t′ OR(S) + ∆mov(S,m′(S),M(T′ i)) and s(Ti)⇒tf(Ti) = tOR(S). Related to relations of type (2), these constraints consider the end time of the tasks related to the start time and the durations of them: s(T′ i)⇒tf(T′ i) = ti(T′ i)+Dur(T′ i)and s(Ti)⇒ tf(Ti) = ti(Ti) + Dur(Ti). Related to relations (3), the next constraints include the equality constraint between the disconnection times of the Or nodes t′ OR and the end time of a disconnection task T′above them: s(T′ i)⇒tf(T′ i) = t′ OR(S1) = t′ OR(S2), and the precedence between the connection time of the Or nodes tOR and the start times of connection task T, and considering the possible delays due to the transportation of subsystems if the two successive tasks involving it use different machines: s(Ti)⇒ti(Ti)≥ tOR(S1)+∆mov(S1,m(S1),M(Ti)) and s(Ti)⇒ti(Ti)≥ tOR(S2) + ∆mov(S2,m(S2),M(Ti)). Related to relations of type (5), these constraints establish that for a task Ti, and its closest predecessor task Tjusing the same machine m, taking into account the possible change of configuration: (s(Ti)∧s(Tj)) ⇒ ti(Tj)≥tf(Ti) + ∆cht(m,Cf(Ti),Cf(Tj)). For each two tasks Tiand Tjrequiring the same machine m, with no precedence constraint among them, and which may belong to the same repair plan, the constraints of type (6) express the two possible orders of execution of the tasks: (s(Ti)∧s(Tj)) ⇒(ti(Ti)≥ tf(Tj) + ∆cht(m,Cf(Tj),Cf(Ti)) ∨ti(Tj)≥tf(Ti) + ∆cht(m,Cf(Ti),Cf(Tj))). For the Or leaf nodes t′ OR and tOR are equals, except for the faulty component due to the delay corresponding to the reparation. Cost Constraints. The cost of a plan can be established by the aggregated costs associated to the execution of the selected tasks. The total cost of selecting a task Tiinvolves: •the execution cost of the task, Cost(Ti) •the cost associated to the possible machine movement of one or two subsystems, costmov(Ti): first, in disconnection tasks T′ i, the possible movement of the subsystem related to the Or nodes above it, related to relation (1), costmov(T′ i) = Costmov(S,m′(S),M(T′ i)); secondly, in connection tasks Ti, the possible movement of the two subsystems related to Or nodes below it, related to relation (3), costmov(Ti) = Costmov(S1,m(S1),M(Ti)) + Costmov(S2,m(S2),M(Ti)). •the possible cost associated to a change of configuration on M(Ti),costcht(Ti). If M(Ti)has been used before by another task with a different configuration, it is necessary to change it. The cost of the change of configuration depends of the sequence oftasks for each machine, so there mustbe considered the precedent task executed on m(Ti). Taking into account this, costcht(Ti) = Costcht(M(Ti),Cf(PM(Ti)),Cf(Ti)), where PM(Ti)is the precedent task executed on m(Ti). Also, the total cost of a plan can be defined as ∑Tis(Ti)(Cost(Ti)+ costmov(Ti) + costcht(Ti)). 4 CONCLUSIONS AND FUTURE WORK This work proposes a CSP model for the planning and optimal sequencing of disconnection and connection multi-mode tasks when repairing faulty components, taking into account the minimization of time and cost. The proposedmodel can be solved using conventional methods for a generic CSP. As future work, it is intended to use differentstrategies to solve the problem, working with heuristicalgorithms basedon the resulting state of the constraint propagation process and on the objective functions to be optimized. ACKNOWLEDGEMENTS This work has been partially supported by the Spanish Ministerio de Educaci´on y Ciencia through a coordinated research project (Grant DIP2006-15476-C0201) and Feder (ERDF). REFERENCES Boddy, M., Cesta, A., and Smith, S. (2004). ICAPS-04 Ws. Integrating Planning into Scheduling. AAAI Press. Deb, K. (2008). Introduction to evolutionary multiobjective optimization. Lecture Notes in Computer Science 5252 LNCS, pages 59–96. Del Valle, C., M´arquez, A., and Barba, I. (2009). A csp model for simple non-reversible and parallel repair plans. Journal of Intelligent Manufacturing. To appear (DOI 10.1007/s10845-008-0162-9). Homem de Mello, L. and Sanderson, A. (1990). And/or graph representation of assembly plans. IEEE Transactions on Robotics and Automation, 6(2):188–189. Kolisch, R. and Drexl, A. (1999). Local for multi-mode resource-constrained project. IIE Transactions (Institute of Industrial Engineers), 29(11):987–999. Rossi, F., Van Beek, P., and Walsh, T. (2006). Handbook of Constraint Programming. Elsevier. Smith, D., Frank, J., and J´onsson, A. (2000). Bridging the gap between planning and scheduling. Knowledge Engineering Review, 15(1):47–83. ICINCO 2009 - 6th International Conference on Informatics in Control, Automation and Robotics 358