Get In The Game: Enhanced Scheduling System Increases Business Profitability

FAYETTEVILLE, Ark. - Accurate scheduling of people, products and equipment can mean the difference between profit and loss for a business. Most scheduling approaches assume that there is a single decision maker that has complete information about the activity, but this is rarely the case. University of Arkansas researcher Erhan Kutanoglu has developed an approach using incentive-compatible scheduling and game theory to ensure selection of the most profitable schedule.

Whether people are using big machinery on a construction site, working with materials on a production line or the determining a courier’s delivery route, schedules are of critical interest in all businesses. Consequently, researchers devote lot of attention to developing scheduling systems that produce the best possible schedule.

Advanced planning and scheduling (APS) has become an important part of management strategies for companies that want to be highly competitive. Many companies are adopting supply chain management (SCM) solutions that come with high-quality APS components.

"Most current scheduling approaches, either stand-alone or as a part of an SCM solution, assume that there is a single decision maker and perfect information is available about all facets of the planning/scheduling activity," Kutanoglu noted. "However, in reality, multiple decision makers, or agents, play a role in different parts of the decision making process and the information comes from various sources or databases."

Many approaches inherently assume that these agents cooperate truthfully and work together for the common good. But that is not usually the case. To overcome these obstacles, Kutanoglu developed an approach using incentive-compatible scheduling to ensure the selection of the most profitable schedule even in today’s distributed or decentralized decision making environment.

"Most of these systems make the assumption that agents have the good will to cooperate and coordinate their decisions, and that they provide all private information truthfully," explained Kutanoglu, assistant professor of industrial engineering. "Worse yet, they assume that these agents will work to support the common goal at the expense of their private goals. If you substitute the word 'people’ for 'agents’ the problem with these assumptions becomes obvious."

Kutanoglu’s system incorporates incentive compatibility, which provides a reward/penalty mechanism to motivate decision agents to align their individual interests with the system-wide objectives. This produces the best results, regardless of individual preferences, manipulations or misrepresentations.

Although this works in a directed system with one decision maker, it is better suited for decentralized decision making. Kutanoglu’s system provides a method for achieving the best result in group or team situations, which occur in many manufacturing and service organizations or in public projects.

Because his system is based on game theory, Kutanoglu models it by using a schedule selection game. In this exercise, a finite number of agents are presented with a number of alternative schedules. Each schedule allocates a particular amount of resource, for example a block of time on a machine, for each task. Each agent represents only one job and the impact of a given schedule on that job is only known to that agent.

The game assumes that each agent only cares about the money and profit (the incentives in this game) and costs (penalties) received from the schedule. When the proper incentives are used, the agents will always reveal their true preference and the collection of all agent’s decisions will correspond to the best possible solution for everyone.

"We assume that a job agent’s preferences are known only by the agent himself,’ said Kutanoglu. "In a manufacturing context, the preferences may be motivated by delivery requirements or contractual agreements specific to the job, the performance evaluation a product manager is subject to, or any other constraints considered a 'local’ goal."

A key in Kutanoglu’s scheduling system is the direct revelation mechanism. In this two-step process, each agent is asked to reveal his true profit from the schedules and then an algorithm chooses the best schedule to maximize profit. Obviously, this assumes that all agents report truthfully. Because of individual preferences and the presence of private information, it may not be in the agent’s best interest to tell the truth.

"Without a proper incentive scheme that induces 'truth telling’ behavior, an agent may lie about his profits, with the intent to maximize his local position," Kutanoglu said. "With a direct revelation mechanism with proper incentives, every job agent has an incentive to report the true valuation of the schedules no matter what the other agents report, since doing so maximizes his own profit. The trick is to provide them the right penalty or reward (money) that affects the net profit of the agents."

Kutanoglu tested his system in an assembly plant that made electronics components for automotive manufacturers world wide. He identified the main bottleneck resource, a surface mount device (SMD), for his study. The SMD was shared among many different products, each of which was under the responsibility of a product manager.

"We can think of these product managers as job agents in the schedule selection game," said Kutanoglu. "Each agent in this case represented an order with a determined number of parts from a specific product type. The agent’s primary responsibility was to meet his job’s due date.

All candidate schedules were posted on a bulletin board for agents’ evaluations.

Each job agent provided a valuation for each schedule, representing the profit he would achieve if that schedule were used. Because the incentive mechanism was specifically designed to produce the truth, agents reported their valuations on the basis of due date achieved under each schedule.

If an agent’s choice had no impact on other agents, he didn’t pay a penalty or receive payments. However, if the agent’s choice negatively impacted the rest of the agents, he had to pay the difference that his evaluation caused.

"The beauty of this mechanism is that even after the payment, which reduces their net profit, the agents are still better off as compared to what they would get with a schedule chosen by the other agents without his valuation," said Kutanoglu. "In this way, it will be in the agent’s best interest to participate in the selection process, reveal the true values and pay the difference."

The valuations were processed and the schedule with the maximum total reported utility was selected. With the selected schedule, the company received the maximum benefit and used its resources in the best way possible and each agent individually also had a positive benefit.

Kutanoglu notes that, although the electronics assembly schedule included only 33 job agents and 8 possible schedules, the system can easily accommodate far more complex scheduling problems. This application demonstrated that including incentive compatiblity in a scheduling system can produce the best schedule. It also means that having decentralized authority or dispersed information among multiple agents does not have to mean a sacrifice in the overall system performance.

The decentralized nature of the decision making process in planing and scheduling is more visible with the increasing use of web-based collaborative planning and scheduling that sometimes spans more than one plant or company. With the advancement of the Internet-based technologies that support collaboration within a company or across multiple companies, the multi-agent planning and scheduling will be more crucial, not only for a single company, but also for the whole supply chain.

Kutanoglu, an assistant professor of industrial engineering, will present his findings today at the annual meeting of the Industrial Engineering Research Council in Cleveland.