Integrating planning and scheduling in workflow domains Integrating planning and scheduling in workflow domains Marı́a Dolores R-Moreno a,*, Daniel Borrajo b, Amedeo Cesta c, Angelo Oddi c a Departamento de Automática, Universidad de Alcalá, Carretera Madrid-Barcelona, Km. 33,600, 28871 Alcalá de Henares, Madrid, Spain b Departamento de Informática, Universidad Carlos III de Madrid, Avda. de la Universidad, 30, 28911 Leganés, Madrid, Spain c ISTC-CNR-Italian National Research Council, Viale Marx 15, I-00137 Rome, Italy Abstract One of the main obstacles in applying AI planning techniques to real problems is the difficulty to model the domains. Usually, this requires that people that have developed the planning system carry out the modeling phase since the representation depends very much on a deep knowledge of the internal working of the planning tools. On some domains such as business process reengineering (BPR), there has already been work on the definition of languages that allow non-experts entering knowledge on processes into the tools. We propose here the use of one of such BPR languages to enter knowledge on the organisation processes to be used by planning tools. Then, planning tools can be used to semi-automatically generate business process models. As instances of this domain, we will use the workflow modeling tool SHAMASH, where we have exploded its object oriented structure to introduce the knowledge through its user-friendly interface and, using a translator transform it into predicate logic terms. After this con- version, real models can be automatically generated using a planner that integrates planning and scheduling, IPSS. We present results in a real workflow domain, the telephone installation (TI) domain. � 2006 Elsevier Ltd. All rights reserved. Keywords: Planning and scheduling; Workflow management systems; Business process reengineering; Makespan minimisation; Time windows 1. Introduction In the last years, companies and markets have quickly grown in complexity so they are looking for flexible and dynamic ways to efficient manage their resources and processes. Due to the competitive nature of businesses and the strong pressure of the market, quality initiatives and the gradual improvement of processes are not enough for the continuous and dynamic changes that current organisations need. Levels of changes so radical need new and powerful tools that can allow the efficient redesign and management of the organisation. Also improving cus- tomer service and increasing customer retention is gaining importance. This is the main objective of BPR (Hammer & Champy, 1993). Over the past few decades, BPR has become fashionable among medium and big enterprises due to its capability to present solutions that improve this type of management. Although there have already been many approaches to the computer-aided design of processes, very few have focused on the automatic generation of process models that have in mind the organisation resources as well as their capabilities and availability. Once the organisation has been studied in depth from a process and resources perspective, corresponding models are modeled in order to handle processes and resources computationally. Business processes are usually repre- sented as workflow, that is, computerised models within which all the parameters needed for the completion of the processes can be defined: resources involved, orders, tasks, conditions, goals, quality criteria, information flow, etc. Workflow management systems (WFMSs) (Leymann & Roller, 1994; Medina-Mora, Winograd, & Flores, 1993; Mohan, 1997) have been deployed in sectors like insurance, banking, accounting, manufacturing, telecommunications, 0957-4174/$ - see front matter � 2006 Elsevier Ltd. All rights reserved. doi:10.1016/j.eswa.2006.05.027 * Corresponding author. Tel.: +34 918856607. E-mail addresses: mdolores@aut.uah.es (M.D. R-Moreno), dborrajo@ ia.uc3m.es (D. Borrajo), a.cesta@istc.cnr.it (A. Cesta), a.oddi@istc.cnr.it (A. Oddi). www.elsevier.com/locate/eswa Expert Systems with Applications 33 (2007) 389–406 Expert Systems with Applications mailto:mdolores@aut.uah.es mailto:dborrajo@ ia.uc3m.es mailto:dborrajo@ ia.uc3m.es mailto:a.cesta@istc.cnr.it mailto:a.oddi@istc.cnr.it administration and customer service (Lydiard, Jarvis, & Drabble, 1999) but it does not have significant commercial impact yet, because of problems related to the cost of pro- cess modeling and the inflexibility in their execution. We can see WFMSs as a set of methods and technolo- gies that allows modeling and managing some of the pro- cesses that happen in the company (there are some processes that will likely never be modeled in workflow sys- tems because, they are either too difficult to formalize, or too dynamic). It can provide active support to a business process by controlling the routing of work around the organisation automatically. This is done based on the busi- ness processes models describing the flow, the decisions, the exceptions, the resources to be used, etc. WFMS co-ordinates user and system participants, together with the appropriate data resources, which may be accessible directly by the system or off-line to achieve defined goals by setting deadlines. The co-ordination involves passing tasks to participants’ agents, and ensuring that all complete their tasks successfully. In case of excep- tions, actions to solve the problem can be triggered, or human operators alerted. Optimising the organisation procedures, routines and resource management, several aspects must be considered. Examples are the activities or tasks that should be per- formed; the organisation model that describes the roles of each agent (software or human), who can perform what in the organisation; and the information model that describes which information is needed to perform an activity. In the last few years an increasing development of doc- umentation tools and/or process modeling techniques have emerged that represent and reason computationally about the knowledge of the current processes and resources. Usu- ally, the task of defining those models is performed with the aid of a set of tools that provide a graphical represen- tation of them, together with the relations among the activities that occur within the processes. The human is usually an expert in the processes that take place in the organisation. Many issues need to be considered on this task and implemented like the reusability of past processes, accessibility to the models by the different agents in the organisation, consistency of usage, or selection of the right model. Prior to WFMS, many enterprises created special-purpose tailored applications to support their processes. The advan- tage of WFMS-based solutions is that the workflow repre- sentation is explicit, and separated from the application code. This means that a WFMS can be customised quickly to support a new business or process, and that workflows are relatively easy to modify when a process changes. Cur- rent WFMS do not address all aspects of the problem, however. In general, they do not deal with scheduling, that is, resources management/allocation. Similarly, while they provide means of generating exception events when things go wrong, they do not have a built-in re-planning function or automatic methods for adapting the workflow model according to those exceptions. They do, however, provide interfaces so that application-specific modules performing these functions can be integrated. Workflow systems hold the promise of facilitating the everyday operation of many enterprises and work environ- ments. Despite the popularity of these products, there is still a lack of maturity in some respect, i.e., a lack of a semantic associated to the models or an easy way to reason about that semantic, that could be overcome using tech- niques coming from other fields such as artificial intelli- gence (AI). Without any doubt, the application of AI techniques to Workflow Management systems has created a big expecta- tion. The AI community and in particular the planning and scheduling field, has been applying successful techniques in different and complex domains like robotics, satellites or military logistics. In these domains, there are activities that must be performed (planning) in a temporal horizon that consume or produce resources (scheduling). During execu- tion, completion of activities, and delays and other prob- lems are detected to take the appropriate measures (rectify the situation, or in more drastic cases, a new plan) to satisfy the goals. In order to represent this information, rich representation models are needed, the majority of them based on predicate logic as is the case of the planning standard language, PDDL2.2 (Edelkamp & Hoffmann, 2004). There is also the HTN representation where planning problems and operators are organised into a set of tasks. High level tasks are reduced into a set of lower levels and the way to do it can be done in several ways as in Yang (1997) and Kuter et al. (2005). In the past, some researchers saw the advantages of the integration of AI planning and scheduling for workflow generation, as shown by the existence of a Technical Co- ordination Unit of the European research network on plan- ning and scheduling, PLANET (PLANET), on applications of planning and scheduling to workflow. This has lead to some exploratory work reflected in a Roadmap PLANET and some related work (Hannebaeur, 1999; Kearney & Borrajo, 2000; Myers & Berry, 1999; R-Moreno & Kear- ney, 2002). The aim that we want to achieve with this integration is double. From one hand, given that the majority of BP tools are based on objects and rules, we propose to trans- late this knowledge into first order predicate logic, in par- ticular into the planning domain definition language PDDL2.2. On the other hand, we propose an integrated P&S fram- kework to automatically solve BRP problems. In the liter- ature there are basically two approaches to solve this type of problems. The component based approach (Cesta, Pecora, & Rasconi, 2004), where the two subproblems of planning and scheduling are just solved one after the other, and the integrated approach (Ghallab & Laruelle, 1994; Tate, Drabble, & Kirby, 1994) where there is an uniform representation without the decomposition over two sequen- tial subproblems. We believe that systems that integrate 390 M.D. R-Moreno et al. / Expert Systems with Applications 33 (2007) 389–406 https://isiarticles.com/article/489