A multi-agent scheduling problem for two identical parallel machines to minimize total tardiness time and makespan

Abstract

We study an agent-based scheduling problem of two identical parallel machines: $\mathrm{P}2\left|\mathrm{Co}\right|{\displaystyle \sum {\mathrm{T}}^{\mathrm{A}}},C_{\max }^{\mathrm{B}}$ . The machines and tasks are regarded as agents. A new multi-agent scheduling model is proposed to achieve the optimum from the two task agents, agent A and agent B. The objective is divided into two classes. The objectives of agent A and agent B are to minimize the total tardiness time and minimize the makespan, respectively. In this article, we research two identical parallel machines in which one job category can be processed by one machine agent only or two machine agents and propose a new multi-agent model for two identical parallel machines, divided into two subsystems. For subsystem 1, the shortest processing time order is used to solve job priorities. A single distribution strategy is proposed to assign jobs to machine agents and is applied to the dynamic scheduling environment. For subsystem 2, a centralized distribution strategy is applied to the static scheduling environment. The proposed model performs more efficiently and is better able to handle complex and dynamic scheduling environments.

Introduction

Production scheduling plays an important role in production activities. With customers’ increasingly high demands for diversification and personalization, more enterprises undertake small-scale and customized production modes instead of mass-scale production modes. In real production, tasks come from distinct customers who have different goals. Each customer may have different tasks and different objectives. Traditional scheduling models only consider a single objective or two objectives for all jobs. Centralized scheduling is applied to all jobs, but different task requirements are not reflected in the models. A production process has a number of variables, such as order change, machine failure, and lack of raw materials. The model must be readjusted when these changes occur. As a result, traditional scheduling is unable to meet the requirements of customers and has low agility and poor flexibility and is not able to handle variant situations.

With the increasing use of cloud computing, big data, the Internet of Things, and other emerging technologies, agent technologies are currently under development. Wooldridge and Jennings ¹ studied agent theory, which is mainly distinguished by two definitions: the weak agent and the stronger agent. The weak agent has four properties: autonomy, social ability, reactivity, and pro-activeness. The stronger agent has a stronger and more specific meaning than the weak agent. The stronger agent is not only a human-like state but also has external human-like attributes. Considering the rapid development of agent theory and technologies and their application to several domains, Baker and Smith ² and Agnetis et al. ³ introduced the multi-agent scheduling problem and applied it to multi-agent technology in production scheduling fields.

Multi-agent scheduling is superior to traditional scheduling in several respects. Agents have two important properties, autonomy and sociality. Tasks are divided into several agents, each of which owns a subset of jobs and the objective. Each agent has its own goal depending on the schedule of its jobs. All jobs must share common resources. Agents can perceive changes and change certain behaviors rapidly to maintain their goals without external intervention when encountering external changes. Agents can also undertake social responsibility. They seek a comprehensive solution by mutual consultation to keep individual and overall benefits. Multi-agent technologies, such as those introduced by Huang and Liao, ⁴ Zhang et al., ⁵ and Li et al., ⁶ have high flexibility and intelligence, are better able to meet customers’ needs, and have been applied in manufacturing.

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

The main contributions of this article are as follows. (1) We consider that all jobs have three selections—to be processed by machine A, machine B, or both—and propose a new scheduling system, building two strategies to assign jobs. All jobs are divided into two task agents according to the jobs’ objectives. Each task agent has a set of jobs. Each type of job may have two or more jobs. For an environment with two identical parallel machines, the job may not meet the requirements if it is processed by one machine only, but it can be split and processed by two machines to better meet the requirements than in the former case. (2) We design a single distribution strategy and centralized distribution strategy and apply them to a dynamic scheduling environment and static scheduling environment separately. These strategies improve the scheduling efficiency. (3) Two machine agents are also defined as agents, and all agents are given different degrees. Because each agent can make decisions by itself, agents have status and power restrictions to maintain the balance between the global objective and individual objective, similar to humans. We introduce three classes for all agents to control our scheduling.

Literature review

Many scholars have been interested in multi-agent scheduling over the past 10 years. There are two main research interests. First, research has focused on how to allocate a job sequence using only algorithms. For example, Zhao et al. ⁹ considered $\mathrm{P}|{|\mathrm{C}}_{\max }^{\mathrm{A}}:{\mathrm{C}}_{\max }^{\mathrm{B}}\le \mathrm{Q}$ and proposed an approximation algorithm to solve this problem effectively. Zhao and Lu ¹⁰ proposed (β, β)-approximation algorithms for ${\mathrm{P}}_{\mathrm{m}}||\sum {\mathrm{W}}_{\mathrm{j}}{\mathrm{C}}_{\mathrm{j}},{\mathrm{C}}_{\max }$ . Lee et al. ¹¹ presented a new branch-and-bound (B&B) algorithm and a genetic algorithm for ${\mathrm{P}}_m||\sum {\mathrm{W}}_{\mathrm{j}}{\mathrm{C}}_{\mathrm{j}},{\mathrm{C}}_{\max }\le \mathrm{Q}$ . Elvikis and T’kindt ¹² studied a two-agent scheduling problem on uniform parallel machines and provided a minimal complete Pareto set enumeration algorithm.

Other studies have mainly focused on the mechanisms of allocating jobs. Many authors have analyzed various mechanisms based on game strategies. For example, Cohen et al. ¹³ introduced a game theoretic model for the problem of scheduling parallel rigid jobs on multicore platforms with a price cost to determine the best strategy for their jobs. Cole et al. ¹⁴ presented simple mechanisms that required only local information and used the game theoretic insights to obtain a new combinatorial approximation algorithm for the underlying optimization problem. Zhao et al. ¹⁵ considered a two-agent scheduling problem on a single machine. They designed a Pareto-efficient solution set and used the Shapley value method to evaluate the job sequence of two agents by comparing the net profit and opportunity. Marini et al. ¹⁶ developed preventive or minimax strategies and best-response strategies to solve the scheduling problem of two agents competing to add items to a solution set. Ye and Zhang ¹⁷ designed and analyzed coordination mechanisms for machines and considered the class of policies based on the bottom-left and shelf-packing algorithms. Mashayekhy et al. ¹⁸ considered a reward-based multi-agent scheduling problem for periodic tasks. The execution of each task is divided into a mandatory part and an optional part. Each task receives a value if its mandatory parts are completed and receives an additional reward value if its optional part is completed. These authors designed an exact and approximate mechanism for selecting a feasible subset of agents and an allocation to achieve the optional execution. Anussornnitisarn et al. ¹⁹ considered the viability of each agent during the coordination process and developed an agent decision model that chooses a monetary unit as a common medium of exchange for the coordination process by applying a market-based pricing and costing approach in the decisions of the coordination network participants.

Some authors consider the multi-agent scheduling problem from a centralized perspective and a single-agent perspective. Nicosia et al. ²⁰ investigated a two-agent, single-machine scheduling problem from a centralized perspective and a single-agent perspective. The shortest processing time (SPT), weight shortest processing time (WSPT), and minimax strategy method were used to optimize the objective of one agent. Agnetis et al. ²¹ investigated a two-agent, single-machine scheduling problem in which one agent has all of the information about the submission sequence of the opponent in advance but the other agent has no information on the opponent’s strategy, representing the worst possible case. The authors minimized the solution cost in this case from a centralized perspective and single-agent perspective and designed a selection strategy.

Several other strategies have been applied in the literature. For instance, Agnetis et al. ²² presented a deterministic scheduling problem with two agents for three different shop configurations. The agent tasks are submitted in successive steps to an external coordinator as a priority rule. A single-agent perspective and centralized perspective are both considered to achieve partial and global objectives. Liang and Fung ²³ proposed explicit and implicit coordination mechanisms based on multi-agent technology to solve the real-time scheduling of virtual cellular manufacturing systems. They designed the point-to-point and subscribe/publish communication mode to realize real-time scheduling.

However, how to assign a job sequence and how to assign jobs to machine agents are still two important issues for parallel machine scheduling. When assigning jobs to machine agents, most previous studies have considered the job in its entirety; however, there are two states for the processed job for the scheduling of two parallel machines—processed by one machine or two machines. Therefore, we consider that one job can be split and processed on two machines if doing so can better achieve the optimum.

In practice, although the scheduling environment is a variable, there are certain situations in which the environment does not change. Centralized scheduling is a more efficient scheduling model and is suitable for a static scheduling environment. Hence, we build a new multi-agent scheduling mode and introduce two strategies. The first strategy is that a single distribution strategy will be applied to a dynamic scheduling environment, where only one category of job information is sent to the first available machine agent in SPT order when a machine agent has no job to process. Task agents submit one category of job, and the job is presorted with current processing jobs to two machine agents to achieve the goal of the job. The other strategy is that a centralized distribution strategy will be applied to a static scheduling environment where jobs remain unchanged during a given period. All job information is submitted and sent to a coordination agent. The coordination agent makes a scheduling plan, and machine agents process this scheduling plan as the plan. To ensure that the scheduling goals are met, we create three classes for all agents and define their function.

The remainder of the article is organized as follows. In the “Problem description” section, we discuss the background of the problem considered in this article. In the “Multi-agent system” section, we state the structure of a multi-agent system. In the “Resolution methods” section, a new model with two strategies is presented: a single distribution strategy applied to a dynamic scheduling environment and a centralized distribution strategy applied to a static scheduling environment. Finally, the conclusions of the article are presented in the “Conclusion” section.

Problem description

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

Each type of job can be processed by one machine or two machines when ${\mathrm{n}}_{\mathrm{i}}^{\mathrm{x}}$ is more than two. The objective of agent A is to minimize the total tardiness time $\sum {\mathrm{T}}^{\mathrm{A}}$ . The objective of agent B is to minimize the makespan ${\mathrm{C}}_{\max }^{\mathrm{B}}$ . Agents A and B complete their jobs as the objective, but they must compete for resources to maintain their benefits. The overall objective is to minimize both $\sum {\mathrm{T}}^{\mathrm{A}}$ and ${\mathrm{C}}_{\max }^{\mathrm{B}}$ . LF_i represents the time at which job i is completed, and D_i denotes due time of job i. T_i denotes the tardiness of job i.

1. The tardiness time function of task agent A is

$${\mathrm{T}}_{\mathrm{i}}=\{\begin{array}{c}\max \left\{0,\left({\mathrm{LF}}_{\mathrm{i}}^{\mathrm{y}}-{\mathrm{D}}_{\mathrm{i}}\right)\right\},\mathrm{y}=1\mathrm{or}2,\mathrm{one\; machine}\\ \max \left\{0,\left({\mathrm{LF}}_{\mathrm{i}}-{\mathrm{D}}_{\mathrm{i}}\right)\right\},L{F}_{\mathrm{i}}=\max ({\mathrm{LF}}_{\mathrm{i}}^1,{\mathrm{LF}}_{\mathrm{i}}^2),\mathrm{both}\end{array}$$

(1)

• 2. The total tardiness time function of agent A is

$${\displaystyle \sum {\mathrm{T}}^{\mathrm{A}}}={\displaystyle \sum {\mathrm{T}}_{\mathrm{i}}}$$

(2)

• 3. The overall objective function is

$$Z_{\mathrm{overall}}=\min \left({\displaystyle \sum {\mathrm{T}}^{\mathrm{A}}}+C_{\max }^{\mathrm{B}}\right)$$

(3)

Suppose that two machine agents (M1 and M2) belong to two identical parallel machines, each having the same function and processing speed for the same jobs. The machine agents know their own status and satisfy the job objectives as soon as possible. All agents, such as machine agents M1 and M2 and the task agents, can communicate with each other. Furthermore, the machine agents can make autonomous decisions based on their own status.

Multi-agent system

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

Architecture of multi-agent systems

Huang and Liao ⁴ developed three categories of agents—job agents, machine agents, and supervisor agents—in multi-agent systems to support the dynamic negotiation mechanism. However, our multi-agent system includes three types of agents who can contact each other by “dialogue” to achieve global and partial objectives for $\mathrm{P}2|\mathrm{Co}|\sum {\mathrm{T}}^{\mathrm{A}},{\mathrm{C}}_{\max }^{\mathrm{B}}$ . The model contains task agents A and B, machine agents M1 and M2, and the coordination agent. All jobs are assigned to two task agents. The objective of agent A is to minimize the total tardiness time. The objective of agent B is to minimize the makespan. There are two parallel machine agents, agents M1 and M2, to pursue meeting the task agents’ objectives as quickly as possible. The coordination agent plays an important role in the scheduling phase. This agent is a control center to maintain the regular scheduling activity. The multi-agent system is shown in Figure 1.

Figure 1.

Architecture of the multi-agent system: (a) multi-agent system, (b) subsystem 1, and (c) subsystem 2.

A multi-agent system can be categorized into two subsystems. One subsystem consists of task agents and machine agents. The other subsystem comprises all agents. In subsystem 1, all agents can contact each other and are utilized as a dynamic scheduling environment. In contrast, task agents cannot communicate with machine agents directly in subsystem 2. The coordination agent is not only a bridge for connecting task agents and machines agents but also a scheduling center for a static scheduling environment.

Agent priorities

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

Table 1.

Agent priorities.

Agents	Making-decision priority	Function
Coordination agent	First class	1. Accept the information from other agents 2. Develop the scheduling plan 3. Send command
Machine agents	Second class	1. Accept or reject the jobs if the coordination agent does not oppose it 2. Accept the demand from the coordination agent
Task agents	Third class	1. Accept the demand from the coordination agent 2. Rank the jobs in SPT order 3. Submit the jobs to the coordination agent or machine agents

SPT: shortest processing time.

Operation process

The operational process of the multi-agent system is shown in Figure 2. It has two subsystems: subsystem 1 and subsystem 2. We discuss their operation process as follows:

• 1. Operation process of subsystem 1

Figure 2.

Operation process of the system.

Subsystem 1 consists of two task agents and two machine agents, and it applies to a dynamic scheduling environment. The jobs of task agents vary frequently, which requires the production plan to be changed in real time to meet customers’ needs. Thus, we design subsystem 1, in which task agents send job information to machine agents one by one and machine agents allocate the jobs.

When task agents vary frequently, we rank all jobs in SPT order initially. If new job information is obtained by the task agents, they re-sort the remaining jobs in SPT order. Each task agent sends the first job information in SPT order to the machine agents each round when a machine agent is idle. If two machine agents are idle at the same time, the jobs are allocated to machine agent M1 first. The machine agent accepts the job information and develops a production plan. If the production plan of the machine agent can satisfy the requirement, the job is processed by the first idle machine agent. If a machine agent cannot satisfy the requirement or cannot do so optimally, the machine agents will develop a new production plan through consultation. The machine agents implement the production plan until the job is complete. When a machine agent is idle, it sends messages to task agents. Task agents will send new jobs to them. The scheduling is over when the task agents have no more jobs.

• 2. Operation process of subsystem 2

Compared with subsystem 1, subsystem 2 has a scheduling center, namely, the coordination agent. The coordination agent controls the remaining agents, similar to the human brain. Subsystem 2 can maintain a high efficiency due to the central scheduling mode and is applicable to static scheduling environments. Orders maintain stability, and machine agents remain healthy for a long period of time. In subsystem 2, task agents must submit all job information to the coordination agent, and machine agents send their status to the coordination agent. The coordination agent develops a central schedule according to a centralized distribution strategy and sends the plan to the machine agents. Machine agents must accept the command to process the jobs.

Resolution methods

There are two sub-problems to be solved in the $\mathrm{P}2|\mathrm{Co}|\sum {\mathrm{T}}^{\mathrm{A}},{\mathrm{C}}_{\max }^{\mathrm{B}}$ multi-agent system. First, for task agents, one must determine how to assign the job sequence. For machine agents, one must determine 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 SPT order to rank the jobs in sequence. For phase 2, we introduce a single distribution strategy to assign jobs to machine agents. For subsystem 2, all jobs are processed by centralized scheduling. We introduce a centralized distribution strategy for subsystem 2.

Single distribution strategy

Phase 1: the job sequence problem

We consider phase 1 from the task agent perspective. The SPT order is used to sort the jobs in sequence. All jobs are ranked based on their processing time from short to long. If some jobs have the same processing time, we rank them according to their due time from short to long.

Example 1

We consider that ${\mathrm{n}}_{\mathrm{A}}=3,{\mathrm{n}}_{\mathrm{B}}=3$ , and the job parameters are shown in Table 2.

Table 2.

Values of the task parameters.

${\mathrm{J}}_{\mathrm{i}}^{\mathrm{x}}$	${\mathrm{J}}_1^{\mathrm{A}}$	${\mathrm{J}}_2^{\mathrm{A}}$	${\mathrm{J}}_3^{\mathrm{A}}$	${\mathrm{J}}_1^{\mathrm{B}}$	${\mathrm{J}}_2^{\mathrm{B}}$	${\mathrm{J}}_3^{\mathrm{B}}$
${\mathrm{n}}_{\mathrm{i}}^{\mathrm{x}}$	2	4	3	3	2	1
${\mathrm{P}}_{\mathrm{i}}^{\mathrm{x}}$	1	1	2	1	2	3
${\mathrm{n}}_{\mathrm{i}}^{\mathrm{x}}\times {\mathrm{P}}_{\mathrm{i}}^{\mathrm{x}}$	2	4	6	3	4	3
${\mathrm{D}}_{\mathrm{i}}^{\mathrm{x}}$	5	5	6	4	7	8

Therefore, all job sequences for the task agents are ${\mathrm{\Gamma }=\{\mathrm{J}}_1^{\mathrm{A}}{,\mathrm{J}}_1^B{,\mathrm{J}}_3^{\mathrm{B}}{,\mathrm{J}}_2^A{,\mathrm{J}}_2^{\mathrm{B}}{,\mathrm{J}}_3^A\}$ as ${\mathrm{n}}_{\mathrm{i}}^{\mathrm{x}}\times {\mathrm{P}}_{\mathrm{i}}^{\mathrm{x}}$ from small to large. The job sequence for task agent A is ${\Gamma }^{\mathrm{A}}=\{{\mathrm{J}}_1^{\mathrm{A}},{\mathrm{J}}_2^{\mathrm{A}},{\mathrm{J}}_3^{\mathrm{A}}\}$ , and the job sequence for task agent B is ${\Gamma }^{\mathrm{B}}=\{{\mathrm{J}}_1^{\mathrm{B}},{\mathrm{J}}_3^{\mathrm{B}},{\mathrm{J}}_2^{\mathrm{B}}\}$ .

Phase 2: assign the jobs to machine agents

A single distribution strategy is mainly applied to dynamic scheduling. From machine agents’ perspectives, the task agents submit information for one type of job in SPT order to the machine agents each round when a machine agent requires it. The first available machine agent selects the job. The objective of the job must remain at the optimum. Therefore, we research all scenarios of one type of job when the job is processed. Assume that machine agent M1 is available first. We partition this situation into two types: when job i from agent A is submitted and when job j from agent B is submitted. We discuss the two situations as follows:

• 1. Job i from agent A is submitted

Assuming that job i will be assigned to the first available machine agent, M1, when it has no job at time ${\mathrm{C}}_0$ . Machine agent M2 is processing its jobs in current time. We analyze the job status of the machine agents at this time. The jobs from agent A have the objective of minimizing the total tardiness time. We consider splitting the job and presort job i if it can be split. There are six possible types of situations (Figure 3).

Figure 3.

Situations for the presorting of job i: (a) The completion time of the remaining job of machine agent M2 is greater than that of job i, and job i can be completed on time. Hence, job i is processed according to the original plan and is not tardy. (b) The completion time of the remaining job of machine agent M2 is greater than that of job i, but it is not completed on time. However, job i cannot be modified and processed according to the original plan. Its tardiness time is (C1 – Di). (c) The completion time of the remaining job of machine agent M2 is equal to that of job i, and job i can be completed on time. Hence, job i is processed according to the original plan and is not tardy. (d) The completion time of the remaining job of machine agent M2 is equal to that of job i, but job i cannot be completed on time. Job i cannot be modified and is processed according to the original plan. Its tardiness time is (C1 – Di). (e) The completion time of the remaining job of machine agent M2 is smaller than that of job i and job i can be completed on time. Hence, job i is processed according to the original plan and is not tardy. (f) The completion time of the remaining job of machine agent M2 is smaller than that of job i, but job i cannot be completed on time. If ${\mathrm{C}}_1-{\mathrm{C}}_2<2P_{\mathrm{i}}$ (see scenario f1 in Figure 3), job i cannot be modified and is processed according to the original plan. Its tardiness time is (C1 – Di). If ${\mathrm{C}}_1-{\mathrm{C}}_2\ge 2{\mathrm{P}}_{\mathrm{i}}$ (see scenarios f2 and f3 in Figure 3), 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 below.

According to Algorithm 1, first, we assess whether job i can be split. Second, if it can be split, we assess the extent to which the job can be split. If the due time of job i can be met by splitting the job, the job is not tardy (sentence 13 in Algorithm 1). If the due time of job i cannot be met by splitting the job, job i is split to attain the optimum and its tardiness time is $[{\mathrm{C}}_0+({\mathrm{n}}_{\mathrm{i}}-\lfloor q\rfloor ){\mathrm{P}}_{\mathrm{i}}-{\mathrm{D}}_{\mathrm{i}}]$ (sentence 17 in Algorithm 1). If job i cannot be split, its tardiness time is $({\mathrm{C}}_0+{\mathrm{n}}_{\mathrm{i}}{\mathrm{P}}_{\mathrm{i}}-{\mathrm{D}}_{\mathrm{i}})$ (sentence 20 in Algorithm 1).

• 2. Job j from agent B is submitted

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

Assume that machine agent M1 is the first available machine agent. Job j from agent B is the candidate for the next job of M1. Job j is submitted to M1. The objective of jobs from agent B is to minimize the makespan. We consider splitting job j and presort job j if it can be split to achieve the current objective of job j (Figure 4). There are three possible types of situations.

Figure 4.

Situations of presorting job j: (a) the completion time of the remaining job of machine agent M2 is greater than that of job j, and job j can be completed before completing the jobs of M2. Hence, job j is processed according to the original plan. Its makespan is C₁. (b) The completion time of the remaining job of machine agent M2 is equal to that of job j. Job j can be completed in the same amount of time as the remaining job of M2. Hence, job j is processed according to the original plan. Its makespan is C₁. (c) The completion time of the remaining job of machine agent M2 is smaller than that of job j. If ${\mathrm{C}}_1-{\mathrm{C}}_2<2{\mathrm{P}}_{\mathrm{j}}$ (see scenario c1 in Figure 4), job j cannot be modified and is processed according to the original plan. Its makespan is C₁. If ${\mathrm{C}}_1-{\mathrm{C}}_2\ge 2{\mathrm{P}}_{\mathrm{j}}$ (see scenario c2 in Figure 4), job j can be split and processed by two machine agents.

The algorithm is shown below.

According to Algorithm 2, first, we assess whether job j can be split. Second, if it can be split, we assess the extent to which the job can be split. Job j is split to attain the optimum; its makespan is $({\mathrm{C}}_0+{\mathrm{n}}_{\mathrm{j}}{\mathrm{P}}_{\mathrm{j}})$ (sentence 10 in Algorithm 2). If the job cannot be split, its makespan is C₁ (sentence 12 in Algorithm 2).

• 3. The single distribution strategy is explained as follows:

• Step 1. All jobs of the task agents are sequenced in SPT order.

• Step 2. Task agents submit one type of job in SPT order each round to the first available machine agent.

• Step 3. Assess whether the objective of each processing job of the machine agents achieves the optimum in the current sequence. If the objective of each job achieves the optimum, go to step 4. Otherwise, go to step 5.

• Step 4. If the machine agents process the jobs, go to step 6.

• Step 5. If the job comes from agent A and can be split, the job is split according to Algorithm 1. If the job comes from agent B and the job is split according to Algorithm 2, go to step 4.

• Step 6. If new jobs are received by the task agents before the machine agents are idle again, job sequence is updated. If not, go to step 7.

• Step 7. If task agents have jobs, go to step 2. If not, the scheduling is complete.

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

Property 1

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

Example 2

Suppose that ${\mathrm{n}}_{\mathrm{A}}=3,{\mathrm{n}}_{\mathrm{B}}=3$ , and the job parameters are shown in Table 2 from Example 1. We use the single distribution strategy and SPT strategy to solve $\mathrm{P}2|\mathrm{Co}|\sum {\mathrm{T}}^{\mathrm{A}},{\mathrm{C}}_{\max }^{\mathrm{B}}$ (Table 3). The results are shown in Figure 5.

Table 3.

Objective values of SPT strategy and single distribution strategy.

Method	${\mathrm{T}}_1^{\mathrm{A}}$	${\mathrm{T}}_2^{\mathrm{A}}$	${\mathrm{T}}_3^{\mathrm{A}}$	$\sum \mathrm{T}$	${\mathrm{C}}_{\max }$	${\mathrm{Z}}_{\mathrm{overall}}$
SPT strategy	0	2	7	9	9	18
Single distribution strategy	0	1	6	7	8	15

SPT: shortest processing time.

Figure 5.

Gantt chart of the (a) SPT strategy and (b) single distribution strategy.

In the SPT strategy, the total tardiness time of agent A is 9 and the makespan of agent B is 9. For the single distribution strategy, the total tardiness time of agent A is 7 and the makespan of agent B is 8. The overall objective value of the single distribution strategy is 15, whereas that of the SPT order is 18. Therefore, the single distribution strategy, in which the jobs can be split, outperforms the SPT order.

Centralized distribution strategy for subsystem 2

In contrast to the single distribution strategy, the centralized distribution strategy can be applied to static scheduling. Task agents submit all jobs to the coordination agent, and the machine agents submit their status to the coordination agent. The coordination agent considers the centralized optimum, assigning all jobs to machine agents. We introduce a hybrid strategy based on the longest processing time (LPT) order, SPT order, and the jobs to be processed by one machine agent or two machine agents. The coordination agent develops a production scheme and sends it to the machine agents, and the machine agents accept the command and process jobs.

According to Algorithm 3, first, we arrange all jobs in LPT order and assume that all jobs are assigned in LPT order to the machine agents. Second, the jobs are reassigned in SPT order for each machine agent. If some jobs have the same processing time in LPT order and SPT order, we rank them by due time from small to large. Third, we execute Algorithm 4 to minimize the total tardiness time except for the final processing jobs for both machine agents. Fourth, we execute Algorithm 5 to minimize the makespan for the job from agent B. Finally, we adjust the final processing jobs of the two machine agents to minimize their completion time gap.

Algorithm 3. Centralized distribution strategy for subsystem 2.

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

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

The centralized distribution strategy is as follows:

• Step 1. Arrange all jobs in LPT order.

• Step 2. Assign all jobs in LPT order to the machine agents.

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

• Step 4. Select all tardiness jobs from agent A except for the final processing jobs from both machine agents as set ${\mathrm{V}}^{\mathrm{A}}$ .

• Step 5. If the job from set ${\mathrm{V}}^{\mathrm{A}}$ has tardiness, select the earliest tardiness job k and determine whether it can be split. If the job from set ${\mathrm{V}}^{\mathrm{A}}$ has no tardiness or cannot be split, go to step 7 (see Algorithm 4).

• Step 6. If the job k can be split, select job h from agent A allocated by the other machine agent whose completion time is less than that of job k but is the closest to job k. Job k is split, and the part of job k partitioned into the other machine agent is added behind job h until the tardiness time of job k is minimized. Then, job k is moved out of set ${\mathrm{V}}^{\mathrm{A}}$ , and we return to step 5. The process is complete when set ${\mathrm{V}}^{\mathrm{A}}$ has no job. Go to step 7 (see Algorithm 4).

• Step 7. If the completion time of job i is the largest completion time for agent B, it selects the job i and determine whether it can be split. If the job cannot be split, go to step 9 (see Algorithm 5).

• Step 8. If job i can be split, the algorithm selects job j in the other machine agent from agent B whose completion time is less than job i but is the largest completion time from agent B. Job i is split, and the part of job i partitioned into the other machine agent is added behind job j but is adjacent to job j until the makespan is minimized. Go step 9 (see Algorithm 5).

• Step 9. Adjust the final processing jobs of the two machine agents to minimize their completion time gap. The scheduling is complete.

Example 3

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

Figure 6.

Gantt chart of the centralized distribution strategy.

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

Table 4.

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

Method	${\mathrm{T}}_1^{\mathrm{A}}$	${\mathrm{T}}_2^{\mathrm{A}}$	${\mathrm{T}}_3^{\mathrm{A}}$	$\sum \mathrm{T}$	${\mathrm{C}}_{\max }$	${\mathrm{Z}}_{\mathrm{overall}}$
SPT strategy	0	2	7	9	9	18
Single distribution strategy	0	1	6	7	8	15
Centralized distribution strategy	0	0	5	5	9	14

SPT: shortest processing time.

Conclusion

In this article, we consider a multi-agent scheduling problem of two identical parallel machines. We study $\mathrm{P}2|\mathrm{Co}|\sum {\mathrm{T}}^{\mathrm{A}},{\mathrm{C}}_{\max }^{\mathrm{B}}$ and design a multi-agent system that can be applied to dynamic and static environments flexibly and is suitable for a discrete and small-sized production problem. The multi-agent system is divided into two subsystems. In subsystem 1, the scheduling problem is divided into two phases. For the job sequence phase, we sort all jobs in SPT order to solve the job sequences. To assign the jobs to machines, we consider one type of job processed by one machine only or two machines and provide a single distribution strategy, where the job is processed by the first available machine agent and jobs can be split and assigned to two machine agents. In subsystem 2, task agents submit information on all jobs, and machine agents submit their status to the coordination agent. The coordination agent makes a centralized schedule based on a centralized distribution strategy used LPT order to SPT order and the jobs to be processed by one machine agent or two machine agents. The two strategies are more flexible and efficient than the SPT strategy.

In the future, we will consider three scenarios: first, we will consider strategies to achieve the optimal scheduling when machine agents do not select allocations from each other and compete with each other; second, we suppose that all jobs’ information is known in advance and investigate the situation in which machine agents do not know the job information before starting work or know a part of the information; and third, we will consider how to allocate the jobs to machine agents when considering the setup time. We will improve the single distribution strategy and centralized distribution strategy to meet customers’ needs.