Sage Journals: Discover world-class research

Abstract

We study a base-agent scheduling problem of two identical parallel machines: $P 2 | Co | \sum T^{A}, C_{max}^{B}$ . The machines and tasks are regarded as agents. A new multi-agent scheduling model is proposed in order to achieve the optimum of task agents, which contains two agents: agent A and agent B. The objective is divided into two classes. The objective of agent A and agent B is to minimize total tardiness time and minimize makespan, respectively. In this article, we research character of two identical parallel machines that one category job can be processed by one machine agent only or two machine agents and propose a new multi-agent model on two identical parallel machines, divided into two subsystems. For subsystem 1, it is applied by a dynamic scheduling environment. Shortest processed time order is proposed to solve jobs’ priorities. Single distribution strategy is proposed to solve assignment of jobs to machine agents. For subsystem 2, centralized distribution strategy applied to a static scheduling environment is addressed. The new model performs more efficiently and owns a stronger ability to deal with complex and dynamic scheduling environments.

Keywords

Multi-agent scheduling two identical parallel machines agent makespan tardiness time single distribution strategy centralized distribution strategy

Introduction

Production scheduling has played an important role in production activities. With customers’ increasingly high demands for diversification, personalization, more and more enterprises undertake small-scale and customization production mode instead of mass-scale production mode. In real production, tasks come from distinct customers who have different goals. In addition, each customer may have some tasks and they also pursue different objectives. Traditional scheduling models only consider a single or two objectives for all jobs. A centralized scheduling is applied by all jobs, but different task requirements do not reflect in the models. What’s more, production process has a number of variables, such as order change, machine failure, and lack of raw materials. The model needs to be readjusted when these changes are encountered. As a result, traditional scheduling is unable to meet the requirements of customers and low agility, poor flexibility, and poor abilities to deal with variant situations.

In recent years, with cloud computing, big data, Internet of things, and other emerging technologies flourishing, agent technologies are coming. Wooldridge and Jennings¹ studied agent theory first that is mainly distinguished by two definitions: weak agent and stronger agent. There are four properties for weak agent, including autonomy, social ability, reactivity, and pro-activeness. Stronger agent has a stronger and more specific meaning than weak agent. It was not only a human-like state, but also an external human-like attributes. Since agent theory and technologies develop quickly and are applied to a lot of domains, Baker and Smith² and Agnetis et al.³ introduced the multi-agent scheduling problem and applied to multi-agent technology in production scheduling fields.

Comparing with traditional scheduling, multi-agent scheduling has some superiority. Agents have two important properties, autonomy and sociality. Tasks are divided into several agents, which each own a subset of jobs and the objective. Each agent has its own goal depending on the schedule of its only jobs. All jobs must share common resources. Agents can perceive changes and make some behave quickly to keep their goals without external intervention when encounter to external changes. Agents can also undertake social responsibility. They seek a comprehensive solution by mutual consultation to keep part and overall benefits. Multi-agent technologies having high flexibility and intelligence meet customers’ needs better and have been applied in manufacturing, such as Huang and Liao,⁴ Zhang et al.,⁵ and Li et al.⁶

Using a classical three-field notation of Graham et al.,⁷ we focus on the multi-agent scheduling problem of $P 2 | Co | \sum T^{A}, C_{\max}^{B}$ for small scale process with varieties of types and few jobs. P2 denotes the two identical parallel machine environment, Co presents a job characteristic that is competing agents, having no job in common and all jobs of an agent belong to the agent exclusively by Agnetis et al.⁸ $\sum T^{A} {, C}_{\max}^{B}$ shows optimality criteria of agent A and B, respectively. The objective of agent A is to minimize total tardiness time, while the objective of agent B is to minimize makespan.

In this article, the main contributions are shown as follows. (1) We consider all jobs have three selections to be processed, namely processed by machine A, machine B, or both first and propose a new scheduling system, building two strategies to assign jobs problem. All jobs are divided into two task agents by jobs’ objective. Each task agent has a set of jobs. Each type of job may have two or more jobs. For two identical parallel machine environments, the job may not meet requirements if it is processed by a machine only, but it can be split and processed by two machines to meet requirements or better than the former. (2) We design single distribution strategy and centralized distribution strategy applied to dynamic scheduling environment and static scheduling environment, separately. It improves the efficiency of scheduling. (3) Two machine agents are also defined as agents and all agents are given different degrees. Since each agent can make decision by oneself, agents have also status and power restriction to keep global objective and part objective balance just like the human. We introduce three classes for all agents to control our scheduling.

Literature review

In recent 10 years, many scholars have interest in multi-agent scheduling. It mainly has two research interests. Some researches focus on how to allocate job sequence by the algorithms only. For example, Zhao et al.⁹ research $P | {| C}_{max}^{A} : C_{max}^{B} \leq Q$ and propose an approximation algorithm to solve this problem effectively. Zhao and Lu¹⁰ propose (β, β)-approximation algorithms for $P_{m} | | \sum W_{j} C_{j}, C_{max}$ . Lee et al.¹¹ provide a new B&B algorithm and a genetic algorithm for $P_{m} | | \sum W_{j} C_{j}, C_{max} \leq Q$ . Elvikis and T’kindt¹² study a two-agent scheduling problem on uniform parallel machines and provide a minimal complete pareto set enumeration algorithm.

However, other studies mainly focus on mechanisms of allocating jobs. Many authors have analyzed various good mechanisms based on the game strategies. For example, Cohen et al.¹³ introduce a game-theoretic model for the problem of scheduling parallel rigid jobs on multicore platforms by a price cost to choose the best strategy for their jobs. Cole et al.¹⁴ state simple mechanisms that require only local information. Authors use the game-theoretic insights to obtain a new combinatorial approximation algorithm for the underlying optimization problem. Zhao et al.¹⁵ state two agents scheduling problem on single machine. They design the pareto efficient solution set and the Shapley value method and evaluate two agents’ job sequence by comparing net profit and opportunity. Marini et al.¹⁶ develop preventive or minimax strategies, best-response strategies to solve the scheduling problem of two agents competing to add items in a solution set. Ye and Zhang¹⁷ design and analyze coordination mechanisms for machines and consider the class of policies based on the Bottom-Left and the Shelf-Packing algorithms. Mashayekhy et al.¹⁸ research the reward-based multi-agent scheduling problem of periodic tasks. Each task’s execution is divided into a mandatory and optional part. Each task gets a value if its mandatory parts are completed and obtains an additional reward value if its optional part is finished. They designed an exact and approximate mechanism for selecting a feasible subset of agents and an allocation of optional execution. Anussornnitisarn et al.¹⁹ consider viability of each agent during the coordination process and develop an agent decision model. By applying market-based pricing and costing approach in the coordination network participants’ decisions, it chooses a monetary unit as common medium of exchange for the coordination process.

On the other hand, some authors consider the multi-agent scheduling problem from centralized perspective and single agent perspective. Nicosia et al.²⁰ investigate a two-agent single machine scheduling problem from centralized perspective and single agent perspective. Shortest processed time (SPT), weight shortest processed time, and minimax strategies method are used to optimize the objective of one agent. Agnetis et al.²¹ explore a two-agent scheduling problem of single machine that one agent knows all information in advance about the submission sequence of opponent, but other agent has no information on the opponent strategy in order to minimize its solution cost in the worst possible case from centralized perspective and single agent perspective and design a selection strategy.

In addition, there are some another strategy to be applied. For instance, Agnetis et al.²² show a deterministic scheduling problem about two agents in three different shop configurations. Tasks of the agents are submitted in successive steps to an external coordinator as a priority rule. Moreover, single agent perspective and centralized perspective both are considered to achieve part and global objectives. Liang and Fung²³ propose explicit and implicit coordination mechanisms based on multi-agent technology to solve the real-time scheduling of virtual cellular manufacturing systems. And they designed point-to-point and subscribe/publish communication model to realize the real-time scheduling.

However, how to assign jobs’ sequence and how to assign jobs to machine agents are still two important issues for parallel machines scheduling. For assigning jobs to machine agents, most literatures consider the job as a whole, while there are three states for the processed job, processed by one machine or two machines for two parallel machines scheduling. Therefore, we consider that the job can be split and processed on two machines if it can achieve the optimum better.

In practical, although scheduling environment is a variable, sometimes it keeps an unchanged environment. Centralized scheduling is more efficient scheduling model and suitable for static scheduling environment. Hence, we build a new multi-agent scheduling mode and introduce two strategies. One is single distribution strategy applied to dynamic scheduling environment that one only job is sent to earliest available machine agent as SPT order when machine agent having no job to be processed. Task agents submit one category job, and it is presorted with current processing jobs on two machine agents to achieve the goal of the job. Other is centralized distribution strategy applied to a static scheduling environment that jobs are unchanging during a period. All jobs are submitted and sent to coordination agent. Coordination agents make scheduling plan and machine agents process it as the plan. In order to ensure the goals of scheduling, we divide three classes for all agents and define their function.

The remaining of the article is organized as follows: in section “Problem descriptions,” we address backgrounds of the problem studied in this article. In section “Multi-agent system,” we state the structure of multi-agent system. In section “Resolution methods,” a new model is given, having two strategies: single distribution strategy applied to a dynamic scheduling environment and centralized distribution strategy applied to a static scheduling environment. Finally, the conclusion of the article is made in section “Conclusion.”

Problem descriptions

In this article, we consider $P 2 | Co | \sum T^{A} {, C}_{\max}^{B}$ . All jobs for small scale process with varieties of types and few jobs are divided into two competing task agents (A and B), each having a set of job $Γ^{x} = {J_{1}^{x}, J_{2}^{x}, \dots, J_{n_{i}}^{x}}$ . Each has its own set of independent and non-preemptive jobs. Jobs of agent A have n_A species of jobs and jobs of agent B have n_B species of jobs. All jobs have n (n = n_A + n_B) species. The number of each categories of job is $n_{i}^{x}$ . The processing time of a job i is denoted by $P_{i}$ . A setup is not considered. All jobs are available for processing at time zero. Processing times all jobs are known in advance.

Each type of job can be processed by one machine or two machines when the number of $n_{i}^{x}$ is more than two jobs. Objective of agent A is to minimize total tardiness time $\sum T^{A}$ . Objective of agent B is to minimize the makespan $C_{\max}^{B}$ . Agent A and agent B finish their jobs as the objective, yet they must compete for resources to keep their benefits. Meanwhile, we hope achieving overall objective that is to minimize $\sum T^{A}$ and $C_{\max}^{B}$ . LF_i defines actual finishing time of job i. D_i denotes due time of job i. T_i denotes the tardiness time of job i:

The tardiness time function from task agent A

T_{i} = {\begin{matrix} max {0, ({LF}_{i}^{x} - D_{i})}, one machine; \\ \max {0, (L F_{i} - D_{i})}, L F_{i} \in max {{LF}_{i}^{A}, {LF}_{i}^{B}}, both \end{matrix}

(1)

The total tardiness time function from agent A

\sum T^{A} = \sum T_{i}

(2)

The overall objective function

Z_{overall} = \min (\sum T^{A} + C_{\max})

(3)

Suppose two machine agents (M1 and M2) belong to two identical parallel machines, each having same function and processing speed for same jobs. Machine agents know its own status and meet the jobs’ objective as soon as possible. All agents can communicate with each other, such as machine agent M1 and M2, machine agents and task agents. And machine agents can make autonomous decision based on own status.

Multi-agent system

In this section, we address structure of multi-agent system and discuss $P 2 | Co | \sum T^{A} {, C}_{\max}^{B}$ in detail. It includes the architecture and operation process of multi-agent system.

Architecture of multi-agent system

Huang and Liao⁴ develop three categorizes of agents: job agents, machine agents, and supervisor agent in multi-agent system to support the dynamic negotiation mechanism. However, in our multi-agent system, it is also made up of three types of agents and contact each other by “dialogue,” to achieve global and part objective for $P 2 | Co | \sum T^{A} {, C}_{\max}^{B}$ . We design the model, which of elements contain task agent A and B, machine agent M1 and M2, coordination agent. All jobs are divided into two task agents. The objective of agent A is to minimize the total tardiness time. The objective of agent B is to minimize makespan. There are two parallel machine agents, agent M1 and M2, to pursue meeting the task agents’ objective as soon as possible. Coordination agent plays an important role in scheduling phase. It is a control center to keep the regular scheduling activity. The multi-agent system is shown in Figure 1.

Figure 1.

Architecture of multi-agent system.

Multi-agent system can be categorized by two subsystems. One consists of task agents and machine agents. Other comprises all agents. In subsystem 1, all agents can contact each other and they are utilized as a dynamic scheduling environment. However, task agents can’t communicate with machine agents directly in subsystem 2. Coordination agent is not only a bridge for connecting tasks agents and machines agents but also a scheduling center dealing with a static scheduling environment.

Priorities of agents

In multi-agent system, each agent’s making-decision priorities are distinct and are divided into three chasses (Table 1). The degree of coordination agent is the highest among all agents. Task agents and machine agents must accept the command of coordination agent and finish the works first without conditions. The degree of machine agent is higher than task agents. Its functions include accepting or rejecting the jobs from task agents if coordination agent has no requirements. The degree of task agent is the weakest among these agents. Its functions contain submitting the jobs to coordination agent and machine agents, ranking the jobs in SPT order.

Table 1.

Priorities of agents.

Agents	Making-decision priority	Function
Coordination agent	The first class	1. Accept the information from other agents; 2. Make scheduling plan; 3. Send command.
Machine agents	The second class	1. Accept or reject the jobs if coordination agent doesn’t oppose it; 2. Accept the demand from coordination agent.
Task agents	The third class	1. Accept the demand from coordination agent; 2. Rank the jobs in SPT order; 3. Submit the jobs to coordination agent or machine agents.

Operation process

Operation process of multi-agent system is designed (Figure 2). It splits two subsystems: subsystem 1 and subsystem 2. We discuss their operation process respectively.

Figure 2.

Operation process of system.

Operation process of subsystem 1

Subsystem 1 consists of two task agents and two machine agents, and it applies to a dynamic scheduling environment. For example, jobs of task agents are variable frequently so that production plan needs to be changed in real time to meet customers’ need. Thus, we design subsystem 1 whose theory is task agents send jobs information to machine agents one by one and machine agents allocate jobs by communication.

When task agents are variable frequently, we rank all jobs in SPT order in initial time. If new jobs information enters task agents, they resort the remaining jobs in SPT order. Each task agent sends the top job information as SPT order to machine agents each round if machine agent is idle. Machine agents accept job information and each machine agent makes a production plan. If production plan of two machine agents all can satisfy requirement, the jobs are processed by the early machine. If only one machine agent can satisfy requirement, the jobs are processed by it. If no machine agents can meet jobs’ objective, machine agents will develop new production plan through consultations. Machine agents implement the production plan until finishing the job. When machine agent is idle, it sends messages to task agents. Task agents will send new job to them. The scheduling is over until task agents have no jobs.

Operation process of subsystem 2

Compared with subsystem 1, subsystem 2 has a center of scheduling: coordination agent. Like the human brain, coordination agent controls the remaining agents. Due to the central scheduling mode, subsystem 2 can maintain a high efficiency. It applies to a static scheduling environment. In instance, orders keep stability and machine agents keep health in a long time. In subsystem 2, task agents must submit all jobs information to coordination agent, and machine agents send their status to coordination agent; Coordination agents make a central scheduling by centralized distribution strategy and send the plan to machine agents. Machine agents must accept the command to process the jobs.

Resolution methods

In $P 2 | Co | \sum T^{A} {, C}_{\max}^{B}$ multi-agent system, there are two sub-problems to be solved. For task agents, how to assign jobs’ sequence? For machine agents, how to select jobs and process them. Therefore, for subsystem 1, we consider the two phases in the following sections. For phase 1, all jobs are sequenced by the shortest processed time (SPT) order to rank jobs’ sequence. For phase 2, we introduce single distribution strategy to assign jobs to machine agents. For subsystem 2, all jobs are processed by a centralized scheduling. We introduce centralized distribution strategy for subsystem 2.

Single distribution strategy

Phase 1: problem of the jobs’ sequence

From task agents’ perspectives, we consider phase 1. Classical SPT order is used by sorting the jobs’ sequence. All jobs are ranked based on their processing time from small to big. If some jobs have same processing time, we rank them as due time from small to big.

Example 1

We consider that $n_{A} = 3, n_{B} = 3$ and parameters of their jobs are as shown in Table 2.

Table 2.

Values of tasks parameters.

$J_{i}^{x}$	$J_{1}^{A}$	$J_{2}^{A}$	$J_{3}^{A}$	$J_{1}^{B}$	$J_{2}^{B}$	$J_{3}^{B}$
$n_{i}^{x}$	2	4	3	3	2	1
$P_{i}^{x}$	1	1	2	1	2	3
$n_{i}^{x *} P_{i}^{x}$	2	4	6	3	4	3
$D_{i}^{x}$	5	5	6	4	7	8

Therefore, all jobs’ sequences in task agents are ${Γ = {J}_{1}^{A} {, J}_{1}^{B} {, J}_{3}^{B} {, J}_{2}^{A} {, J}_{2}^{B} {, J}_{3}^{A}}$ as $n_{i}^{x *} P_{i}^{x}$ from small to big. In task agent A, the jobs’ sequences are $Γ^{A} = {J_{1}^{A}, J_{2}^{A}, J_{3}^{A}}$ . In task agent B, the jobs’ sequences are $Γ^{B} = {J_{1}^{B}, J_{3}^{B}, J_{2}^{B}}$ .

Phase 2: assign the job to machine agents

Single distribution strategy is mainly applied to dynamic scheduling. From machine agents’ perspectives, task agents submit one special of job as SPT order to machine agents each round when machine agent requires it. The machine agent selects the job as earliest available rule of machine agent. We must keep objective of the job to be optimum. Therefore, we research all scenarios of one job when the job is processed. Assume that machine agent M1 is the earliest available. We partition it into two types: one is the job i from agent A is submitted and other is job j from agent B is submitted. We discuss the two situations as follows.

Job i from agent A is submitted

Assuming that job i will be assigned to earliest available machine agent M1 when it has no job. Machine agent M2 is processing its jobs in current time. We analyze jobs’ status of machine agents at this time. For jobs from agent A, its objective is to minimize total tardiness time. We consider splitting job and presort job i if it can be split. It may have six kinds of situations (Figure 3).

Finishing time of remaining job of machine agent M2 is larger than that of job i, and the job i can be finished on time. Hence, the job i is processed as the original plan and has no tardiness.

Finishing time of remaining job of machine agent M2 is larger than that of job i, but it is not finished on time. However, the job i can’t be modified and processed as the original plan. Its tardiness time is (C1-Di).

Finishing time of remaining job of machine agent M2 is equal to that of the job i, and the job i can be finished on time. Hence, the job i is processed as the original plan and has no tardiness.

Finishing time of remaining job of machine agent M2 is equal to that of the job i, but the job i cannot be finished on time. But the job i cannot be modified and is processed as the original plan. Its tardiness time is (C1-Di).

Finishing time of remaining job of machine agent M2 is smaller than that of job i, and the job i can be finished on time. Hence, the job i is processed as the original plan and has no tardiness.

Finishing time of remaining job of machine agent M2 is smaller than that of job i, but the job i cannot be finished on time. If $C_{1} - C_{2} < 2 P_{i}$ (see f1 scenario in Figure 3), the job i cannot be modified and is processed as the original plan. Its tardiness time is (C1-Di). If $C_{1} - C_{2} \geq 2 P_{i}$ (see f2 and f3 scenario in Figure 3), the job i can be split and processed by two machine agents. The objective of splitting job i is to minimize the tardiness. The algorithm is shown as follows:

Figure 3.

Situation of presorting job i.

Figure 4.

Situations of presorting job j.

From algorithm 1, first, we judge whether the job i can be split. Second, if it can be split, we judge what extent the job can be. If it can meet due time of job i by splitting job, it has no tardiness (sentence 13 in algorithm 1). If it cannot meet due time of job i by splitting job, it splits the job i to attain the optimum and its tardiness time is $C_{1} = C_{0} + (n_{i} - ⌊ q ⌋) P_{i} - D_{i}$ (sentence 17 in algorithm 1). If job i cannot be split, its tardiness time is $(C_{0} + n_{i} P_{i} - D_{i})$ (sentence 20 in algorithm 1).

2. Job j from agent B is submitted

Algorithm 1. Split job i from agent A at f scenario for subsystem 1

Assume machine agent M1 is the earliest available machine. Job j from agent B is candidate for next job of M1. The job j is submitted to M1. For jobs from agent B, its objective is to minimize makespan. We consider splitting job j and presort job j if it can be split to achieve current objective of job j. It can also have three kinds of situations:

Finishing time of remaining job of machine agent M2 is larger than that of job j. And the job j can be finished before finishing jobs of M2. Hence, the job j is processed as the original plan. Its makespan is C₁.

Finishing time of remaining job of machine agent M2 is equal to that of job j. And the job j can be finished the same as that of M2. Hence, the job j is processed as the original plan. Its makespan is C₁.

Finishing time of remaining job of machine agent M2 is smaller than that of job j. But the job j can be finished after that of M2. If $C_{1} - C_{2} < 2 P_{i}$ (see c1 scenario in Figure 4), the job j cannot be modified and is processed as the original plan. Its makespan is C₁. If $C_{1} - C_{2} \geq 2 P_{i}$ (see c2 scenario in Figure 4), the job j can be split and processed by two machine agents.

Figure 5.

Gant chart of single distribution strategy and SPT order.

The algorithm is shown as follows:

From algorithm 2, first, we judge whether the job j can be split. Second, if it can be split, we judge what extent the job can be. It splits the job j to attain the optimum; its makespan is $(C_{0} + n_{j} P_{j})$ (sentence 10 in algorithm 2). If no, its makespan is C₁ (sentence 12 in algorithm 2).

Single distribution strategy is explained as follows:

Step 1. All jobs of Task agents are sequenced in SPT order.

Step 2. Task agents submit one type of job of the shortest processing time to the earliest available machine agent.

Step 3. Judge if objective of each processing job on machine agents achieves the optimum as current sequence. If the objective of each job achieves the optimum, go to step 4. If no, go to step 5.

Step 4. Machine agents process jobs, go to step 6.

Step 5. If the job comes from agent A and can be split, it splits it by algorithm 1. If the job comes from agent B, and it splits by algorithm 2. Go to step 4.

Step 6. If new jobs enter task agents before machine agent are idle again, it updates jobs’ sequences. If no, go to step 7.

Step 7. If task agents have jobs, go to step 2. If no, the scheduling is over.

Algorithm 2. Split job j from agent B at c scenario for subsystem 1

Property 1

For the scheduling problem in subsystem 1, the time complexity of problem can be solved in $O (\sum n_{i}^{x})$ , where $\sum n_{i}^{x}$ denotes the number of all jobs of problem.

Example 2

Suppose $n_{A} = 3, n_{B} = 3$ and parameters of their job are as shown in Table 2 from Example 1. We use single distribution strategy and SPT to solve $P 2 | Co | \sum T^{A}, C_{\max}^{B}$ respectively (Table 3). The end results are shown as follows (Figure 5).

Table 3.

Objective values of SPT order and single distribution strategy.

Method	$T_{1}^{A}$	$T_{2}^{A}$	$T_{3}^{A}$	$\sum T$	$C_{max}$	$Z_{overall}$
SPT order	0	2	7	9	9	18
Single distribution strategy	0	1	6	7	8	15

The total tardiness time of agent A is 9 and makespan of agent B is 9 in SPT order. For single distribution strategy, the total tardiness time of agent A is 7 and makespan of agent B is 8. For overall objective value, value of single distribution strategy is 15, while the SPT order is 18. Therefore, single distribution strategy that the jobs can be split has a better performance than SPT order.

Centralized distribution strategy for subsystem 2

Different from single distribution strategy, centralized distribution strategy can be applied to static scheduling. Task agents submit all jobs to coordination agent and machine agents submit own status to coordination agent. Coordination agent considers centralized optimum, assigning all jobs to machine agents. We introduce a hybrid strategy based on longest processed time (LPT) rule, SPT rule, and the jobs to be processed by one machine agent or two machine agents. Coordination agent makes a production scheme and sends it to machine agents, and machine agents accept the command and process jobs.

From algorithm 3, first, we arrange all jobs in LPT order and assume assigning all jobs as LPT rule to machine agents. Second, reassign the jobs in SPT order for each machine agent. If some jobs have same processing time as LPT or SPT order, we rank them as due time from small to big. Third, we execute algorithm 4 to minimize the total tardiness time except for final processing jobs both two machine agents. Fourth, we execute algorithm 5 to minimize makespan for the job from agent B. Fifth, we execute algorithm 4 again to revision when the total tardiness time changes. Finally, we adjust the final processing jobs on two machines agents to minimize their completion time gap.

Algorithm 3. Centralized distribution strategy for subsystem 2

Algorithm 4. Minimize total tardiness times for the jobs from agent A in subsystem 2

Algorithm 5. Minimize makespan for the job from agent B in subsystem 2

Centralized distribution strategy is explained as follows:

Step 1. Arrange all jobs in LPT order.

Step 2. Assign all jobs as LPT rule to machine agents.

Step 3. Reassign the jobs in SPT order for each machine agent.

Step 4. Compute the total tardiness time of jobs from agent A except for the final processing jobs both two machine agents.

Step 5. If the job from agent A has tardiness, it selects an earliest tardiness job k and judges it if it can be split. If the job from agent A has no tardiness or cannot be split, go to step 7 (see Algorithm 4).

Step 6. If the job k can be split, it selects the job h from agent A allocated by other machine agent whose finishing time is less than job k, but it is the closest to job k. It splits the job k and adds the part of job k partitioned into other machine agent behind job h until minimize the tardiness time of job k. Then, the job k has moved out the agent A, go to step 5. It is not over until agent A having no tardiness. Go to step 7 (see Algorithm 4).

Step 7. If the finishing time of job i is largest finishing time for agent B, it selects the job i and judges it if it can be split. If the job can’t be split, go to step 10 (see Algorithm 5).

Step 8. If job i can be split, it selects the job j allocated by other machine agent from agent B whose finishing time is less than job k, but it is the largest finishing time from other machines. It splits the job i and adds the part of job i partitioned into other machine agent behind job j but is adjacent to job j until minimize makespan. Go to step 9 (see Algorithm 5).

Step 9. If it has some jobs behind job i from agent A except for the final processing job and the jobs can be split, go to step 5 for the jobs. If the jobs have no tardiness or cannot be split, go to step 10.

Step 10. Adjust the final processing jobs by two machine agents to minimize their completion time gap. The scheduling is over.

Example 3

We use centralized distribution strategy to solve same problem from Example 2 (Figure 6). The end results are shown as follows.

Figure 6.

Gant chart of centralized distribution strategy.

For centralized distribution strategy, the total tardiness time of agent A is 5 and makespan of agent B is 9, and the overall objective value is 14. As shown in Table 4, centralized distribution strategy that the jobs can be split has a better performance than SPT order. Comparing with objective of agent B, makespan in centralized distribution is bigger than that in single distribution strategy, but the overall performance is better. Hence, the new model performs more efficiently and has a stronger ability to deal with complex and dynamic scheduling environments.

Table 4.

Objective values of SPT order, single distribution strategy, and centralized distribution strategy.

Method	$T_{2}^{A}$	$T_{3}^{A}$	$\sum T$	$C_{max}$	$Z_{overall}$
SPT order	2	7	9	9	18
Single distribution strategy	1	6	7	8	15
Centralized distribution strategy	0	5	5	9	14

Conclusion

In this article, we consider a multi-agent scheduling problem of two identical parallel machines. We study $P 2 | Co | \sum T^{A} {, C}_{\max}^{B}$ and design a multi-agent system which can be applied to dynamic and static environment flexibly and suitable for a discrete and small scale production problem. The multi-agent system is divided into two subsystems. In subsystem 1, the scheduling problem is divided into two phases. For jobs’ sequences phase, we sort all jobs in SPT order to solve jobs’ sequences. For assigning the jobs to machines, we take one special of job processed by one machine only or two machine both into account and provide single distribution strategy, which the job is processed by the earliest available machine agent and jobs can be split and assigned to two machine agents. In subsystem 2, task agents submit information of all jobs and machine agents submit their status to coordination agent. Coordination agent makes a centralized scheduling scheme based on centralized distribution strategy based on LPT rule, SPT rule, and the jobs to be processed by one machine agent or two machine agents. The two strategies are flexible and efficient methods compared with SPT order.

In the future, we will consider three scenarios: first, machine agent don’t select allocation each other and compete for each other, what strategies are given to achieve the optimal scheduling; second, we already suppose all jobs’ information are known in advance, it will be studied that machine agents don’t know the jobs’ information before starting work or know a part of information, how to solve this problem; third, how to allocate the jobs to machine agents when we consider setup time. What’s more, we will improve single distribution strategy and centralized distribution strategy to meet customers’ need.

Footnotes

Academic Editor: Murat Uzam

Declaration of conflicting interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) disclosed receipt of the following financial support for the research, authorship, and/or publication of this article: This work was supported by the National Natural Science Foundation of China (NSFC, no. 71501020).

References

Wooldridge

Jennings

NR.

Intelligent agents: theory and practice. Knowl Eng Rev 1995; 10: 115–152.

Baker

Smith

JC.

A multiple-criterion model for machine scheduling. J Sched 2003; 6: 7–16.

Agnetis

Mirchandani

Pacciarelli

. Scheduling problems with two competing agents. Oper Res 2004; 52: 229–242.

Huang

Liao

LM.

Parallel machines scheduling with machine preference via agent-based approach. Appl Math Comput 2014; 233: 298–309.

Zhang

Wang

Liu

Development of a collaborative 3D virtual monitoring system through integration of cloud computing and multiagent technology. Adv Mech Eng 2014; 6: 762091.

Yang

. Development of a collaborative scheduling system of offshore platform project based on multiagent technology. Adv Mech Eng 2014; 6: 298149.

Graham

Lawler

Lenstra

. Optimization and approximation in deterministic sequencing and scheduling: a survey. Ann Dis Mthm 1979; 5: 287–326.

Agnetis

Billaut

Gawiejnowicz

. Multi-agent scheduling. Oper Res Decis Theor 2014; 10: 13–14.

Zhao

A new approximation algorithm for multi-agent scheduling to minimize makespan on two machines. J Sched 2016; 19: 21–31.

10.

Zhao

Two approximation algorithms for two-agent scheduling on parallel machines to minimize makespan. J Comb Optim 2016; 31: 260–278.

11.

Lee

Wang

Lin

MC.

A branch-and-bound algorithm for minimizing the total weighted completion time on parallel identical machines with two competing agents. Knowl-Based Syst 2016; 105: 68–82.

12.

Elvikis

T’kindt

Two-agent scheduling on uniform parallel machines with min-max criteria. Ann Oper Res 2014; 213: 79–94.

13.

Cohen

Cordeiro

Trystram

Coordination mechanisms for decentralized parallel systems. Concurr Comp Pract E 2015; 27: 1255–1272.

14.

Cole

Correa

Gkatzelis

. Decentralized utilitarian mechanisms for scheduling games. Game Econ Behav 2015; 92: 306–326.

15.

Zhao

Ruan

. Two game-based solution concepts for a two-agent scheduling problem. Cluster Comput 2016; 19: 769–781.

16.

Marini

Nicosia

Pacifici

. Strategies in competing subset selection. Ann Oper Res 2013; 207: 181–200.

17.

Zhang

. Coordination mechanisms for selfish parallel jobs scheduling. In: Proceedings of the international conference on theory and applications of models of computation, Beijing, China, 16–21 May 2012, pp.225–236. Berlin, Heidelberg: Springer.

18.

Mashayekhy

Fisher

Grosu

Truthful mechanisms for competitive reward-based scheduling. IEEE T Comput 2015; 65: 2299–2312.

19.

Anussornnitisarn

Nof

Etzion

Decentralized control of cooperative and autonomous agents for solving the distributed resource allocation problem. Int J Prod Econ 2005; 98: 114–128.

20.

Nicosia

Pacifici

Pferschy

Scheduling the tasks of two agents with a central selection mechanism. Optimization Online 2014: 02–4222.

21.

Agnetis

Nicosia

Pacifici

. Scheduling two agent task chains with a central selection mechanism. J Sched 2015; 18: 243–261.

22.

Agnetis

Nicosia

Pacifici

. Two agents competing for a shared machine. In: Proceedings of the international conference on algorithmic decision theory, Bruxelles, Belgium, 13–15 November, 2013, pp.1–14. Berlin, Heidelberg: Springer.

23.

Liang

Fung

RYK

. Coordination mechanism in real-time scheduling of Virtual Cellular Manufacturing Systems. Proc IMechE, Part B: J Engineering Manufacture 2016; 230: 534–547.