Elsevier

Applied Soft Computing

Volume 7, Issue 1, January 2007, Pages 229-245
Applied Soft Computing

Framework of agent-based intelligence system with two-stage decision-making process for distributed dynamic scheduling

https://doi.org/10.1016/j.asoc.2005.04.003Get rights and content

Abstract

The advent of multiagent systems, a branch of distributed artificial intelligence, introduced a new approach to problem solving through agents interacting in the problem solving process. In this paper, a collaborative framework of a distributed agent-based intelligence system is addressed to control and resolve dynamic scheduling problem of distributed projects for practical purposes. If any delay event occurs, the self-interested activity agent, the major agent for the problem solving of dynamic scheduling in the framework, can automatically cooperate with other agents in real time to solve the problem through a two-stage decision-making process: the fuzzy decision-making process and the compensatory negotiation process. The first stage determines which behavior strategy will be taken by agents while delay event occurs, and prepares to next negotiation process; then the compensatory negotiations among agents are opened related with determination of compensations for respective decisions and strategies, to solve dynamic scheduling problem in the second stage. A prototype system is also developed and simulated with a case to validate the problem solving of distributed dynamic scheduling in the framework.

Introduction

Scheduling problems are often found in various business and industrial application areas, for example, in the scheduling of meeting rooms, airline crew assignments, general production, work projects, etc. Although scheduling has played an important role in planning daily routines in many domains, in practice it is still a fairly abstruse matter to handle all types of scheduling problems efficiently. Scheduling is one of the crucial tasks guaranteeing the smooth execution of activities, that is defined as the temporal assignment of activities to resources where a number of goals and constraints have to be considered [20]. In general, it involves two kinds of actions: the creation of schedules of activities over a longer period, which is called predictive scheduling, and adaptations of existing scheduling due to actual events in a scheduling environment, this is called reactive scheduling [22]. Dynamic scheduling (also known as reactive scheduling), which can react to a dynamic environment and adjust as fast as possible, is growing rapidly in importance, and close attention has been paid to it by many researchers and specialists in recent decades [1], [5], [7], [12], [13], [26].

In a highly competitive and changeable environment, the schedule of a multi-contract project [23] can easily encounter various unforeseen circumstances at the project execution phase caused by the influence of various uncertainties. O’Brien indicates that discrepancies between the needed resources for activities and the resources available to subcontractors are a major cause of project changes [18]. Resource discrepancies will occur when the timing of activities is not well matched with the available resources. If subcontractors cannot handle the problem well in time, they may cause delays to the schedule, affecting the schedules and resource allocations of succeeding activities, and even causing the project as a whole to falter or fail.

Another cause of schedule upsets in a distributed project can occur when the traditionally centralized control mechanism of the general contractor ceases to be effective and efficient. In most multi-contract projects, regardless of contract types, 80–90% of tasks commonly are performed by subcontractors, but only 40% of subcontractors are regularly informed by the general contractor when their services will be needed in the project [9]. Although, the general contractor conventionally takes the major responsibility of coordinating all project participants, due to subcontractors’ characteristics of independence, specialization and distribution, many of them do not have contractual relationships with general contractor; accordingly, most subcontractors still have to monitor schedule progress and project difficulties on their own as much as possible [13], [23]. Also, various interface problems can occur at a project execution phase because of the general contractor's lack of specialized expertise, shortage of manpower, and slow responses [2], [9].

Therefore, if project participants were offered the assistance of distributed and real-time system approaches that could automatically coordinate activities and resources, while also encouraging intra-project cooperation based on individual benefits and preferences without the intervention of the general contractor during the project execution phase, then some potential difficulties, such as resource discrepancies, interface problems, inarticulate communications and delays could be predicted and resolved earlier by the subcontractors involved. Such assistance could be important for the success of a project. Several studies have addressed the situation that multiagent systems (MAS), a branch of distributed artificial intelligence, can be satisfactorily applied to such problems [3], [5], [23], [26].

In this paper, a collaborative framework of a distributed agent-based intelligence system with a two-stage decision-making process for dynamic scheduling is addressed. The systems are used to automatically control and resolve the difficulties for project participants in distributed projects, especially focusing on the dynamic scheduling problem solving. Studies of multiagent systems and issues related to this topic are described in Section 2, and the architecture of the agent-based intelligence system for distributed projects is introduced in Section 3. The framework of the two-stage decision-making process performed by the fuzzy decision-making process and the compensatory negotiation process applied to dynamic scheduling is analyzed in Sections 4 Analysis of the two-stage decision-making process for dynamic scheduling, 5 The second-stage decision-making process. The implementation of a prototype system with a case simulation is described in Section 6 to validate the framework, and some conclusions and suggestions for future studies are provided in the final section.

Section snippets

Multiagent systems

Applications of agent technology have been growing rapidly in many domains in recent years. The term “agent” usually refers to an item of hardware or software of the computer system that has the properties of autonomy, social ability, reactivity and pro-activeness. A stronger notion characterizing an agent is the use of mentalistic notions, such as knowledge, belief, intention, and obligation [25]. Multiagent systems represent a new paradigm in analyzing, designing, and solving problems which

Architecture of the agent-based intelligence system

The architecture of the agent-based intelligence system for distributed projects is depicted in Fig. 3. It is an information platform coordinated in real time. The system not only can provide a flexible environment, but also can help all project participants monitor and manage their activities through the assistance of agents. The architecture of the system consists of related logical and physical capability components as shown in the following:

  • Naming agent

    The naming agent provides supervisory

Operating strategies of activity agents for dynamic scheduling

In the project participant system, each activity agent behaves as if its project participant were performing the activity. The agent possesses the specialized ability of the participant to coordinate with related works in order to keep the activity going smoothly and successfully. It can also cooperate with others based on the individual benefits and preferences characteristic of the participant.

With regard to the problem solving of dynamic scheduling in the framework, if any delay events occur

Framework of the compensatory negotiation model

At the end of the first-stage decision-making process, if there is any PAA whose schedule will be affected by the delay action resulting from the decision made by IAA, then IAA will open negotiation with these PAAs to ensure compensatory agreements for the delay decision. Thus begins the second-stage decision-making process: the compensatory negotiation process. The framework of the compensatory negotiation model for dynamic scheduling is depicted in Fig. 7, which consists of various operating

Implementation and a case example

To validate the feasibility of the framework we have proposed, a prototype system has been developed. We chose Java and JADE [4], [11] for agent programming to implement the prototype, because of the properties of platform independence, a high degree of openness and flexibilities, integrated network ability, FIPA [8] standard compliance and easy extension. Also, we use the case of the distributed project whose contractual relationship and Gantt chart is represented in Fig. 1, Fig. 2,

Conclusion and future works

During a distributed project execution phase, unexpected uncertainties can force the project schedule to change. Resource discrepancies occurring in the execution period of every activity are the major cause of schedule changes. In addition, the traditionally centralized control mechanism of the project being hardly able to control these distributed disturbances, because of the general contractor's lack of specialized expertise, shortage of manpower, and slow response time. Several interface

References (30)

  • R.J. Abumaizar et al.

    Rescheduling job shops under random disruptions

    Int. J. Prod. Res.

    (1997)
  • A.-M. Al-Hammad

    Common interface problems among various construction parties

    J. Perform. Construct. Facil.

    (2000)
  • K. Burbeck et al.

    Scale-up and performance studies of three agent platforms

  • FIPA, The Foundation for Intelligent Physical Agents, 2005, available at...
  • J. Hinze et al.

    The contractor-subcontractor relationship: the subcontractor's view

    J. Construct. Eng. Manage.

    (1994)
  • Cited by (32)

    • An agent-based intelligent algorithm for uniform machine scheduling to minimize total completion time

      2014, Applied Soft Computing Journal
      Citation Excerpt :

      Results show that it is capable of generating good schedules in real time comparable with the optimization algorithms and the frequently used dispatching rules. Chen and Wang [28] proposed a collaborative framework of a distributed agent-based intelligence system to control and resolve dynamic scheduling problem of distributed projects. They developed a prototype system and simulated with a case to validate the problem solving of distributed dynamic scheduling in the framework.

    • Multi-agent based approach for single machine scheduling with sequence-dependent setup times and machine maintenance

      2014, Applied Soft Computing Journal
      Citation Excerpt :

      Fuzzy decision-making and the compensatory negotiation processes are used by the agent types. The methodology of Chen and Wang [1] and of this present paper can maintain a high degree of openness and flexibility due to their programming structure. Both studies use Java programming language and its standards as agent programming language.

    • Applications of agent-based models for optimization problems: A literature review

      2012, Expert Systems with Applications
      Citation Excerpt :

      The paper proposes an agent-based algorithm to support distributed scheduling across the supply chain thanks to a modified Contract-Net Protocol. Similarly, Chen and Wang (2007a) and Chen and Wang (2007b) propose a model focusing on solving the dynamic scheduling problem of a distributed project for non-cooperative and self-interested participants. In this model, the self-interested activity agents possess various negotiation tactics and strategies.

    • A knowledge-based architecture for distributed fault analysis in power networks

      2010, Engineering Applications of Artificial Intelligence
    View all citing articles on Scopus
    1

    Tel.: +886 3 4638800x2515; fax: +886 3 4638907.

    View full text