Sage Journals: Discover world-class research

Abstract

Aimed at enhancing the effectiveness and efficiency for offshore platform project scheduling, a multiagent collaborative scheduling model based on the analysis of distributed offshore platform project scheduling was proposed. The functional definitions and internal structure of agents in the proposed system were analyzed. Moreover, in order to explore the cooperative way of agents, communication mechanism was presented and a negotiation model was elaborated. Then, system architecture and hardware architecture were constructed to lay a foundation to develop the collaborative scheduling system. Finally, an intelligent algorithm based on Bayesian method was designed to verify the negotiation model and a prototype system was developed to test the feasibility and rationality.

1. Introduction

Offshore platform construction of Engineering to Order (ETO), which belongs to the complicated and multivariate system engineering project, is a typical cross-organizational collaborative process [1]. Besides, it generally has the characters of high technology, complex product structure, complicated process flow, high cost, long construction period, tight delivery date, and so forth. As the key link of offshore platform construction, offshore platform project scheduling often involves multienterprise collaboration, multidepartment interaction, and multiproject in parallel. The involved enterprises or departments can be seen as distributed decision makers that contain their own information, objectives, and strategies. And they together form a Virtual Enterprise (VE) network structure to collaboratively tackle the scheduling problem.

Traditional centralized scheduling methods often result in low efficiency and poor coordination situation; many researchers try to adopt and apply the multiagent system (MAS) theory to handle distributed scheduling problem [2 –5]. In MAS, agents are used to represent the logical or physical resources in scheduling process and they together abide by some kind of agreement to fulfill the scheduling objectives through mutual coordination [6]. These characteristics of MAS can precisely match the features of offshore platform project scheduling. Therefore, it is of great significance to study the collaborative scheduling model based on the MAS theory since it can not only provide a dynamic and quick responding scheduling mechanism but also improve scheduling efficiency and effectiveness for offshore platform project.

The remainder of this paper is organized as follows. Section 2 reviews relevant research related to project scheduling and MAS theory. In Section 3, collaborative scheduling characters and flow of offshore platform project are analyzed. Section 4 proposes an MAS-based framework and presents the functional definitions and internal structure of agents. Section 5 studies the communication and negotiation mechanism. Section 6 designs the system architecture. Then, in Section 7, an intelligent algorithm is designed to verify the critical resource allocation and a prototype system adopting the B/S structure is developed. Finally, Section 8 concludes with some advantages of our proposed system and points out some remaining work.

2. Literature Review

In this section, we try to summarize and analyze relevant literature from three research streams: project scheduling, MAS technology, and the application of MAS to scheduling problem.

2.1. Project Scheduling

Project scheduling problem is a typical NP-hard problem. Generally, the artificial intelligence solutions to solve scheduling problem include heuristic algorithms, intelligent optimization algorithm, and MAS-based method.

Based on deduction and calculation of available information, heuristic algorithm can help to get the approximate optimal solution. Among all the heuristic algorithms, Lagrangian relaxation algorithm (LRA) performs better on scheduling problem due to its high efficiency to get high-quality resolutions, as paper [7 –9] showed. Compared to heuristic algorithm, intelligent optimization algorithm has shown outstanding performance on the aspects of rapidity and validity to search optimal resolutions in scheduling problem. It has acquired tremendous achievements during these years. Kim et al. [10] proposed a kind of adaptive hybrid genetic algorithm (AHGA) combined with the fuzzy logic controller to solve the minimum makespan punishment problem. In [11], Jianxing and Cangyan utilized improved ant colony algorithm (IACA) based on information entropy to resolve dynamic resource allocation problem for offshore platform project. Fung et al. [12] considered the penalty for completion date and combined the genetic algorithm (GA) and matrix theory to study priority relationships among multiple projects. In [13], Z.-J. Lee and C.-Y. Lee adopted hybrid genetic algorithm (HGA) to tackle resource dynamic allocation problem for multiple projects. Li [14] designed a combined intelligent algorithm, genetic and ant colony algorithm (CGAA), to search a more efficient optimization method for multiproject resource leveling problem.

2.2. MAS Technology

MAS theory is a significant branch of Distributed Artificial Intelligence (DAI) and is mainly concerned with three aspects: system modeling, architecture, and coordination mechanism [15]. Some relevant literature reviews from these three aspects are as follows.

System modeling that maps problem object to MAS system lays a foundation for agent system development. There are mainly two methods: functional mapping and physical mapping. In [16], Yu et al. developed a virtual reality system for microscopic traffic behavior according to different functions of agents. Wong et al. [17] mapped the dynamic shop-floor scheduling to a multiagent system made up by manufacturing cell agent and machine agent. Erol et al. [18] also adopted the physical mapping method. MAS architecture primarily is concerned about organization modes and interactive ways so as to connect agents and analyze system structure. Papers [19, 20] adopted blackboard structure to construct the multiagent system and paper [21] utilized the distributed norm. Coordination mechanism focuses on the study of communication and negotiation method among agents. Through coordination mechanism, agents can exchange and share information. Smith and Davis first proposed the Contract Net Protocol (CNP) theory to solve distributed negotiation problem. Most of the following researches [22 –24] were based on this theory to design negotiation mechanism.

2.3. Applications of MAS Technology in Scheduling Problem

With the speedy development of MAS technology, many researchers have successfully applied MAS technology to deal with distributed scheduling problem in many engineering fields [25 –28]. Besides, considering the issue of multiagent adoption to deal with scheduling problem, current researches mainly aim to study negotiation strategies or tackle the multiobjective scheduling optimization problem to minimize production time and resource allocation.

On the one hand, some researchers design the negotiation strategies or mechanisms between agents aimed at solving some conflicts like critical resource conflict during scheduling process. Lau et al. [29] proposed a negotiation algorithm to handle distributed project scheduling problem (DPSP). Similarly, Siddiqui and O'Brien [30] aimed to solve DPSP and set up a repetitive scheduling system so as to correlate the global scheduling agent with the subproject scheduling agent. To tackle the coordination problem of distributed projects interests, Chen and Wang [31] developed a compensatory negotiation model for distributed dynamic scheduling directed against the mutual coordination of multiproject interests. In [32], Lin et al. generated a MAS-based negotiation mechanism in terms of price schedules decomposition, which allowed self-interested collaborators to make decisions according to their own benefits.

On the other hand, other researches tend to optimize the process scheduling time or machine productivity. Given that process planning and scheduling are performed sequentially, Li et al. [33] designed an agent-based approach to facilitate these two functions and connect them more tightly. In [34], Lee et al. regarded the scheduling problem on a single machine and therefore simplified the multiproject scheduling problem into a multiobjective shortest path (MOSP) problem to minimize the weighted completion time. Cheng [35] considered two-agent scheduling problem and discussed some polynomial cases to design the algorithm to optimize task tardiness. In [36], Asadzadeh and Zamanifar proposed an agent-based parallel approach combined with the genetic algorithm and aimed to enhance the efficiency of job shop scheduling. For the concurrent scheduling problem, Gutierrez-Garcia and Sim [37] innovatively elaborated a family of 14 scheduling heuristics for concurrent execution of bag-of-tasks applications (BoTs), and the results showed that it could optimize the makespan and allocate cloud resource reasonably. To solve the collaborative scheduling problem of container terminal logistics system (CTLS), a multiagent system was presented by Bin and Wenfeng [38] to stimulate the container scheduling process including loading, collection, stacking, and distribution, and, therefore, the scheduling efficiency was enhanced.

2.4. Discussions

Although these researches have gained amounts of approaches to solve scheduling problem, they cannot totally satisfy the requirements of offshore platform projects. Firstly, most of the researches mainly focused on the scheduling problem under single production environment. In this way, offshore platform project scheduling problem could hardly be resolved since it is a kind of collaborative scheduling problem under distributed environment rather than a mere optimization problem. Secondly, current studies lack the systematic analysis for offshore platform scheduling problem and very little have been done to put emphasis on the scheduling relationship and involved roles in offshore platform project. Thirdly, more emphasis is put on the algorithms design and strategies analyzed and, therefore, very few have been fulfilled to develop the scheduling system, which can directly guide the practical scheduling in engineering.

Bearing the above analysis in mind, for offshore project scheduling system, we adopt the functional and physical mixing mapping method for system modeling and distributed hybrid architecture to study the organizational structure. Moreover, the communication mechanism and negotiation mechanism based on CNP theory are presented. Last, the prototype system is elaborated to support the scheduling process of offshore platform project and through the practical application, data comparison and efficiency analysis is presented.

3. Process Analysis

3.1. Network Structure Based on VE

To begin with, we propose the concept of Virtual Enterprise for offshore platform project (OPPVE), as described in Figure 1. OPPVE can be considered as a temporary alliance of enterprises and it can realize the scheduling process by opportunities sharing and collaborative decision-making among members [39, 40]. In addition, OPPVE is formed by enterprise network, handled by task allocation and coordination, and operated by the multilateral agreement among members to standardize the criteria, rules, and communication process.

Figure 1:

VE network for offshore platform project collaborative scheduling.

As Figure 1 shows, marine enterprise decomposes the offshore platform project to productive tasks and subcontracted tasks by formulating project plans according to the owner's requirement. The productive ones are assigned to manufacturing plants in marine enterprise and the subcontracted tasks are jobbed out to subcontractors through signing bilateral contracts. Moreover, OPPVE can be regarded as a “delivery system,” which is supported by the information and communication technology (ICT), created by the reconfigurable core competence set, and guided by the owner's requirement. In brief, this paper's research is developed in terms of the collaboration and interaction of OPPVE.

3.2. Process Analysis for Collaborative Scheduling

As mentioned above, offshore platform project scheduling involves multienterprise interaction, multidepartment cooperation, and multiproject in parallel. For this point, we present the collaborative scheduling flow chart shown in Figure 2 and describe the collaborative scheduling features as follows.

Figure 2:

Collaborative scheduling flow chart of offshore platform project.

3.2.1. Project-Oriented Supply Chain

The project-oriented supply chain of offshore platform project can be considered as a “dynamic” chain. Each management link in the chain contains its own supply-demand relationship. Besides, it can provide agile and robust management system for offshore platform project scheduling. In this way, the involved enterprises and departments can quickly reorganize and read just to scheduling plans.

3.2.2. Cross-Enterprise/Department/Profession Collaborative Operation

Marine enterprise is responsible for project leading, planning, and some modules construction; suppliers provide required materials; subcontractors take charge of subcontracted tasks. Additionally, in the marine enterprise, different departments and professions collaborate with each other to complete the platform construction. Therefore, the scheduling process can be considered as a cross-enterprise/department/profession collaborative operation.

3.2.3. Hierarchical Scheduling Decision-Making Process

During the initial stage of platform construction, project decomposition structure is not fully integrated, so are the assigned tasks for involved enterprises and departments. Besides, the upper scheduling change usually leads to the alteration of task attributes, required materials, cost estimation, and so forth. Therefore, the scheduling process for offshore platform project should be a hierarchical planning and decision-making process.

3.2.4. Distributed Decision-Making Bodies

The involved enterprises and departments can be considered as distributed bodies geographically in different places, and each one has its own interest, knowledge, environment, and so forth. During the scheduling process, it is normal to see incomplete interaction, asymmetrical information, slow responding, and conflicting resource requirement among distributed bodies. Hence, taken all the reasons into consideration, marine enterprise should coordinate each organization and reasonably optimize resource allocation.

4. Architecture of the Proposed System

4.1. System Framework

In order to tackle the complexity of offshore platform project collaborative scheduling, we adopt MAS technology to construct the model. The first step is to utilize agents to stand for different functional or physical resource during the scheduling process. According to the above description, we establish the framework of offshore platform project collaborative scheduling as Figure 3 shows and propose the model of offshore platform multiagent collaborative scheduling system (OPMACSS) by using a multituple:

OPMACSS = (TPA, ECA, SA, CA, PA, RA) .

(1)

Figure 3:

Collaborative scheduling system framework based on MAS technology.

According to Figure 3, the workflow of agents in OPMACSS is depicted as follows. By analyzing task objectives, task planning agent (TPA) decomposes the project to task packages under related constraints. Some of the professional tasks like plates welding, electrical equipment installation, are jobbed out from extended coordination agent (ECA) to subcontract agents (SA) which belongs to subcontractor; other tasks are completed by the marine enterprise itself, like materials procurement and transportation. Having balanced the production agent's (PA) capacity and task load, coordination agent (CA) distributes the productive tasks to PAs. Then, resource agents (RA) allocate relevant resources to different PAs based on their orders’ requirement. When it happens to meet some critical resource conflicts, the CA, RA, and PAs tend to negotiate with each other to solve them. Additionally, the PA is responsible for monitoring tasks execution.

4.2. Functional Definitions of Agents

The framework of OPMACSS also reflects the functions of agents, and Table 1 specifically defines functions of each agent.

Table 1:

Functional definitions of each agent in OPMACSS.

Agent Type	Functional Definition

Task Planning Agent (TPA)	Analyze task objectives and attributes; decompose project into task packages; be responsible for task planning.
Extended Coordination Agent (ECA)	Formulate subcontract planning; select tendentious SA according to its knowledge library; review and negotiate with different SAs to come to contracts; transmit the bill of quantities of subcontracted tasks.
Subcontract Agent (SA)	Receive subcontract information from ECA; calculate its own benefits and bid; sign the contract agreement by bargaining with ECA.
Coordination Agent (CA)	Schedule productive tasks by calling related algorithms from the library and assign the scheduled tasks to PAs; be responsible for conflict resolution like the critical resource conflict.
Production Agent (PA)	Acquire tasks’ schedule and orders and execute them; negotiate with RA and CA when facing resource conflicts.
Resource Agent (RA)	Connect to production resources and allocate related resources to PAs; negotiate with PAs to resolve resource conflicts.

4.3. System Architecture

System architecture contains three parts: man-machine interaction, operation kernel, and operation environment. The OPMACSS system architecture is designed as in Figure 4.

Figure 4:

OPMACSS system architecture diagram.

4.3.1. Man-Machine Interaction

Man-machine interaction part contains two layers: interface layer and function layer. Through human-machine interfaces, OPMACSS can realize the interaction process with users and provide data, document, or graph. Besides, by the collaboration of each function, it can enable users to manipulate the OPMACSS to guide scheduling process.

4.3.2. Operation Kernel

Operation kernel consists of tool layer, collaborative layer, and model layer and helps to manage and control data flow. Tool layer and collaborative layer are the core part in the OPMACSS. For collaborative layer, it mainly includes two sub-MAS—subcontract scheduling and production scheduling. For tool layer, it contains different agents, which serves for the collaborative scheduling process. Last, model layer can simulate the collaborative scheduling modeling for offshore platform project.

4.3.3. Operation Environment

This part mainly introduces the internet environment and hardware environment. Protocol layer studies the language norms, message expression, database type, and so forth. Physical layer presents applied hardware in OPMACSS.

4.4. Hardware Architecture

Hardware architecture is usually used to describe physical topology structure and operation process, which also reflects the connection relationship and logical structure between different kinds of equipment. The hardware architecture diagram of OPMACSS is presented in Figure 5.

Figure 5:

OPMACSS hardware architecture diagram.

As Figure 5 shows, agents are connected by internet; under this circumstance, different agents can form a multiagent system if needed so as to fulfill scheduling tasks. Moreover, accounting that each agent has interfaces and databases, agents can be operated autonomously and intelligently to tackle some scheduling problem and enable users to manipulate the system to realize the scheduling process.

5. Coordination Mechanism

In the OPMACSS, agents cooperate together to fulfill the scheduling objectives. On the one hand, agents can communicate with each other to deliver scheduling information or data. On the other, when facing some conflicts, agents can negotiate to solve them and rehabilitate the normal operation. Therefore, it is of great significance to put much more emphasis on the communication mechanism and negotiation mechanism for OPMACSS.

5.1. Communication Mechanism

Knowledge Query and Manipulation Language (KQML), which is developed based on speech act theory, is a kind of widely used communication language for multiagent system. In compliance with this trend, we utilize the KQML as the communication language for OPMACSS since KQML not only supports distributed and dynamic information sharing but also enables agents in OPMACSS to interact with other systems. In this way, OPMACSS can quickly realize global scheduling and obtain data from external systems. Moreover, the communication process is achieved by message exchange pattern, which adopts KQML as its performative and XML as its content format. Thus, we construct the communication mechanism, elaborated in Figure 6.

Figure 6:

Communication mechanism of agents in OPMACSS.

In Figure 6, enterprise ontology creates the required task orders, drawings, material lists, and other documents. The messages processor can convert the contents of these documents to KQML performative and transmit them to different agents through the Internet. Each agent in the OPMACSS can accept related message through its communication module. When an agent receives a piece of message, XML analyzer and KQML analyzer map it to the local semantic representation and analyze the contents. Then, the message is transferred to local message and delivered to definition layer. In accordance with the message contents, definition module creates a series of task objectives and definitions and hands them to planning layer. Task planner extracts related algorithms, belief or knowledge from agent's library, while the coordination machine generates relevant planning strategy. Also in this layer, the monitor can autonomously supervise the task performance and help agent to respond to changes agilely. Meanwhile, each agent in OPMACSS has external interface, which not only helps agent interact with other system to obtain related data information but also makes the users to operate agent to fulfill scheduling objectives.

5.2. Negotiation Mechanism

In the process of offshore platform project scheduling, it is not unusual to see lots of conflicts, for example, critical resource conflict, operation plan conflict, construction ground conflict, and so forth. It is high time that some MAS-based negotiation mechanisms should be researched to work out these conflicts. Contract Net Protocol (CNP) is one of the most significant methods to study multiagent negotiation mechanism. By inviting bids and signing contract for the conflict goals, agents can achieve the global scheduling process. In this section, we try to establish the negotiation mechanism by CNP theory.

In the OPMACSS, the negotiation mechanism can be regarded as a kind of “competition-cooperation” mechanism. For one thing, each agent competes for opportunities to access to own profits or interests; for another thing, they unite with each other to constitute a whole system to pursue the global optimization. Additionally, the negotiation objectives can be not only a single one like the assignment of subcontracted task, but also a combination of multiple objectives like the quality, makespan, and critical resource. In the process of negotiation, each agent's information is private and, thus, the information distribution in OPMACSS will be asymmetrical. By learning own belief and other agents’ behaviors, agent can make decisions and strategies [41]. Accordingly, this paper designs a negotiation mechanism by using a multituple:

Negotiation = (SA, SG, OP, BP, Action, T, U) .

(2)

5.2.1. SA: Agent Set

Firstly, we classify the agents into bidding agent and bid agent, which are separately represented by Agent_C and Agent_S. In OPMACSS, RA and PA can be treated as a relation of Agent_C and Agent_S. RA launches bidding for critical resources and PA will bid for them so as to complete tasks. For each agent in the OPMACSS, there exists Agent_i ∈ SA.

5.2.2. SG: Negotiation Goal Set

SG = {goal₁, goal₂,…, goal_n}. Generally, for the multiple objectives, the bid agent tends to give different weights to different goals according to its preference, capacity, and urgency of tasks: R = (ω₁, ω₂,…, ω_n), ∑ω_i = 1.

5.2.3. OP: Offering Price

In the OPMACSS, agent offers its bid price according to preference, capacity, and some required elements. The negotiation process can be considered as a process of mutual bid between Agent_C and Agent_S aimed at reaching the maximum union profit. Here, we use e_OP which represents the knockdown price.

5.2.4. RP: Reservation Price

For the bidding agent, if the offering price from bid agent is less than its reservation price, the bidding agent will propose counteroffering price. Similarly, it is the same for the bid agent. During the specified time, the negotiation will not stop until the offering price reaches the agreement range. At this time, there is e_OP ∈ [BP_S, BP_C]. If BP_S > BP_C, the agreement cannot be reached. The negotiation process is illustrated as Figure 7 shows.

Figure 7:

Negotiation process between agents.

5.2.5. Action: Decision-Making Behaviors

We define three behavior patterns of agents during negotiation process: “accept,” “continue,” and “stop.” For bidding agent and bid agent, we separately define their decision-making behaviors as the following formulas:

\begin{matrix} Actio n_{C} = \{\begin{cases} Accept & if O P_{S} \geq B P_{C} \\ Continue & if O P_{S} < B P_{C} \\ Stop & if t > T_{\max}, \end{cases} \\ Actio n_{S} = \{\begin{cases} Accept & if O P_{C} \leq B P_{S} \\ Continue & if O P_{C} > B P_{S} \\ Stop & if t > T_{\max} . \end{cases} \end{matrix}

(3)

Here, we take the bid agent as an example to analyze: when counteroffering price OP_CA from bidding agent is less than bid agent's reservation price BP_S, bid agent accepts OP_CA, and negotiation process stops; when counteroffering price OP_CA is more than bid agent's reservation price BP_S, the bid agent continues to offer its bid price; only when the negotiation rounds exceed the specified rounds can the negotiation process be forced to stop.

5.2.6. T: Negotiation Rounds

During negotiation process, the negotiation time t can be dispersed to the concept of negotiation rounds. And the process of bidding and bid can be defined as one round. T_E stands for the negotiation round without punishment, while T_max stands for the maximum negotiation round. If 0 < t < T_E, the union utility will not be punished and the negotiation process continues; if T_E < t < T_max, the negotiation process still continues but the union utility will be punished; if t > T_max, the negotiation process is compelled to stop.

5.2.7. U: Negotiation Utility

According to paper [42], the union utility can be defined as the following formula:

U_{union} = \frac{(B P_{S} - e_{OP}) (e_{OP} - B P_{C})}{{(B P_{S} - B P_{C})}^{2}} .

(4)

When T_E < t < T_max, U_union′ = U_union·ξ(T), where ξ(T) stands for the penalty function. For the multiobjective negotiation, there is

\begin{matrix} U_{e} = ω \cdot U_{union} = ω_{1} {U_{1}}_{union} + ω_{2} {U_{2}}_{union} + \dots + ω_{n} {U_{n}}_{union}, \\ \sum_{i = 1}^{n} ω_{i} = 1 . \end{matrix}

(5)

During the specified negotiation rounds, the agent will allocate the task to the bidding agent which has the maximum union utility.

6. Case Study

6.1. Case Background

In order to verify the model and test the feasibility of OPMACSS, we obtain some practical data of 5 kinds of critical resource allocation in a small-scale production period from a marine enterprise in Shanghai area, China.

Figure 8 depicts the usage of different types of critical resources, in which x-axis stands for the time unit in the production period, while y-axis means the percentage of resources supply. Here, we define gas the resource supply capacity, and when all of the current storage of one kind of resource is required, then g = 100%, which means the max resource supply capacity. In Figure 8, if the point locates above the line of g = 100%, it means that there are critical resource conflicts; in other words, the current amount of this kind of resource cannot satisfy the requirements. If the point locates below the line, then there will no critical resource conflict and the tasks can be executed normally.

Figure 8:

Usage of 5 kinds of critical resources in a small-scale production period.

Critical resource conflict problem is one of the most typical problems during the production scheduling process in offshore platform project. Therefore, this section will verify the proposed mechanisms by taking the critical resource conflict resolution as an example. In accordance with the CNP theory, we propose critical resource negotiation process between agents in Figure 9.

Figure 9:

Negotiation process among agents for critical resource conflict.

In Figure 9, CA delivers the conflicted critical resource requirement from PAs to RA and then, RA issues bid message to PAs. After obtaining the message of invitation to bidding, PA tends to calculate the bidding price considering its own profit, capacity, and task attributes. When all PAs finish their bid, RA balances the offering price and proposes its counteroffering price. After a series of bidding and bid, all of the tenders can be completed. And CA calculates the union utility according to each tender and sends the winning message to RA. RA allocates the critical resources to the winning PA according to its requirement. Having accepted the critical resources, the PA can execute relevant tasks and give a feedback about the execution message to CA. Hereto, negotiation process for critical resources conflict ends.

6.2. Communication Example

Based on the description in Section 5.1, we present the communication process between different agents in OPMACSS to tackle the resource conflicts, as shown in Figure 10. The negotiation process for critical resource conflict can be roughly divided into six parts. (1) </register>: PA that needs critical resource for task production should register and attach its site. (2) </require>: after successful registration, PA can send the requirement message to CA including the resource type, item, id, quantity, and so forth. (3) </bid>: by receiving all the requirement messages, CA announces that bid begins and different PAs send the bidding message to RA according to their utility evaluation. (4) </tell>: after receiving all of the tenders, RA sends the related information to CA to facilitate the union utility calculation. (5) </award>: CA calculates the union utility and awards the winning PA that it can successfully obtain the resource to execute task, and other PAs might get the failure message. (6) </announce>: RA announces the resource allocation and sends the required resource information to the winning PA. By such a kind of message interaction, different agents in OPMACSS can cooperate with each other to fulfill the scheduling goals and negotiate to deal with the conflicts during the offshore platform construction.

Figure 10:

Communication example based on KQML.

6.3. Negotiation Example

As Figure 8 shows, there are some points, which generate resource conflicts. Now we adopt Bayesian algorithm as paper [43] shows and utilize the negotiation model as Section 5.2 presents to handle the negotiation process. Through Bayesian self-adaptive learning, agent can infer the adverse reservation price according to its own belief and knowledge. And thus, it can offer reasonable price. And by repeatedly offering price and countering price, during the specified time, the negotiation process will not stop until RA and PA reach a transaction price e_OP. Also, according to Von Neumann-Morgenstern utility function, we define $ξ (T) = c^{T_{\max} - T_{E}}$ , where c is the time coefficient, c ≤ 1; T_max stands for the limited negotiation time, and if t > T_max, the negotiation process is compelled to stop; T_E means the time period when union utility will not get punishment. Then CA calculates the union utility:

U_{union} = \frac{(c_{\max}^{'} - e_{OP}) (e_{OP} - c_{\min})}{{(c_{\max}^{'} - c_{\min})}^{2}} \cdot ξ (T) .

(6)

Consider each objective's weight. In the example, there are two kinds of critical resources; the resource set can be presented as SR = (resource1, resource2). Besides, the set of the involved agents in OPMACSS is SA = {CA, RA, PA₁, PA₂, PA₃, PA₄, PA₅}. The utility can be expressed as $U_{e} = ω \cdot U_{union} = ω_{1} {U_{1}}_{union} + ω_{2} {U_{2}}_{union}$ , and ω₁ + ω₂ = 1. We set c = 0.6, T_E = 6, and T_max = 10. Then, we get the concrete information of the negotiation process as Table 2 illustrates. At last, RA allocates the two kinds of critical resources to PA3 since PA3 can help to get the highest union utility.

Table 2:

Negotiation process for critical resources.

	1		2		3		4		5
	CA	PA1	CA	PA2	CA	PA3	CA	PA4	CA	PA5

Resource 1
RP	250	270	250	260	250	265	250	265	250	270
1st OP	—	220	—	215	—	225	—	215	—	220
Weight	—	0.4	—	0.7	—	0.6	—	0.4	—	0.5
T	4		7		6		6		4
e_OP	268		254		253		263		253
Utility 1	0.090		0.144		0.160		0.116		0.128
Resource 2
RP	660	680	660	675	660	670	660	675	660	680
1st OP	—	625	—	620	—	620	—	620	—	625
Weight	—	0.6	—	0.3	—	0.4	—	0.6	—	0.5
T	5		6		8		7		5
e_OP	677		674		664		664		662
Utility 2	0.128		0.062		0.086		0.117		0.09
Union Utility	0.1128		0.1194		0.1304		0.1166		0.1090

6.4. Resource Balance Example

On the basis of agent communication and negotiation process, OPMACSS can autonomously handle some critical resource conflicts. Now we take resource 1 as an example to verify that the application OPMACSS can help to balance the resource allocation and shorten the makespan. In the traditional scheduling method, the resource conflicts are embodied in the constraint conditions, and the early calculation is not considered, which leads to the individual conflict like Figure 11 showing the practical resource allocation situations in this production period from marine enterprise, while Figure 12 presents the usage of resource 1 after the application of OPMACSS. We can see that resource balance capacity has been improved and agents in OPMACSS can negotiate with each other to try to reach the global optimization.

Figure 11:

Usage of resource 1 before the application of OPMACSS.

Figure 12:

Usage of resource 1 after the application of OPMACSS.

Then, consider all of these five kinds of resources. We present the results by OPMACSS in Figure 13 and Table 3. Figure 13 shows that the line of each kind of resource allocation tends to be flat, when compared to Figure 8. The flatter the line is, the less severe the conflicts are. And therefore, it can help to balance the resource distribution and boost the efficiency of PA. Further, some more detailed data is presented in Table 3, which indicates the number of resource conflicts resolutions in this period. The balance of resource distribution not only can eliminate conflicts but also can abbreviate the makespan.

Table 3:

Evaluation for 5 kinds of critical resources optimization in OPMACSS.

	Resource 1	Resource 2	Resource 3	Resource 4	Resource 5

Variance before optimization	1660.5	1087.2	709.9	1110.3	1450.1
Variance after optimization	12.3	10.3	8.1	13.9	13.5
Max utilization of resource	100%	88%	96%	91%	96%
Min utilization of resource	83%	74%	87%	78%	82%
Num of multi-resource conflicts	5	2	4	0	5
Num of conflicts resolution	7	4	5	5	9

Makespan before optimization	24
Makespan after optimization	22

Figure 13:

Resource usage situation after optimization.

7. Development of the Proposed System

According to what Section 6 presents, we adopt B/S structure which consists of browser and server to develop OPMACSS. In this way, users can operate the agent via browser to realize collaborative scheduling process. Besides, a development framework based on Java and Oracle Database is utilized. The interface interaction flow is elaborated in Figure 14.

Figure 14:

OPMACSS interfaces interaction process.

In Figure 14, firstly, the login interface enables users to enter the system, while main interface provides the guided operation and basic information of agents. During the scheduling process, PA obtains project information or data from other systems through its external interfaces. Then, under the guidance of project objectives, PA can decompose the project to concrete task packages and plan the subcontracted tasks and productive tasks and, then, transfer them to CA and ECA. By overall planning, CA allocates the production task packages to different PAs aimed at decreasing the delay and cost. According to the received tasks, the PA can execute the tasks and give feedback about the execution information. For ECA, it sends request to agent address server to get related SA address to connect to them. And by negotiating with each other, ECA and SAs together fulfill the subcontract scheduling. In OPMACSS, agents’ communication and function are realized by users’ operation and data calls.

8. Conclusions and Future Work

In this paper, according to the analysis of offshore platform project scheduling, a MAS-based collaborative scheduling system (OPMACSS) was proposed. The communication mechanism based on KQML language was presented, while a negotiation model based on CNP theory was elaborated. Afterwards, system architecture was constructed to lay a foundation for the development of OPMACSS. An algorithm based on Bayesian method aimed at solving critical resource allocation was designed and the system of OPMACSS was developed. The advantages of OPMACSS can be summarized as automaticity, modularity, and flexibility. These specialties not only permit agents work autonomously and automatically to function as an integration of multiple subsystems to search for the global optimal scheduling resolutions but also enable new methods and technologies to be readily and easily added to OPMACSS.

Ongoing and future work will pay a close attention to the improvement and extension of the proposed system. Some more intelligent functions and modules will be added into the system to enhance the utility of agents. Furthermore, much more efforts will be put into the study of intelligent algorithms for collaborative scheduling so as to provide a variety of ways for agents to make decisions when facing different scheduling situations in the construction of offshore platform.

Conflict of Interests

The authors declare that there is no conflict of interests regarding the publication of this paper.

Footnotes

Acknowledgments

The support of National Natural Science Foundation of China (no. 51209045) and the High Technology for Ship Scientific Research Program of Ministry of Industry and Information Technology of China in carrying out this research is gratefully acknowledged.

References

Rodammer

F. A.

and White

K. P.

Jr. , “Recent survey of production scheduling.” IEEE Transactions on Systems, Man and Cybernetics, vol. 18, no. 6, pp. 841–851, 1988.

Adhau

Mittal

M. L.

, and Mittal

, “A multi-agent system for decentralized multi-project scheduling with resource transfers,” International Journal of Production Economics, vol. 146, no. 2, pp. 646–661, 2013.

Palmieri

Buonanno

Venticinque

Aversa

, and Di Martino

, “A distributed scheduling framework based on selfish autonomous agents for federated cloud environments,” Future Generation Computer Systems, vol. 29, no. 6, pp. 1461–1472, 2013.

Chen

Y. M.

and Wang

S. C.

, “Framework of agent-based intelligence system with two-stage decision-making process for distributed dynamic scheduling,” Applied Soft Computing Journal, vol. 7, no. 1, pp. 229–245, 2007.

Giordani

Lujak

, and Martinelli

, “A distributed multi-agent production planning and scheduling framework for mobile robots,” Computers & Industrial Engineering, vol. 64, no. 1, pp. 19–30, 2013.

Andreadisa

Klazogloub

Niotakib

, and Bouzakisa

K.-D.

, “Classification and review of multi-agent systems in the manufacturing section,” Procedia Engineering, vol. 69, pp. 282–290, 2014.

Jarray

, “A Lagrangean-based heuristics for the target covering problem in wireless sensor network,” Applied Mathematical Modelling, vol. 37, no. 10–11, pp. 6780–6785, 2013.

Zhou

and Jin

Y.-H.

, “Coordination method for multi-plants supply chain production planning based on Lagrange relaxation algorithm,” Computer Integrated Manufacturing Systems, vol. 11, no. 9, pp. 1255–1278, 2005.

Xuan

and Tang

L. X.

, “Lagrangian relaxation algorithm for real-time hybrid flowshop scheduling with no-wait in process,” Control and Decision, vol. 21, no. 4, pp. 376–380, 2006.

10.

Kim

K. W.

Yun

Y. S.

Yoon

J. M.

Gen

, and Yamazaki

, “Hybrid genetic algorithm with adaptive abilities for resource-constrained multiple project scheduling,” Computers in Industry, vol. 56, no. 2, pp. 143–160, 2005.

11.

Jianxing

and Cangyan

, “Study on resource scheduling in offshore engineering project group management based on ACO,” System Engineering Theory and Practice, vol. 27, no. 7, pp. 57–63, 2007.

12.

Fung

I. W. H.

Huang

, and Tarn

V. W. Y.

, “Application of GA techniques for solving precedent relationship problem in project scheduling optimization,” in Proceedings of the 12th East Asia-Pacific Conference on Structural Engineering and Construction (EASEC '12), pp. 2527–2534, January 2011.

13.

Lee

Z.-J.

and Lee

C.-Y.

, “A hybrid search algorithm with heuristics for resource allocation problem,” Information Sciences, vol. 173, no. 1–3, pp. 155–167, 2005.

14.

, “Combination of genetic & ant colony algorithms for multi-project resource leveling problem,” Computer Integrated Manufacturing Systems, vol. 16, no. 3, pp. 643–649, 2010.

15.

Balasbramanian

and Norrie

D. H.

, “A multi-agent intelligent design system integrating manufacturing and shop-floor control,” in Proceedings of the 1st International Conference on Multi-Agent System, pp. 3–9, San Francisco, Calif, USA, 1995.

16.

El Kamel

Gong

, and Li

, “Multi-agent based modeling and simulation of microscopic traffic in virtual reality system,” Simulation Modelling Practice and Theory, vol. 45, pp. 62–79, 2014.

17.

Wong

T. N.

Leung

C. W.

Mak

K. L.

, and Fung

R. Y. K.

, “Dynamic shopfloor scheduling in multi-agent manufacturing systems,” Expert Systems with Applications, vol. 31, no. 3, pp. 486–494, 2006.

18.

Erol

Sahin

Baykasoglu

, and Kaplanoglu

, “A multi-agent based approach to dynamic scheduling of machines and automated guided vehicles in manufacturing systems,” Applied Soft Computing Journal, vol. 12, no. 6, pp. 1720–1732, 2012.

19.

Jurado

Redondo

M. A.

, and Ortega

, “Blackboard architecture to integrate components and agents in heterogeneous distributed eLearning systems: an application for learning to program,” The Journal of Systems and Software, vol. 85, no. 7, pp. 1621–1636, 2012.

20.

Beran

P. P.

Mach

Schikuta

, and Vigne

, “A multi-staged blackboard query optimization framework for world-spanning distributed database resources,” in Proceedings of the International Conference on Computational Science (ICCS '11), pp. 156–165, Innsbruck, Austria, 2011.

21.

Vasconcelos

W. W.

García-Camino

Gaertner

Rodríguez-Aguilar

J. A.

, and Noriega

, “Distributed norm management for multi-agent systems,” Expert Systems with Applications, vol. 39, no. 5, pp. 5990–5999, 2012.

22.

Adhau

Mittal

M. L.

, and Mittal

, “A multi-agent system for distributed multi-project scheduling: an auction-based negotiation approach,” Engineering Applications of Artificial Intelligence, vol. 25, no. 8, pp. 1738–1751, 2012.

23.

Chen

and Jian

, “Research on mental coefficient-based multi-agent contract net collaborative model,” Computer Application and Software, vol. 30, no. 6, pp. 46–51, 2013.

24.

Jégou

Kim

D.-W.

Baptiste

, and Lee

K. H.

, “A contract net based intelligent agent system for solving the reactive hoist scheduling problem,” Expert Systems with Applications, vol. 30, no. 2, pp. 156–167, 2006.

25.

Wang

Jing

Wang

, and Chen

, “A distributed cooperative dynamic task planning algorithm for multiple satellites based on multi-agent hybrid learning,” Chinese Journal of Aeronautics, vol. 24, no. 4, pp. 493–505, 2011.

26.

Logenthiran

Srinivasan

, and Khambadkone

A. M.

, “Multi-agent system for energy resource scheduling of integrated microgrids in a distributed system,” Electric Power Systems Research, vol. 81, no. 1, pp. 138–148, 2011.

27.

Jinghua

Huichao

Zaiping

Miao

, and Xueying

, “Plate traceable system based on MAS in offshore equipment projects,” Computer Integrated Manufacturing Systems, CIMS, vol. 19, no. 5, pp. 1041–1050, 2013.

28.

Isern

Abellá

, and Moreno

, “Development of a multi-agent system simulation platform for irrigation scheduling with case studies for garden irrigation,” Computers and Electronics in Agriculture, vol. 87, pp. 1–13, 2012.

29.

Lau

J. S. K.

Huang

G. Q.

, and Mak

K. L.

, “Multi-project scheduling and control,” Project Mangement Journal, vol. 35, pp. 39–50, 2011.

30.

Siddiqui

M. K.

and O'Brien

W. J.

, “Multi-agent based integration of distributed scheduling algorithms,” in Proceedings of the IASTED International Conference-Intelligent Systems and Control, pp. 86–101, 2010.

31.

Chen

Y. M.

and Wang

S.-C.

, “An evolutionary compensatory negotiation model for distributed dynamic scheduling,” Applied Soft Computing Journal, vol. 8, no. 2, pp. 1093–1104, 2008.

32.

Lin

Y.-I.

Tien

K.-W.

, and Chu

C.-H.

, “Multi-agent hierarchical negotiation based on augmented price schedules decomposition for distributed design,” Computers in Industry, vol. 63, no. 6, pp. 597–609, 2012.

33.

Zhang

Gao

, and Shao

, “An agent-based approach for integrated process planning and scheduling,” Expert Systems with Applications, vol. 37, no. 2, pp. 1256–1264, 2010.

34.

Lee

Choi

B.-C.

Leung

J. Y.

, and Pinedo

M. L.

, “Approximation algorithms for multi-agent scheduling to minimize total weighted completion time,” Information Processing Letters, vol. 109, no. 16, pp. 913–917, 2009.

35.

Cheng

S.-R.

, “Some new problems on two-agent scheduling to minimize the erarliness costs,” Production Economics, vol. 156, pp. 24–30, 2014.

36.

Asadzadeh

and Zamanifar

, “An agent-based parallel approach for the job shop scheduling problem with genetic algorithms,” Mathematical and Computer Modelling, vol. 52, no. 11–12, pp. 1957–1965, 2010.

37.

Gutierrez-Garcia

J. O.

and Sim

K. M.

, “A family of heuristics for agent-based elastic Cloud bag-of-tasks concurrent scheduling,” Future Generation Computer Systems, vol. 29, no. 7, pp. 1682–1699, 2013.

38.

Bin

and Wenfeng

, “Container terminal logistics systems collaborative scheduling based on multi-agent systems,” Computer Integrated Manufacturing Systems, vol. 17, no. 11, pp. 2502–2513, 2011.

39.

Liu

Raahemi

, and Benyoucef

, “Knowledge sharing in dynamic virtual enterprises: a socio-technological perspective,” Knowledge-Based Systems, vol. 24, no. 3, pp. 427–443, 2011.

40.

Esposito

and Evangelista

, “Investigating virtual enterprise models: literature review and empirical findings,” International Journal of Production Economics, vol. 148, pp. 145–157, 2014.

41.

Gao

Zhou

, and Zeng

X.-Q.

, “Multi-agent learning negotiation research in virtual enterprise based on contract net,” Computer Integrated Manufacturing Systems, vol. 10, no. 4, pp. 471–475, 2004.

42.

Zeng

and Sycara

, “Bayesian learning in negotiation,” International Journal of Human Computer Studies, vol. 48, no. 1, pp. 125–141, 1998.

43.

Tan

Z.-F.

Wang

J.-J.

Jiang

H.-Y.

, and Wang

C.-W.

, “A fuzzy bayesian learning model in agent-based electric power bilateral negotiation,” Proceedings of the Chinese Society of Electrical Engineering, vol. 29, no. 7, pp. 106–113, 2009.

Development of a Collaborative Scheduling System of Offshore Platform Project Based on Multiagent Technology

Abstract

1. Introduction

2. Literature Review

2.1. Project Scheduling

2.2. MAS Technology

2.3. Applications of MAS Technology in Scheduling Problem

2.4. Discussions

3. Process Analysis

3.1. Network Structure Based on VE

3.2. Process Analysis for Collaborative Scheduling

3.2.1. Project-Oriented Supply Chain

3.2.2. Cross-Enterprise/Department/Profession Collaborative Operation

3.2.3. Hierarchical Scheduling Decision-Making Process

3.2.4. Distributed Decision-Making Bodies

4. Architecture of the Proposed System

4.1. System Framework

4.2. Functional Definitions of Agents

4.3. System Architecture

4.3.1. Man-Machine Interaction

4.3.2. Operation Kernel

4.3.3. Operation Environment

4.4. Hardware Architecture

5. Coordination Mechanism

5.1. Communication Mechanism

5.2. Negotiation Mechanism

5.2.1. SA: Agent Set

5.2.2. SG: Negotiation Goal Set

5.2.3. OP: Offering Price

5.2.4. RP: Reservation Price

5.2.5. Action: Decision-Making Behaviors

5.2.6. T: Negotiation Rounds

5.2.7. U: Negotiation Utility

6. Case Study

6.1. Case Background

6.2. Communication Example

6.3. Negotiation Example

6.4. Resource Balance Example

7. Development of the Proposed System

8. Conclusions and Future Work

Conflict of Interests

Footnotes

Acknowledgments

References