A two-agent production and transportation coordinated scheduling problem in a single-machine environment is suggested to compete for one machine from different downstream production links or various consumers. The jobs of two agents compete for the processing position on a machine, and after the processed, they compete for the transport position on a transport vehicle to be transported to two agents. The two agents have different objective functions. The objective function of the first agent is the sum of the makespan and the total transportation time, whereas the objective function of the second agent is the sum of the total completion time and the total transportation time. Given the competition between two agents for machine resources and transportation resources, a non-cooperative game model with agents as game players is established. The job processing position and transportation position corresponding to the two agents are mapped as strategies, and the corresponding objective function is the utility function. To solve the game model, an approximate Nash equilibrium solution algorithm based on an improved genetic algorithm (NE-IGA) is proposed. The genetic operation based on processing sequence and transportation sequence, as well as the fitness function based on Nash equilibrium definition, are designed based on the features of the two-agent production and transportation coordination scheduling problem. The effectiveness of the proposed algorithm is demonstrated through numerical experiments of various sizes. When compared to heuristic rules such as the Longest Processing Time first (LPT) and the Shortest Processing Time first (SPT), the objective function values of the two agents are reduced by 4.3% and 2.6% on average.
In modern manufacturing models, various production connections inside a business or distinct clients outside a firm will have different personalized wants and compete for production resources. At this time, cooperative planning and decision-making among different decision makers must be considered [
Examples involving two-agent production and transportation may be found in the steel plant manufacturing process. As one practical example, the steelmaking-continuous casting processes in the steel plant demonstrate the real production settings. The manufacturing process is depicted in
The majority of research on multi-agent scheduling has been on a single machine. Baker et al. [
There is less research on multi-agent scheduling issues that address transportation and processing cooperatively. Fan et al. [
In summary, the multi-agent scheduling problem is mostly studied as a two-agent scheduling problem under a single machine, with less consideration of the collaboration between processing and transportation. Most of the solution methods transform the multi-objective problem into a single-objective problem and solve the small-scale problem by an exact algorithm, ignoring the competitive relationship between two agents.
Mathematical programming approaches, meta-heuristic algorithms, intelligent optimization algorithms, and other methods are commonly adopted to solve the production scheduling problem [
It can be seen that more scholars have studied production scheduling problems based on non-cooperative games, although game theory is rarely applied to analyze multi-agent scheduling problems. As a result, non-cooperative game theory is used to investigate the two-agent production and transportation coordinated scheduling problem by taking into account the competition between the jobs of two agents for the processing sequence and transportation sequence from the standpoint of maximizing the payoff of agents.
This paper carries out the following three works listed below. Two different production links or customers are regarded as agents in view of the competition for the same machine resources between the jobs from different production links or customers. After the job has been processed, it needs to be delivery to the respective agent, and the two agents have distinct objectives. Considering production and post-production transportation cooperatively, a scheduling problem of two-agent production and transportation coordination in a single machine is suggested. A non-cooperative game model for the competition relationship between the jobs of two agents for the machine and the transport vehicle is constructed. The two agents are mapped as players, and the two agents compete for the processing position on the machine and the transportation position on the transport vehicle. The processing position and transportation position of the jobs are mapped as strategies, and the objective function of the two agents is mapped as payoff functions. An approximate Nash equilibrium solution algorithm based on an improved genetic algorithm (NE-IGA) is proposed to solve the approximate Nash equilibrium solution of the problem. The fitness function is designed from the Nash equilibrium definition, and the genetic operator based on production and transportation is designed according to the characteristics of the two-agent production and transportation coordination scheduling problem in single-machine.
This paper is outlined as follows: Section 2 develops a non-cooperative game model to handle the problem of two-agent production transportation coordination scheduling in single machine. Section 3 designs an approximate Nash equilibrium solution method based on an improved genetic algorithm. Section 4 describes the experiment setting and the results of the experiment. Finally, Section 5 summarizes the conclusions.
The jobs of two agents compete to be processed on a single machine and transported to their respective agents after completion, i.e., the jobs of two agents compete to get the order of processing on the machine and transport on the transport vehicle.
Let there be two agents: agent
Set of indices | |
---|---|
Set of jobs, |
|
Agent, |
|
Set of jobs for agent |
|
Set of jobs for agent |
|
Parameters | |
The processing time of the |
|
The time for the transport vehicle to travel between machine and agent |
|
Variables | |
The completion time of |
|
The finish time of the transport vehicle transporting the |
|
The waiting time for the transport vehicle to transport |
|
The optimization objective of agent |
|
The optimization objective of agent |
Assume that the following assumptions are satisfied to simplify the problem. The single machine can process continuously without the requirement for setup or switching time. All jobs have arrived at the initial time and are ready to be processed. The transport vehicle has a capacity restriction, and only one job can be loaded onto the transport vehicle at a time.
Considering that there is a competitive relationship between the two agents, each agent needs to maximize its own utility. The objective of agent
where
According to the extended three-domain representation
In a non-cooperative game model, multiple players choose their strategies based on their own interests, and there is both conflict and cooperation between players, which conforms to the competition and cooperation between two agents for resources in the two-agent scheduling problem. As a result, we adopt non-cooperative game theory to address the problem of two-agent production and transportation scheduling in a single machine.
In a single machine setting, a non-cooperative game model for the two-agent production and transportation coordinated scheduling problem is established. The model can be formulated as
where
Not all strategies are valid. Strategy Sequences of processing conflict: Because the two players only consider their own strategies, there will be two jobs processed at the same position, rendering the strategy invalid. In other words, for any two different jobs Sequences of transport conflict: When two jobs are transported at the same position, the strategy is invalid. In other words, or any two different jobs
For example, the job sets of agent
For example, the job sets of agent
Agent |
Agent |
||
---|---|---|---|
1 | 2 | 3 | |
0.5 | 1.5 | 1.8 | |
1.2 | 1.2 | 1.9 |
According to the non-cooperative game model built for the two-agent production and transportation coordination scheduling problem, there are 36 alternative strategies for agent
The strategy space of the game model grows exponentially as the number of jobs of two agents increases, and the genetic algorithm can undertake a speedy search for the best solution without the limitation of scale change. Therefore, an approximate Nash equilibrium solution algorithm based on an improved genetic algorithm (NE-IGA) has been developed to seek the approximate Nash equilibrium of the provided game model.
According to the action strategy in the game model, integer coding is applied, and each job needs to choose a processing position and a transportation position, so each chromosome is divided into two sections, as shown in
For example, there are 5 jobs with chromosome codes (3, 4, 1, 2, 5, 2, 5, 1, 3, 4), which implies that the processing sequence of the jobs is 3, 4, 1, 2, 5, namely
The design of the fitness function is critical to resolving the Nash equilibrium. The objective of the two-agent production and transportation coordination scheduling problem is to minimize the objective functions of agents A and B. According to the definition of Nash equilibrium in the non-cooperative game model, when the Nash equilibrium is reached, it is difficult for the players to improve their own payoffs by modifying their own strategies, and the payoffs of the two agents are close enough to the best payoffs of the previous generation. As a result, the Nash equilibrium is determined by the difference between individual payoffs in the current generation and the best individual payoff in the previous generation. Second, the genetic algorithm calculates the likelihood of individual inheritance to the next generation based on the proportion of individual fitness, which must be positive. The fitness function is defined as
where
According to the definition of the Nash equilibrium of the non-cooperative game model, the smaller the fitness value, the better. Defining
The roulette selection operator is applied, and the likelihood of each chromosome joining the next generation is equal to the ratio of its fitness value to the total fitness values of the whole population. Then, according to the single lottery logic, chromosomes are chosen based on the random number’s area.
The fitness is divided into
Paternal chromosomes
Chromosome
Crossover or mutation operations are decided based on the similarity between parental chromosomes in order to improve population diversity and avoid slipping into a local optimum. The similarity between chromosomes
The optimal individual retention strategy is adopted by NE-IGA to safeguard the best individuals in each generation of the population from being eliminated during subsequent selection, crossover, or mutation. This is accomplished by replacing the one with the largest value of the fitness function calculated in the offspring generation with the one with the smallest value of the fitness function in the parent generation.
The following are the steps of NE-IGA for solving the two-agent production and transportation coordination scheduling problem. And
Step1: Parameter settings: population size
Step2: Initialize the population and set g = 1.
Step3: The fitness value
Step4: Update the population. Two chromosomes
Step5: Retain the best individuals. Calculate the fitness value of the current population using
Step6: If
Step7: Determine whether the maximum number of iterations has been reached, i.e., whether
The following numerical example is created for simulation and analysis in order to validate the effectiveness of the proposed algorithm. The experiments are carried out on an Intel(R) Core(TM) i5-7200U CPU 2.50 GHz 2.71 GHz processor, 8 GB RAM, and Unity 2017 software.
Take
Serial number | Average value | ||||
---|---|---|---|---|---|
1 | 50 | 0.7 | 0.5 | 0.01 | 139.75 |
2 | 50 | 0.8 | 0.6 | 0.05 | 132.09 |
3 | 50 | 0.9 | 0.7 | 0.1 | 133.01 |
4 | 100 | 0.7 | 0.5 | 0.01 | 129.03 |
5 | 100 | 0.8 | 0.6 | 0.05 | |
6 | 100 | 0.9 | 0.7 | 0.1 | 130.01 |
7 | 200 | 0.7 | 0.5 | 0.01 | 129.21 |
8 | 200 | 0.8 | 0.6 | 0.05 | 133.70 |
9 | 200 | 0.9 | 0.7 | 0.1 | 140.47 |
It can be seen from
Iterations | Scheduling plan | Payoff | |
---|---|---|---|
Agent |
Agent |
||
1 | ( |
98.50 | 280.80 |
100 | ( |
95.70 | 264.00 |
400 | ( |
To further validate the efficacy of the proposed algorithm, a comparison analysis is done at various experimental sizes, utilizing the Longest Processing Time first (LPT) and the Shortest Processing Time first (SPT).
Algorithm | Payoff | Average value | |
---|---|---|---|
Agent |
Agent |
||
LPT | 96.20 | 301.10 | 198.65 |
SPT | 95.70 | 178.00 | 136.85 |
NE-IGA |
Algorithm | Payoff | Average value | |
---|---|---|---|
Agent |
Agent |
||
LPT | 244.70 | 1500.80 | 872.75 |
SPT | 259.80 | 408.80 | |
NE-IGA | 559.0 |
It can be seen that the objective functions of the two agents under the NE-IGA algorithm can converge to the optimum at the same time under different experimental scales, and a solution closer to the Nash equilibrium is obtained.
In this paper, we investigate the problem of coordinated production and transportation scheduling for two agents in a single machine. The jobs of two agents compete to be processed on a single machine and delivered to their respective agents after completion, and there is also competition for the transport vehicle. The objective of agent
This paper assumes that the transport vehicle can only transport one job at a time and does not consider batch transport. Furthermore, the job may need to be delivered to the matching agent for the next processing within a limited time after the current machine processing is completed, which is known as the transportation waiting constraint. Therefore, the problem of two-agent production and transportation coordination scheduling considering transportation batch and transportation waiting time constraints can be further investigated in a single machine environment in the future. Furthermore, the development of new efficient algorithms is a potential research topic for the problem of two-agent production and transportation coordination.
The authors wish to acknowledge the contribution of Liaoning Key Lab of Equipment Manufacturing Engineering Management, Liaoning Research Base of Equipment Manufacturing Development, Liaoning Key Research Base of Humanities and Social Sciences: Research Center of Micro-management Theory of SUT.
This work was supported in part by the
The authors declare that they have no conflicts of interest to report regarding the present study.