The modern vision of the resource scheduling problem assumes that there is an organization with a number of static or Global Positioning System (GPS)-based mobile resources that receives orders in real time, as well as a flow of other unpredictable events: order cancelations, resources unavailable, failures, delays, etc.

The plan for resource usage has to be dynamically formed and continuously and adaptively revised, taking into consideration individual sets of criteria, characteristics, preferences, and constraints concerning orders and resources. The full cycle of resource management must include fast reaction to new events, the allocation of orders to resources, the scheduling of orders/resources, the optimization of orders (if time is available), communication with users, monitoring of plan execution, and rescheduling in case of a growing gap between the plan and reality.

The revision of the schedule must be made by the allocation of operations to open time slots or by solving conflicts between operations that can be shifted to previously allocated resources or reallocated/swapped to the new resources.

Communication with users means supporting a dialog with the users via mobile phones or other tools initiated by either side at any time.

12.2.2 Brief Overview of Existing Methods and Tools

The solving of classical problems on resource scheduling (also known as Non-deterministic Polynomial-time (NP)-hard complex problems) was originally formulated as a batch process where all orders and resources were given in advance and were not changed during runtime.

Traditionally, the enterprise resource planning (ERP) systems and schedulers offered by SAP, Oracle, Manugistic, i2, ILOG, and others implement batch versions of linear or dynamic programming, constraint programming, and other methods based on a combination of search options (Shirzadeh Chaleshtari and Shadrokh, 2012). In the case of one well-known scheduling system, it may take up to 8-12 h to allocate 300 trucks to 4500 orders. However, it may turn out that only 40% of this schedule is feasible in the real-world application.

To reduce the complexity of combinatorial searches, new methods consider heuristics and meta-heuristics (Vos, 2001), allowing the provision of acceptable decisions in a reasonable time and reducing search options. Some examples are “greedy” local search methods, simulated annealing, adaptive memory programming, tabu searches, and ant optimization.

However, these methods still use batch processing and struggle to take into consideration real-life criteria, preferences, and constraints.

The search for options remains very time consuming and results are often just not feasible or not comparable given the nature of human decisions.

12.2.3 The Multi-Agent Technology for Adaptive Scheduling

The fundamentals of multi-agent technology began to form in the last decades of the twentieth century at the edge of artificial intelligence, object-oriented and parallel programming, and telecommunications (Wooldridge, 2002).

In contrast with classical large, centralized, monolithic, and sequential programs, multi-agent systems (MAS) are built as distributed communities of small autonomous software objects working asynchronously but in a coordinated way to get the results.

The key features of MAS can be specified in the following way:

• Agents work autonomously, which means the agent cannot be called as a method, only asked to carry out tasks.

• Agents can react to events but can also trigger their activities internally and try to proactively achieve their objectives.

• Agents can communicate and coordinate decisions with other agents and can change their decisions adaptively.

At present, multi-agent technology is considered a new paradigm for solving complex problems that are difficult or even impossible to solve by classical mathematical methods or algorithms (Shoham and Leyton-Brown, 2009)—for example, in scheduling and optimization, pattern recognition, text understanding, and other domains.

Multi-agent technology was initially applied to solve classical optimization problems through the use of distributed problem-solving approaches—for example, the distributed constraint optimization problem (Rolf and Kuchcinski, 2011). Alternatively, a number of bio-inspired methods were developed—for example, swarm optimization, hybrid methods based on an artificial immune system, and particle swarm optimization for solving production planning problems and others (Gongfa, 2011; Xueni and Lau, 2010).

As a next step, a market-based approach to scheduling was developed where order agents and the resource agents participate in continuously running auctions based on contact-net protocols (Pinedo, 2008; Allan, 2010; Noller et al., 2013).

There are a growing number of first prototypes and industrial solutions based on multi-agent solutions (Pechoucek and Marík, 2008; Leitao and Vrba, 2011; Florea et al., 2013).

12.2.4 The Concept of Demand-Supply Networks

The developed approach is based on a “holon” concept of the PROSA system (Brussel et al., 1998) where specific classes of agents of “orders,” “products,” and “resources” were introduced, as well as a “staff” agent that monitors results and advises other agents when required.

To make this approach more flexible and efficient, the concept of demand-supply networks (DSN) was introduced, where agents of demands and supply compete and cooperate on the virtual market (VM). In this concept, any agent (holon) of physical or abstract entity can generate “small” demand-and-supply agents that follow the specific requirements—for example, a truck can demand a driver or fuel, a route, and maintenance. From the other side, the truck can be busy for the first half of a day only and is interested in finding and supplying a truck for orders for the second part of a day. As a result, the schedule can be formed as a kind of requirement-driven network of operations that can be easily adapted by events in real time (Skobelev and Vittikh, 2003, 2009).

Another example: An order for product assembling can generate demands for specific equipment and a worker as factory resources, but the same equipment can generate a new demand on regular maintenance or special repairmen. The role of demand agent here is to get the best possible time slot of equipment and worker in the factory schedule or a truck in cargo transportation, etc. The role of a supply agent is the opposite—to provide full utilization of the resources. Having received proposals from various supply agents, the demand agent can decide which proposal is most appropriate, and vice versa, because DSN agents have conflicting interests and operate in the VM according to their economic reasons. The decision-making rules for agents in the VM are determined by the microeconomic model of a DSN, which defines the virtual cost of services, the penalties and bonuses, rules for sharing the profits, what taxes should be paid under various conditions, etc. It gives agents an opportunity to accumulate virtual money and use it for getting the best possible options. In fact, the virtual money plays the role of energy, and agents use it to create new schedules or adapt fragments of the existing ones. This model can become more and more complex due to: (1) introducing new agents into a DSN that represent the interests of various physical or abstract entities; and (2) the increasing number and variety of classes of interaction protocols between agents.

Specific DSN-based methods and tools were developed to design adaptive MAS for real-time scheduling (Rzevski and Skobelev, 2014).

12.2.5 The Formal Problem Statement

The formalized problem statement is based on searching for a consensus between agents in a DSN VM and can be formulated as follows.

Let’s assume that all agents of demands and supply have their own goals, criteria, preferences, and constraints (for example, due date, cost, risk, priority, required equipment type, or worker qualification). The importance of each criterion can be represented by weight coefficients in a linear combination of criteria for the given situation in scheduling, but can change during the schedule forming or execution.

Let’s introduce the satisfaction function for each agent (Figure 12.1a), which will show deviations of the current value of this function from the given ideal value by any of the criteria for the current step of finding a scheduling solution for this agent. The activity of agents also depends on bonus/penalty functions and the current budget allocated on specific accounts for virtual money (Figure 12.1b).

Let each demand j have several individual criteria x_i and suggested ideal values x_ij^id. Each agent of demand j normalized bonus/penalty function is calculated by component i (virtual value), given for example as a linear function $f_{ij}^{\text{task}}\left(x_i-x_{ij}^{\text{id}}\right)$. In most of these cases, this function has a bell form with a maximum at the point of the suggested ideal value. As a summary value of the result for each demand, the sum of virtual values for each criterion i with the given weight coefficients α_ij^task is estimated.

By proper selection of the signs and form of the function, the goal of each agent can be reformulated as maximizing the virtual value y_j^task of demand j (upper index task means that the values belong to the demand agents):

$y_j^{task}={\displaystyle \sum _i{a}_{ij}^{task}}.f_{ij}^{task}(x_i-x_{ij}^{id})$

where ∀j weight coefficients are normalized: ${\displaystyle \sum _i{a}_{ij}^{task}}=1$.

Similarly, the problem of finding the states x_ij^* of agents of demands j, which maximize the total value of all orders, can be formulated:

$y^{\text{task}}={\displaystyle \sum }_j{b}_j^{\text{task}}{y}_j^{\text{task}}={\displaystyle \sum }_j{b}_j^{\text{task}}{\displaystyle \sum }_i{a}_{ij}^{\text{task}}{f}_{ij}^{\text{task}}\left(x_i-x_{ij}^{\text{id}}\right)$

$y^{{\text{task}}^{*}}=\underset{x_i}{max}\left(y^{\text{task}}\right)$

where β_j^task is the demand weight that allows us to set and dynamically change the priorities showing the importance of the criteria.

Similarly, the value function can be given for the supply using criteria z_k, with the bonus/penalty function $f_{kl}^{\text{res}}\left(z_k-z_{kl}^{\text{id}}\right)$, the weight α_kl^res of criterion k for resource l, and resource value β_l^res for the system (which is similar for the weight for the demand agents function):

$y^{\text{res}}={\displaystyle \sum }_l{b}_l^{\text{res}}\cdot y_l^{\text{res}}={\displaystyle \sum }_l{b}_l^{\text{res}}{\displaystyle \sum }_k{a}_{kl}^{\text{res}}\cdot f_{kl}^{\text{res}}\left(z_k-x_{kl}^{\text{id}}\right)$

$y^{{\text{res}}^{*}}=\underset{z_k}{max}\left(y^{\text{res}}\right)$

$z_k\in D^K,x_i\in D^I\forall i,k,I=\text{Dim}\left(D^I\right),K=\text{Dim}\left(D^K\right)$

Variables x and z belong to some areas of the space of criteria for demands and supply, I and K are dimensions of the corresponding criteria spaces, and upper index res means that the values belong to resource agents.

Thus, in Demand-Supply Network (DSN) the optimization problem is formulated as solving Equations (1)–(3).

In other words, in the suggested bottom-up methodology, one global optimizer is replaced by many small local optimizers that are able to negotiate and find trade-offs when they search their local optimums.

12.2.6 The Method of Adaptive Scheduling

The developed method is based on a DSN concept where agents of demands and supply operate in the VM and continuously try to improve their individual functions of satisfaction that reflect their given multi-criteria objectives.

The core part of the developed method can be identified as the following:

1. The number of classes of demand and supply agents represents the specifics of the problem domain with the required level of granularity.

2. Satisfaction functions and the function of bonuses/penalties are represented by a linear combination of the multi-criteria objectives, preferences, and constraints of each agent.

3. Protocols are defined that specify how to identify conflicts and find trade-offs with the open slots, shifts, and swaps of operations.

4. A schedule formed in the process of DSN agent self-organization is based on decision making and the interaction of agents.

5. Special event procession protocols are triggered when new events occur (for example, the arrival of a new demand):

a. An agent is allocated to a demand as it arrives in the system. The demand agent sends a message to all agents assigned to available resources stating that it requires a resource with particular features and it can pay for this resource with a certain amount of virtual money.

b. All agents representing resources with all or some specified features and with the cost smaller or equal to the specified amount of money, offer them to the demand agent.

c. The demand agent selects the most appropriate free resource from those on offer. If no suitable resource is free, the demand agent attempts to obtain a resource, which has already been linked to another demand, by offering to that demand some compensation.

d. The demand agent that has been offered some compensation considers the offer. It accepts the offer only if the compensation enables it to obtain a different satisfactory resource and at the same time increase the overall value of the system.

e. If the demand agent accepts the offer, it reorganizes the previously established relationship between that demand and the resource and searches for a new relationship, with the resource increasing the overall value of the system.

f. The same process is running with resource agents that are able to generate supply agents with specific context-based requirements.

6. The preceding process is repeated until all resources are linked to orders and there is no way for agents to improve their current state or until the time available is exhausted.

To achieve the best possible results, agents use the virtual money that regulates their behavior. The amount of virtual money can be increased by getting bonuses or it can be decreased by penalties, depending on their individual cost functions. The key rule of the designed VM is that any agent that is searching for a new and better position in the schedule must compensate losses to other agents that change their allocations to resources, and the propagation of such a wave of changes is limited by virtual money (Skobelev and Vittikh, 2009).

The use of the VM presumes that demands buy the services of the resources that, in their turn, have static or dynamic cost. The dynamic cost of the resource depends on how resources can be shared. For example, a truck has a certain cost, but it is distributed between its cargoes with some planned profitability given in advance. As stated before, the agents can offer each other compensations for shifts and reallocations, the sum of which is defined during negotiations between demand and supply agents. If the cost of functioning is not covered by the income, the resource can decide to switch off.

The main features of the suggested VM microeconomics are:

• Agents have ideal and current values of objective functions, which are used to compute the agents’ “satisfaction” with the current plan.

• Order agents enter the system having virtual money to achieve their objectives, including service level, costs, and delivery time.

• Resource agents look for their maximum utilization, but also have their own ideal preferences, constraints, and costs for sharing.

• Product agents are interested in minimizing the time spent in storage.

• There are dynamic values of weight coefficients of the scalarized objective function that are linked to a virtual money bonus or a penalty for orders, products, and resources, and each criteria has its own coefficient of conversion to virtual money.

• The current virtual budget is used by agents to improve their local allocation of demands and supply in the schedule.

• Agents iteratively improve their criteria to reach locally optimal values, compensating for the losses of other agents from their virtual budget, in such a way that virtual profit is growing.

Such an approach offers opportunities to introduce virtual taxes related to the agents’ job planning and execution, the cost of messaging between agents, and so on. These taxing mechanisms can be used to control the process of the self-organization of the schedule and provide a good quality schedule within a limited time.

If necessary, the user can interactively intervene with the plan at any time and manually rework the schedule by dragging and dropping the operations.

As a result, the plan will be automatically revised and rescheduled.

12.2.7 The Basic Multi-Agent Solution for Adaptive Scheduling

The basic solution includes a number of agents, which are applicable for various domains of real-time resource scheduling:

• The agent dispatcher, which supports the agent life cycle, the creation and termination of agents, and communication protocols.

• The agent for supporting messaging services.

• The main classes of PROSA agents and supporting agents of DSN.

• The event queue agent that is responsible for events processing.

• The scene agent for data loading and serving the resulting schedule.

The list of the designed basic classes of agents is shown in Table 12.1.

The presented list of agents (Table 12.1) can be adjusted during the development process for a specific domain of scheduling. As an example, the list of agents and protocols regarding their negotiations for a factory scheduler is given in Figure 12.2.

The “scene” is an object model of the forming schedule in which jobs/tasks are linked with time slots of resources. The scene is considered to be a “mirror” of the reality. In the new versions of adaptive schedulers, the scene is formed as an ontology-based semantic network of key domain objects and relations—for example, in factories linking orders and technological operations, equipment and workers, and skills and competencies. These links are continuously investigated by agents and help them narrow the search and find reasonable options by analyzing the “topology” of the schedule.

The solution can be easily integrated with the existing ERP systems—for example, order management, accounting, etc.

12.2.8 The Multi-Agent Platform for Adaptive Scheduling

The multi-agent platform is designed to automate the developed methodology and increase the quality and efficiency of the development process for creating real-time resource management systems for different problem domains.

The developed multi-agent platform combines the functionality of a basic adaptive scheduler that can be easily modified for new domains with a simulation environment that is useful for experiments with the different DSN models, methods, and algorithms.

Functionality of the multi-agent platform provides the possibility for end-users to specify an initial network of resources, form a sequence of events manually or automatically or load it from external files, make individual settings for all demands and resources, run simulations with different parameters, and visualize the process and results of the experiments.

An example of the user interface of the platform that represents the results of experiments with a given flow of orders is shown in Figure 12.3.

The screen presents a network of resources, Gantt charts with the resource schedule, the workload of orders and resources, the satisfaction of orders and resources, virtual money transfers, a log of decisions, and other items.

During the simulation mode, a number of useful charts and diagrams can be visualized or exported in Excel files for future investigations:

• A graph of network loading shows the utilization of all resources.

• A Gantt chart shows the allocation of demands to resources over time.

• The communication activity diagram shows how many messages are generated in the platform at any moment of time.

• The satisfaction of demand and resources chart demonstrates how the satisfaction level changes during the process of simulations.

• The orders execution chart shows the status of the orders’ execution.

• The resource utilization chart shows how busy resources are at different moments of time.

• The message log demonstrates the exchange of messages between selected agents.

• The decision making log presents the results of decision making for a selected agent.

• The financial transactions log shows the transfers of virtual money between the demand and supply agents.

The platform architecture includes the following components: initial scene editor, event generator, event queue for the main classes of events, a multi-agent world built as a VM, basic classes of agents and the supporting demand and supply agents, visual components for editing agents’ settings and the visualization of results, the export and import of data, the logging and tracking of messages, and agent financial transactions and other specific components.

These components can be adjusted for new problem domains and applications.