A Market-Based Approach to Workflow Automation

Patrick T. Harker and Lyle H. Ungar

Departments of Systems Engineering and Computer and Information Science
University of Pennsylvania
Philadelphia, PA 19104

harker@eniac.seas.upenn.edu, ungar@cis.upenn.edu

Abstract

We propose a market-based approach to workflow problems in which human and computer agents bid for tasks and resources in an open market or auction, and demonstrate its applicability to a small business loan application process. Workflow problems generally require the coordination of many workers, machines and computers. Markets provide a natural mechanism for scheduling tasks and allocating resources. Markets serve many functions: bidding provides asynchronous communication between different agents, allowing them to communicate their capabilities, utilities, and availabilities while hiding irrelevent details of the individual work processes. Auctions optimize the allocation of tasks and resources and determine transfer prices. By properly structuring the auction, incentive compatibility can be assured, so that agents are rewarded for being productive and for giving truthful and accurate assessments of their utilities. The decentralized structure of a market also facilitates longer term learning by individual agents. Optimization theory and operations research provide some insight into the limitations of distributed systems such as markets and suggest cases where the decentralized market must be supplemented by a central controller which uses market intervention to assure stability and global optimality.

Market-based systems - introduction

Increasingly, work is a collaborative effort between multiple people and computers. In such complex undertakings, there are typically many data repositories and many decision makers, each of whom must communicate and coordinate decisions with a variety of human and computer agents. We are developing an agent and market-based approach for the control of complex service delivery systems such as those arising in workflow, purchasing, and transportation. Such systems are characterized both by the need for human/machine communication and by the complexity of the processes and their divergence; i.e., the ability of the service provider(s) to create alternative paths through the process by their actions. In addition, the criteria of performance of these systems are often multi-dimensional, incorporating measures such as service time, adherence to promised due dates, costs, and service quality. The goal of this research is to extend agent and market-based control schemes to create a theory for the design and implementation of adaptive intelligent workflow systems for the control of such processes. In these schemes, control is decentralized to various human and computer (e.g., databases, schedulers, models) agents that bid for the opportunity to work on various service delivery tasks.

There has been substantial work in academia in recent years on intelligent agents (Maes 1993), and in industry on workflow systems. The agent-based technologies offer a good start toward a formal basis for distributed problem solving (Davis and Smith 1983), and the workflow systems offer good support for unstructured human-human communication, but both approaches have largely neglected control, scheduling, and optimization.

Over the years, several people have proposed using the metaphor of the free market as a basis for building systems which coordinate or schedule tasks (Malone 1994, Wellman 1995, Baker 1995, Huberman and Hogg 1995). These works provide inspiration and a foundation on which we build our market-based workflow system.

Baker's Market-Driven Contract Net, a market-based system for scheduling manufacturing facilities (Baker 1995), exemplifies the state-of-the-art in market-based systems. Agents responsible for each machine tool or manufacturing unit offer bids on jobs, and subcontract out other jobs (e.g. for raw materials) to other agents. Production reservation scheduling is used, so that time is scheduled in advance on different machines, allowing efficient manufacturing of products involving processing on multiple machines. Each machine locally optimizes its costs when it determines what bids to accept on subcontracted work and what schedule to pursue. Baker's Contract Net was tested on a simulation of a GE plant which manufactures tens of thousands of different hardware products for the power industry, and showed significant reduction in costs from both work-in-progress inventory and time-in-progress. In order to extend this strong performance to the actual plant - or to the banking industry examples we will address - extensions are needed to: explicitly model uncertainty, improve models with experience, detect instabilities and reduce them through central intervention, and reschedule after unexpected disruptions.

However, Baker's system is not really a market because the agents do not attempt to maximize their own revenue, and hence do not compete. If all the agents were competitive, a problem with so few buyers and sellers at each level would be in the realm of game theory, as there is negligible competition. We are constructing market-based systems that share the structure of Baker's system, but are true markets, and are designed to be incentive compatible (Leonard 1983, Pratt and Zeckhauser 1985, van Ackere 1993).

Market-based workflow scheduling as optimization

In theory, coordination, and hence scheduling, can be viewed as a mixed integer nonlinear programming problem. In practice, the constraints and even the objective functions of the different participants are rarely explicit. Constraints are often contradictory, and even if they were known and consistent, optimal solutions are intractable. Communication is asynchronous (messages are left by voice mail, electronic mail, fax and letter) and multiple interactions are required which involve communication with human decision makers and with computers (e.g., databases with information about resource availability). Worse, each agent (either human or computer) must divide its resources between many tasks; aircraft may be carrying people and cargo other than those for the immediate task at hand, etc.

A number of technologies have been developed to help with such problems. We focus here on using intelligent agents and market-driven systems together with conventional scheduling algorithms and data bases.

Our market-based control system, briefly described, is organized as follows: Work is allocated among different agents (either computer or human), which subcontract out tasks to other agents based on their bids. In the bidding process, an agent requests bids for a set of tasks which it wishes to have completed. The request for bid (RFB) includes a time by which all bids must be received, and a time at which the bids will be awarded. If they assess their chances of making money as worth the effort, agents respond to RFBs with bids. Bids contain a description of the tasks to be performed and a function relating price to be paid as a function of both the time the raw material for the tasks is supplied and the time that all tasks are completed. Many simplified versions of this function can be used, e.g., the information needed to begin the task may be available at bid time, and payment before a due date may not be a function of time.

The goal of the scheduling is to assign tasks to agents in a fashion which minimizes the total price paid by the originating agents. In the context of the market-based economy, this can be viewed as a two level optimization. At the higher, master, level, the price offered to have jobs completed may be adjusted, as may the length of time that agents wait for bids or guarantee to fulfill bids that have been made. Agents may also be removed or re-deployed if they become bankrupt - they persist in failing to create value. At the lower level, each agent does a local optimization in determining its schedule in order to maximize its income.

Establishing internal transfer prices for work done has the added advantage that companies can use this information to help make the "make/buy" decision: oil refineries can often choose between making a given blend of oil or buying it on the spot market, and service industries can subcontract out work. Indeed, as computer coordination technology improves, companies are downsizing and subcontracting more work.

Research program

A market-based scheduling system is being developed and used to address a series of theoretical and practical questions concerning the structure and limitations of the proposed approach. Specifically, simplified adaptive work flow systems are being studied to address questions of stability, convergence and optimality. Key questions involve selecting the auction procedure and deciding what centralized operations are required to assure good performance. Analysis methods include optimization, control theory, and game theory (e.g., principal/agent theory).

Key system design issues include: Defining the language for communicating and resolving bids, selecting the internal representations used by the computer agents, selecting statistical process control models to ascertain when the process is out of control (e.g., oscillating) and thus, market intervention is necessary, and developing evolutionary optimization algorithms to adaptively improve the performance of the system.

Structured simulations are being used to test how well the theoretical results apply to more realistic systems. In particular, an adaptive workflow control system has been developed in C++ and Lotus Notes and its performance is being tested on a model of a small business loan application process.

Application to small business loan processing

A natural setting for studying market-based approaches to workflow automation is in financial services. Financial services are the largest single consumer of information technology in the economy, investing $38.7 billion dollars in 1991 (National Research Council 1994; p. 2). Banks are actively seeking the type of technology and operations management knowledge outlined herein since a major success factor as stated by retail banking leaders includes flexibility and responsiveness in operations (Roth and van der Velde 1991) . In particular, significant opportunities exist in the automation of the traditional "front-office" functions that are highly knowledge-intensive (Roach 1993; p. 10). Given this need, workflow systems have begun to make a substantial impact in financial services (Denning and Medina-Mora 1994; Schael and Zeller 1993).

As an example of the need for a market-based or adaptive workflow system, consider the Small Business segment of the retail banking industry. In our recent survey of the retail banking industry (Frei, Harker and Hunter, 1994) , the vast majority of the banks see Small Business as a major strategic focus for their business. In addition to providing loans and other lines of credit to the small businesses, banks also provide a variety of fee-generating services such as lock-box processing and cash management. However, the service delivery processes that are used to serve this market are poorly automated at present: only 10-12% of the banks can take a small business loan application on-line, and only 6% can correct errors in these accounts on-line. Clearly, technology will become a major factor in improving the efficacy and efficiency of the Small Business service processes in the near future.

What will this technology look like? Small Business operations, like most complex service systems, is a mix of overlapping processes such as sales support, lock-box processing, statement processing, cash management, etc. Many if not all of these processes are shared by other business segments in the bank: consumer, mid-market corporate, private banking, etc. Not only are production processes shared by a multitude of service products, but individual agents in the process, such as the customer service representatives in the branch office, must also “time share” between different product-oriented production processes. However, the manager of the Small Business market segment still needs to control the production of services for his or her customers. This paper addresses the question: How?

Consider the flowchart for the opening a small business loan process at one of the banks in our sample of banking operations. In this case, the customer returns the application to a platform employee in the Branch office (Agent 1), and then another employee in the branch performs a preliminary credit analysis of this loan application (Agent 2). Of course, Agents 1 and 2 are also performing such work for other products sold at the branch; in this sense, they are “time sharing” for the process of handling this single customer’s request. Once the above two steps are performed, the branch sends the application to a centralized lending office to make a final decision (Agent 3); again, this office is handling multiple products. The decision and the paperwork are communicated to the branch, which then schedules the closing. Once the branch employee (who could be different from Agent 1 and 2) receives the signed documents and processes the disbursement (Agent 5), the regulatory filings are performed and the branch books the loan (Agent 6). All together, six different human agents must interact with each other and information systems (computer agents) to process this single task.

What would a workflow depiction of the above process entail? The Action Technologies' workflow diagram for this process illustrates the myriad of decisions involved in processing a simple loan. However, what happens when a high priority "hot prospect" comes in who is buying multiple Small Business products from the bank and thus needs expedited service? The typical approach is to simply shout at those agents that are not performing the tasks on-time. However, this approach simply becomes unmanageable as the volume and complexity of operation increases; this increase is very real in banking as mergers form larger and larger organizations. Some type of control mechanism is needed to coordinate the processing of these loan requests, recognizing that the agents involved in the process are also involved in other service delivery processes within the organization. Precisely this type of control scheme is the focus of our research.

Conclusions

Workflow systems for processes such as credit approval and manufacturing job shops need to combine flexibility with scheduling and optimization. Markets offer an efficient mechanism for such workflow scheduling. They are naturally decentralized, distributed and flexible, and they support the inclusion of humans in the scheduling process by allowing asynchronous communication, encouraging specification of utilities, and being incentive compatible. We have taking the first steps toward establishing a market-based workflow system, and are testing in on a small business loan approval process.

References

A.D. Baker (1995) "Metaphor or reality: A case study where agents bid with actual costs to schedule a factory", to appear in Market-Based Control: A Paradigm for Distributed Resources Allocation, S.H. Clearwater, Ed. (Addison-Wesley, Reading, MA).

D.P. Bogia, W.J. Tolone, S.M. Kaplan, and E. de la Tribouille (1993), "Supporting dynamic interdependencies among collaborative activities," Proceedings of the 7th Conference on Organizational Computing Systems 1993 (Milpitas, CA), 108-118.

R. Davis and R.G. Smith (1983) "Negotiation as a metaphor for distributed problem solving" Artificial Intelligence 20(1) 63-109

P.J. Denning and R. Medina-Mora (1994), "Completing the loops," Interfaces 25, 42-57.

T. Finin and G. Wiederhold (1991) "An overview of KQML: A knowledge query and manipulation language. Stanford University Dept. of Computer Science Tech. Report.

B.T. Frankema, S.M.M. Joosten and R.R. Bakker (1995), "Usability of intelligent agents in workflow support systems," Working paper, Department of Computer Science, University of Twente (Twente, The Netherlands).

F. Frei, P.T. Harker and L.W. Hunter (1994), "Performance in consumer financial services: framework and results from the pilot study," Report to the Financial Institutions Center The Wharton School, University of Pennsylvania (Philadelphia, PA).

S.J. Grossman and O.D. Hart (1983), "An analysis of the principal-agent problem," Econometrica 51, 7-45.

B.A. Huberman and T. Hogg (1995), "Distributed computation as an economic system," Journal of Economic Perspectives 9, 141-152.

M. Jensen and W. Meckling (1976), "Theory of the firm: managerial behavior, agency costs and ownership structure," Journal of Financial Economics 3, 305-360.

H.B. Leonard (1983), "Elicitation of honest preferences for the assignment of individuals to positions," Journal of Political Economy 91, 461-479.

P. Maes (ed.) (1993), Designing Autonomous Agents (MIT Press, Cambridge, MA).

T.W. Malone (1987), "Computer support for organizations: toward an organizational science," in J.M. Carroll (ed.), Interfacing Thought: Cognitive Aspects of Human- Computer Interaction (MIT Press, Cambridge, MA).

T.W. Malone, R.E. Fikes, K.R. Grant, and M.T. Howard (1988), "Enterprise: a market- like task scheduler for distributed computing environments," in B.A. Huberman (ed.), The Ecology of Computation (North Holland, Amsterdam), 177-205.

T.W. Malone and K. Crowston (1994), "The interdisciplinary study of coordination," ACM Computing Surveys 26, 87-119.

M.S. Miller and K.E. Drexler (1988), "Markets and computation: agoric open systems," in B.A. Huberman (ed.), The Ecology of Computation (Amsterdam: North-Holland), 133-205.

National Research Council (1994), Information Technology in the Service Society (National Academy Press, Washington, DC).

J.W. Pratt and R.J. Zeckhauser (1985), "Principals and agents: an overview," in J.W. Pratt and R.J. Zeckhauser (eds.), Principals and Agents: The Structure of Business (Boston: Harvard Business School Press), 1-35.

S.S. Roach (1993), Making Technology Work , Special Economic Study (Morgan Stanley, New York).

A.V. Roth and M. van der Velde (1991), "Customer-perceived quality drives retail banking in ‘90s," Bank Management (November), 29-35.

T. Schael and B. Zeller (1993), "Workflow management systems for financial services," Proceedings of the 7th Conference on Organizational Computing Systems (Milpitas, CA), 258-268.

A. van Ackere (1993), "The principal/agent paradigm: its relevance to various functional fields," European Journal of Operational Research 70, 83-103.

W. Vickrey (1961), "Counterspeculation, auctions, and competitive sealed tenders," Journal of Finance 16, 8-37.

M.P. Wellman (1993), A market-oriented programming environment and its application to distributed multicommodity flow problems. Journal of Artificial Intelligence Research, 1:1-23.

M.P. Wellman (1995), A computational market model for distributed configuration design. Proceedings of the National Conference on Artificial Intelligence, pages 401-407, AAAI, August 1994. Revised version in AI EDAM, 9:125-133.

M.P. Wellman (1995), Market-oriented programming: Some early lessons. In S. H. Clearwater (ed.), Market-Based Control: A Paradigm for Distributed Resource Allocation. World Scientific.