[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Next Article in Journal
Optimization of Interconnected Natural Gas and Power Systems Using Mathematical Programs with Complementarity Constraints
Previous Article in Journal
Research on Risk-Averse Procurement Optimization of Emergency Supplies for Mine Thermodynamic Disasters
You seem to have javascript disabled. Please note that many of the page functionalities won't work as expected without javascript enabled.
 
 
Search for Articles:
Title / Keyword
Author / Affiliation / Email
Journal
Article Type
 
 
Advanced Search
 
Section
Special Issue
Volume
Issue
Number
Page
 
Journals
Mathematics
Volume 12
Issue 14
10.3390/math12142223
mathematics-logo
Submit to this Journal Review for this Journal Propose a Special Issue
► Article Menu

Article Menu

share Share announcement Help format_quote Cite question_answer Discuss in SciProfiles thumb_up
...
Endorse textsms
...
Comment
first_page
settings
Order Article Reprints
Font Type:
Arial Georgia Verdana
Font Size:
Aa Aa Aa
Line Spacing:
Column Width:
Background:
Article

Bounding the Price of Anarchy of Weighted Shortest Processing Time Policy on Uniform Parallel Machines

by
Felipe T. Muñoz
* and
Rodrigo Linfati
Departamento de Ingeniería Industrial, Facultad de Ingeniería, Universidad del Bío-Bío, Concepción 4030000, Chile
*
Author to whom correspondence should be addressed.
Mathematics 2024, 12(14), 2223; https://doi.org/10.3390/math12142223
Submission received: 17 June 2024 / Revised: 10 July 2024 / Accepted: 13 July 2024 / Published: 16 July 2024
Versions Notes

Abstract

:
This article investigates the performance of the Weighted Shortest Processing Time (WSPT) rule as a local sequencing policy in a scheduling game for uniformly related parallel machines, where the social objective is the total weighted completion time. Our research aims to establish improved upper bounds for the price of anarchy in this game. We determine two bounds, incorporating parameters that characterize the instance family, such as the speed of the fastest machine ( s m ) and the number of machines (m). One bound establishes a fixed upper bound for the price of anarchy, while the other outperforms the parametric upper bound found in the existing literature. These newly derived bounds provide better insights into the performance of the scheduling game under study, proving that the price of anarchy is upper bounded by min s m 1 + 1 / 2 s m − 1 / 2 m , m , 4 .

1. Introduction

Job scheduling problems are recurring in several fields, including industrial production, project management, and logistics. The efficient allocation of resources and time optimization are critical factors for ensuring the optimal performance of complex systems. In this context, game theory emerges as an innovative approach to comprehending the dynamics of decision-making processes, offering insights that can significantly enhance real-time decision-making efficiency. The scheduling problems viewed from the game theory perspective are known as scheduling games. We recommend referring to Heydenreich et al. [1] for a more in-depth introduction to scheduling games. This article provides a comprehensive overview of this field of research, addressing key concepts.
The scheduling game approach has applications across diverse problem domains, particularly in computing and networks. Notable examples include load balancing in computational grids [2] and traffic routing in networks [3,4,5,6,7,8]. Additionally, this approach has been applied for modeling traffic flows and route choices in transport networks [9,10,11]; it has also been used to support decision-making for subcontracting production orders [12] among other applications.

1.1. Scheduling Game Description

This study considers the scheduling game in an environment of uniformly related parallel machines. In this environment, each machine operates at a different speed. Unlike the classic scheduling problem, where a single decision maker (central authority) must decide the allocation and sequence of jobs, each job now belongs to an agent who decides which machine will process its job. In this decentralized decision approach, each job (as an agent) makes a decision that maximizes its own utility (or minimizes its disutility) without regard to the performance of some central or social objective. Depending on the utility of the jobs, a distinction can be made between two models [1,13]: the congestion model (load balancing) and the sequencing model (scheduling).
In a congestion model [14], each job receives a utility indirectly related to the workload of the selected machine, that is, the total processing time related to all jobs assigned to the same machine. At the same time, the social objective is to minimize the makespan of the overall schedule. Note that the makespan is a minimax social choice objective. Some relevant works related to this model are presented in [5,14,15,16,17,18,19,20,21,22,23,24,25,26].
In the sequencing model, each job receives a utility indirectly related to its own completion time. In a decentralized way, each job selects a machine, trying to minimize its completion time. At the same time, the social objective is to minimize the total completion time (weighted or unweighted). Note that this objective is a minsum social choice objective. Then, to determine the sequence of jobs to be processed, each machine announces its local sequencing policies in advance, known as local policy or coordination mechanism [22]. If the policy depends solely on the processing requirements of the jobs assigned to the same machine, it is a strongly local policy rule.
Regarding the choice of jobs, their strategies can be considered in two ways: pure and mixed. A pure strategy implies that an agent must select a single machine. In contrast, a mixed strategy implies that the agent can choose multiple strategies over pure strategies, like a probability distribution.
The two most commonly used local policies for pure strategies in a minsum social choice objective are the Shortest Processing Time (SPT) rule, which sequences jobs in increasing order of their processing time, and the Weighted Shortest Processing Time (WSPT) rule, which sequences jobs in descending order of their weight-to-processing time ratio ( w j / p j ). Some relevant works related to the sequencing model are presented in [12,13,27,28,29,30,31,32,33,34,35,36,37]. Some of these works present results for other local policies [1,27,29,31,32,35,38]. On the other hand, for congestion games, the performance of SPT rules, such as local policy, has also been studied [21,25,26,39,40,41].
One of the fundamental aspects of decentralized decision-making involves achieving convergence to an equilibrium, commonly referred to as the Nash equilibrium. This equilibrium represents a state where no player is incentivized to change their strategy unilaterally. While Nash equilibria may not always be attainable for pure strategies, they are guaranteed to exist for mixed strategies. Studies such as [1,16,25,38] demonstrate that employing the WSPT or SPT rule as the local policy for pure strategies ensures convergence to a Nash equilibrium.
In general, the value of the social objective for some Nash equilibrium can be worse than that of the social objective for the optimal schedule (social optimum) obtained through centralized decision-making. This inefficiency of the game is quantified with the Price of Anarchy (PoA) proposed by Koutsoupias and Papadimitriou [14]. Given a game, the PoA for a game instance is the worst-case ratio of the social cost at a Nash equilibrium to the cost at the social optimum. The PoA for a game is the worst-case value of the PoA overall game instances.
According to the classification scheme proposed by [35], a scheduling game can be described by the three-field notation α | β | γ . The α field describes the machine environment and the local sequencing policy used by each machine (in parentheses), the β field contains entries relating to the job specifications and also indicates the egoistic utility ( u t ) criterion of the jobs, and the γ field indicates the social objective. Therefore, the problem considered in this study is represented by Q ( W S P T ) | u t = − C j | ∑ w j C j . Meanwhile, the centralized problem, represented by Q | | ∑ w j C j in the scheduling notation [42,43], is a well-known NP-Hard problem.

1.2. Related Works

Table 1 presents the PoA for scheduling games in parallel machine environments that use the WSPT (or SPT) rule as the local sequencing policy, where the social objective is to minimize the total completion time, whether weighted or unweighted. In cases where a single value is provided, the PoA has already been proven to be tight. For instances where a range or inequality is given, these values represent the lower and upper bounds for the PoA. Note that this highlights a research opportunity to establish a tight PoA for the game or narrow the gap between the upper and lower bounds.
For the studied problem, Muñoz and Parra [45] establish that the PoA is at least two and propose the following parametric upper bounds:
s 2 s 1 + 1 4 , for m = 2 ,
3 2 1 − 1 m s m s 1 + 1 m , for m > 2 .
For the unweighted case of the studied problem, the literature establishes that the PoA ranges from 1.582 to 2 (see Table 1 for more details) [34,37]. Meanwhile, for the particular case of m = 2 machines, the PoA ranges from 1.1875 to 1.618 [35,37].
On the other hand, in [32,33], the PoA is examined for two generalizations related to the studied problem. In [32], the scheduling game on unrelated machines is analyzed, while [33] explores the scheduling game on uniformly related machines with the additional consideration of machine eligibility restrictions. These restrictions establish that each job j can be processed by a subset M j of machines. Both studies demonstrate that the PoA of their respective problems is strictly 4.
According to the literature related to the study of the PoA in sequencing games [25,32,33,34,35,37,45], the typical methodology involves two stages: establishing lower bounds and upper bounds for the PoA. Upper bounds indicate the potential worst-case social performance, while lower bounds highlight instances where the Nash equilibrium demonstrates poor social performance. When upper and lower bounds coincide, a tight PoA is established, concluding the analysis for that sequencing game and the specific local policy. The establishment of upper bounds involves characterizing schedules, determining properties of the social optimum and the Nash equilibrium, bounding the total weighted completion time of these schedules, and establishing relationships among these values. This is typically achieved through the use of inequalities. To establish lower bounds, the usual method is to design problem instances that demonstrate the worst-case performance for PoA. Often, trial-and-error studies are necessary to achieve this objective. According to the literature, problem instances to illustrate worst-case scenarios can be classified into small, parametric, and large (asymptotic) instances.
A problem closely related to the problem discussed corresponds to assignment-sequencing models for multi-agent scheduling, also referred to as the Pareto-scheduling problem, e.g., in [46,47,48,49,50,51,52]. In this context, a finite set of customers (or agents) each possess a set of jobs. These jobs must be processed on parallel machines. Each customer has an objective function for their jobs, and manufacturers aim to find the best scheduling scheme considering the trade-off between the objectives. Another related work involves the fair allocation of divisible and indivisible chores, which can be seen as a scheduling problem on unrelated parallel machines. For example, in [53], the price of fairness with utilitarian diswelfare is studied.

1.3. Our Study

This study investigates the worst-case performance for the WSPT rule as the local sequencing policy for the Q ( W S P T ) | u t = − C j | ∑ w j C j problem. Specifically, our objective is to establish an improved parametric upper bound for the PoA.
Our proof technique follows a similar approach to that used in [45], establishing a mathematical expression for the Nash equilibrium condition. Subsequently, we establish specific properties of the solutions to the problem, the Nash equilibria, and the social optimum. The main difference from the approach in [45] lies in determining the lower bound for the social optimum. While [45] derives a lower bound based on the inequality proposed by Eastman et al. [54] for a related problem, we employ a lower bound proved in [55] for the centralized decision problem, Q | | ∑ w j C j . This allows us to establish a tighter parametric upper bound for the studied problem.
Our main result establishes that the PoA for any pure Nash equilibrium in the Q ( W S P T ) | u t = − C j | ∑ w j C j problem, where ∑ i ∈ M s i = m , is at most
min s m 1 + 1 2 s m − 1 2 m , m , 4 .
This implies an improved bound for the PoA compared to the parametric upper bounds proved in [45].
The remainder of this article is structured as follows. Section 2 formalizes the scheduling game under investigation and explains the notation utilized throughout this study. This section also includes an analysis of the properties of optimal (social) solutions and pure Nash equilibria. Section 3 is dedicated to studying the price of anarchy. In Section 4, we discuss our findings. Finally, we summarize the main conclusions of this study in Section 5.

2. Problem Statement and Notation

The scheduling game addressed in this study is set in an environment with m uniformly related parallel machines, where the local policy assumed by each machine is the WSPT rule, which is known to allow a set of jobs to be optimally sequenced on a single machine [56] (Thm. 3). Each machine may have a different speed in this setting and can process one job at a time without interruption. Let M represent the set of machines and s i the processing speed of machine i ∈ M . Without loss of generality, we assume that the machines are indexed in increasing order based on their speed,
s 1 ≤ s 2 ≤ ⋯ ≤ s m ,
and we rescale the machine speeds such that
∑ i ∈ M s i = m .
Let J be the set of n jobs (agents) that must choose a single machine to perform their processing. Each job j ∈ J has a processing requirement p j ≥ 0 and a weight or relative importance w j ≥ 0 . Let v be the vector representing the choices made by all the jobs. This vector, combined with the local policy, defines the schedule that will be implemented to process the entire set of jobs. In this vector, v j indicates the machine chosen by job j. More precisely, v j = i indicates that in the schedule v , job j selected the machine i. Then, its processing time will be p j / s i . Additionally, we define J i ( v ) ⊆ J as the set of jobs that chose machine i as their strategy.
Regarding the local job-sequencing policy, the WSPT rule determines that the jobs must be sequenced according to the w j / p j ratios in descending order. In the remainder of the article, we will use the notation ≺ and ≻ to represent the sequence induced by the WSPT rule, considering that ties in the ratio are broken arbitrarily. We will also use the notation ⪯ and ⪰ to represent preceding and succeeding jobs, including the job itself.
For a schedule v , where v j = i , the completion time of job j is determined as:
C j ( v ) = ∑ k ∈ J i ( v ) k ⪯ j p k s i = ∑ k ∈ J v j ( v ) k ⪯ j p k s v j .
The total weighted completion time of schedule v is defined by
Z ( v ) = ∑ j ∈ J w j C j ( v ) = ∑ i ∈ M ∑ j ∈ J i ( v ) ∑ k ∈ J i ( v ) k ⪯ j w j p k s i = η ( v ) + ∑ j ∈ J ∑ k ∈ J v j ( v ) k ≺ j w j p k s v j .
where,
η v = ∑ i ∈ M ∑ j ∈ J i ( v ) w j p j s i = ∑ j ∈ J w j p j s v j ,
is the weighted sum of the processing times of schedule v . For this weighted sum and any schedule v , the following property was established [55] (Lem. 3):
η ( v ) ≥ ∑ j ∈ J w j p j s m .
Throughout the rest of this article, we denote the social optimum solution and the pure Nash equilibrium as x * and x , respectively.

2.1. Pure Nash Equilibrium

In decentralized decision-making, each job selects a machine that minimizes its disutility, modeled by its completion time. Then, the condition required for schedule x to be a Nash equilibrium is that no job has incentives to change its choice. More precisely, any change in his choice deteriorates his utility. Thus, the condition for x to be a Nash equilibrium is:
C j ( x ) ≤ p j s h + ∑ k ∈ J h ( x ) k ≺ j p k s h for all j ∈ J , h ∈ M .
The left-hand side of the Equation (9) indicates the completion time of the job j in the schedule x , while its right-hand side establishes the completion time that job j would have if it changed its choice from being processed by machine x j to machine h. In Section 3.1, we will utilize this Nash equilibrium condition to upper bound the PoA.

2.2. Social Optimum

In centralized decision-making, the social optimum is determined by a central authority. This optimum represents a schedule that minimizes the total weighted completion time. Recently, in Muñoz et al. [55] (Theor. 1), a lower bound was established for the optimal total weighted completion time. This inequality is presented in the following theorem.
Theorem 1.
([55] (Theor. 1)). For any optimal schedule x * of the Q | | ∑ w j C j problem, where ∑ i ∈ M s i = m , the following expression holds:
2 Z ( x 1 ) − η ( x 1 ) ≤ 2 Z ( x * ) − η ( x * ) .
In Theorem 1, x 1 represents a schedule in which all jobs are assigned to a fictitious machine operating at speed m (the total number of machines). Note that by Equation (4), the number of machines is equivalent to the sum of the speeds of all the machines. For this schedule, we have the following expressions that allow us to determine its total weighted completion time and its weighted sum of the processing times:
Z ( x 1 ) = ∑ j ∈ J ∑ k ∈ J k ⪯ j w j p k m ,
η ( x 1 ) = ∑ j ∈ J w j p j m .

3. Results

This section introduces parametric and fixed upper bounds for the price of anarchy of the Q ( W S P T ) | u t = − C j | ∑ w j C j problem. In Lemma 1, we establish a parametric expression that bounds the PoA for a family of instances defined by the number of machines (m) and the speed of the fastest machine ( s m ). Additionally, Lemma 3 provides a fixed upper bound that uses the number of machines as input (a common practice for scheduling problems).

3.1. Parametric Bound for the Price of Anarchy

Let I ( m , s m ) be the family of instances of the Q | | ∑ w j C j problem, where m uniformly related machines must process a given set of jobs, and the speed of the fastest machine is represented by s m . In addition, it also considers the rescaling established in Equation (4).
The following lemma establishes the parametric upper bound of the studied PoA.
Lemma 1.
For any instance of the family I ( m , s m ) , where ∑ i ∈ M s i = m , the price of anarchy of the Q ( W S P T ) | u t = − C j | ∑ w j C j problem for any pure Nash equilibrium is at most
s m 1 + 1 2 s m − 1 2 m .
Proof. 
Starting from the pure Nash equilibrium condition, Equation (9), and multiplying both sides of the inequality by w j ,
w j C j ( x ) ≤ w j p j s h + ∑ k ∈ J h ( x ) k ≺ j w j p k s h ∀ j ∈ J , h ∈ M .
Multiplying both sides of Equation (14) by s h / m and summing over all h ∈ M , leads to
w j C j ( x ) ≤ w j p j + ∑ h ∈ M ∑ k ∈ J h ( x ) k ≺ j w j p k m = w j p j + ∑ k ∈ J k ≺ j w j p k m = 1 − 1 m w j p j + ∑ k ∈ J k ⪯ j w j p k m , ∀ j ∈ J .
By summing over all j ∈ J in Equation (15) and using Equations (11) and (12), we have
Z ( x ) ≤ 1 − 1 m ∑ j ∈ J w j p j + Z ( x 1 ) = 1 − 1 2 m ∑ j ∈ J w j p j + Z ( x 1 ) − η ( x 1 ) 2 .
Utilizing Theorem 1 in Equation (16), we obtain the following expression:
Z ( x ) ≤ 1 − 1 2 m ∑ j ∈ J w j p j + Z ( x * ) − η ( x * ) 2 .
Note that, in Equation (17), the coefficient multiplying ∑ j w j p j is always positive, and according to Equation (8), we have
∑ j ∈ J w j p j ≤ s m η ( x * ) .
From Equations (17) and (18), we have
Z ( x ) ≤ Z ( x * ) + s m − s m 2 m − 1 2 η ( x * ) .
Note that in Equation (19), the coefficient multiplying η ( x * ) is always positive since m ≥ 2 and s m ≥ 1 . This is,
s m − s m 2 m − 1 2 = s m 1 − 1 2 m − 1 2 s m ≥ s m 1 − 1 4 − 1 2 = s m 4 > 0 .
By Equation (6), we have that
η ( x * ) ≤ Z ( x * ) .
Therefore, by Equations (19)–(21), we have
Z ( x ) ≤ Z ( x * ) s m + 1 2 − s m 2 m .
Finally, the proof is concluded by isolating Z ( x ) / Z ( x * ) . □
The subsequent lemma illustrates that the introduced parametric upper bound from Lemma 1 outperforms the parametric upper bound reported in [55].
Lemma 2.
The parametric upper bound for the price of anarchy introduced in this study for the Q ( W S P T ) | u t = − C j | ∑ w j C j problem is tighter than the parametric upper bound previously reported in the literature.
Proof. 
To compare the parametric upper bounds, we define D i as the difference between the parametric upper bounds for i parallel machines. Specifically, let D 2 represent the difference between the parametric upper bounds given by (1) and (13), and D m denote the difference between the parametric upper bounds specified by (2) and (13). Note that proving the non-negativity of D 2 and D m is sufficient to establish the lemma.
For the case of m = 2 machines, we have
D 2 = s 2 s 1 + 1 4 − s 2 1 + 1 2 s 2 − 1 4 = s 2 s 1 − 3 s 2 4 − 1 4 .
However, according to the assumptions (3) and (4), it is stated that s 1 ≤ 1 and s 2 ≥ 1 , implying
D 2 ≥ s 2 − 3 s 2 4 − 1 4 = 1 4 s 2 − 1 ≥ 0 .
On the other hand, for m > 2 machines, we have
D m = 3 2 1 − 1 m s m s 1 + 1 m − s m 1 + 1 2 s m − 1 2 m = s m 3 2 s 1 1 − 1 m − 1 s m 1 2 − 1 m − 1 + 1 2 m .
Note that, for m ≥ 2 , 1 − 1 / m and 1 / 2 − 1 / m are non-negative. Then, according to the assumptions (3) and (4), it is stated that s 1 ≤ 1 and s m ≥ 1 , implying
D m ≥ s m 3 2 1 − 1 m − 1 2 − 1 m − 1 + 1 2 m = 0 .
Equations (23) and (24) demonstrate that D i ≥ 0 for all i ≥ 2 , thereby concluding the proof. □

3.2. Fixed Bound for the Price of Anarchy

The following lemma establishes the fixed upper bound for the PoA.
Lemma 3.
The price of anarchy for any pure Nash equilibrium of the Q ( W S P T ) | u t = − C j | ∑ w j C j problem, where ∑ i ∈ M s i = m , is at most m.
Proof. 
From Lemma 1 we have that
P o A ≤ s m 1 + 1 2 s m − 1 2 m = s m 2 m − 1 2 m + 1 2 s m .
By Equations (3) and (4) we have that s m ∈ [ 1 , m ] . Then, from Equation (25), the PoA can be upper-bounded as follows:
P o A ≤ s m 2 m − 1 2 m + 1 2 ≤ m 2 m − 1 2 m + 1 2 = m .
□

3.3. Main Result

The following theorem establishes our main result, wherein the parametric upper bound for PoA from Lemma 1 and the fixed PoA from Lemma 3, is utilized in conjunction with the fixed PoA proved in [33] for the Q ( W S P T ) | u t = − C j , M j | ∑ w j C j problem (refer to Table 1). The use of this result is based on the fact that the studied problem is a particular case of the problem with machine eligibility restrictions. More precisely, when | M j | = m , i.e., each job can be processed by any of the m machines.
Theorem 2
For the family of instances I ( m , s m ) of the Q ( W S P T ) | u t = − C j | ∑ w j C j problem, where ∑ i ∈ M s i = m , the price of anarchy for any pure Nash equilibrium is, at most,
min s m 1 + 1 2 s m − 1 2 m , m , 4 .

4. Discussion

In the previous section, an analysis was conducted on families of instances of the Q ( W S P T ) | u t = − C j | ∑ w j C j problem. The analysis showed that the pure PoA is upper-bounded by Equation (13). Additionally, Lemma 2 established that this upper bound is tighter than the previous upper bound documented in the literature [45].
For two machines, the upper bound on the PoA is set at
1 2 + 3 s 2 4 ,
converging monotonically to
1 2 + s m ,
as the number of machines (m) increases.
Another feature of the proposed parametric upper bound is its complementarity with the fixed upper bound established in [33]. This complementarity is explained in Theorem 2. However, we are concerned about which of the other two bounds is tighter. The answer to this concern lies in the speed of the fastest machine. We will analyze the cases where m ≤ 4 and m > 4 .
For m ≤ 4 , analyzing
s m 1 + 1 2 s m − 1 2 m ≤ m ,
results in s m ≤ m . Thus, by assumptions (3) and (4), the parametric upper bound is always tighter than the fixed upper bound.
On the other hand, for m > 4 , analyzing
s m 1 + 1 2 s m − 1 2 m ≤ 4 ,
leads to
s m ≤ 7 m 2 m − 1 .
Consequently, the parametric upper bound is tighter than the fixed upper bound for some specific values of s m . More precisely, for m = 5 , the parametric upper bound will be better for s m ≤ 35 / 9 ≈ 3.89 . This value converges monotonically to 3.5 as m → ∞ .
Finally, we extend the results of Lemma 1 to the environment of identical parallel machines. In this case, the studied scheduling game is a generalization of the problem in an identical parallel machine environment. This problem is represented by P ( W S P T ) | u t = − C j | ∑ w j C j . By setting s m = 1 in Equation (13), we obtain ( 3 m − 1 ) / 2 m . This expression is well-documented in the literature and coincides with the expression for the Price of Anarchy (PoA) of the scheduling game for mixed strategies [34] and the robust PoA in the case of unweighted jobs [36].

5. Conclusions

This study presents upper bounds for the price of anarchy of a sequencing game on a uniformly related parallel machine environment. In this setting, each job acts as an agent, selecting a machine for its processing without considering the impact of its decision on other agents (jobs). The social goal is to minimize the total weighted completion time, and the local sequencing policy executed by each machine is the Weighted Shortest Processing Time (WSPT) rule.
The research focused on establishing properties for the Nash equilibrium and the optimal solution of the problem, aiming to determine a parametric upper bound for the price of anarchy based on the parameters: the number of machines (m) and the speed of the fastest machine ( s m ). The research has determined that the price of anarchy is upper-bounded by
s m 1 + 1 2 s m − 1 2 m .
The notable findings of this study are that the proposed parametric upper bound outperforms the previously reported parametric upper bound and the complementarity of this new bounds with the fixed upper bounds. Upper bounding the PoA by the number of machines and a fixed value of 4.
The obtained results offer new insights into the efficiency of the scheduling game under study, particularly in environments with two or three parallel machines. The findings are especially noteworthy for instances where the parametric upper bound reports a value less than 4.

Author Contributions

Conceptualization, F.T.M. and R.L.; Methodology, F.T.M.; Formal analysis, F.T.M. and R.L.; Investigation, F.T.M.; Writing—original draft, F.T.M.; Writing—review & editing, R.L. All authors have read and agreed to the published version of the manuscript.

Funding

The APC for this article was funded by the Vice-Rectorate for Research and Graduate Studies and the Department of Industrial Engineering of the University of Bío-Bío.

Data Availability Statement

Data are contained within the article.

Acknowledgments

The authors thank UBIOBIO GI2380142, and ANID FONDECYT 1230125 for their collaboration and support. Additionally, the authors thank the editor and anonymous referees for their valuable comments.

Conflicts of Interest

The authors declare no conflict of interest.

References

  1. Heydenreich, B.; Müller, R.; Uetz, M. Games and mechanism design in machine scheduling - An introduction. Prod. Oper. Manag. 2007, 16, 437–454. [Google Scholar] [CrossRef]
  2. Rzadca, K.; Trystram, D. Promoting cooperation in selfish computational grids. Eur. J. Oper. Res. 2009, 199, 647–657. [Google Scholar] [CrossRef]
  3. Averbakh, I. Nash equilibria in competitive project scheduling. Eur. J. Oper. Res. 2010, 205, 552–556. [Google Scholar] [CrossRef]
  4. Bilò, V.; Flammini, M.; Moscardelli, L. On Nash equilibria in non-cooperative all-optical networks. Algorithms 2021, 14, 15. [Google Scholar] [CrossRef]
  5. Lu, P.Y.; Yu, C.Y. Worst-case nash equilibria in restricted routing. J. Comput. Sci. Technol. 2012, 27, 710–717. [Google Scholar] [CrossRef]
  6. Mane, P.C.; Krishnamurthy, N.; Ahuja, K. Formation of stable and efficient social storage cloud. Games 2019, 10, 44. [Google Scholar] [CrossRef]
  7. Libman, L.; Orda, A. Atomic resource sharing in noncooperative networks. Telecommun. Syst. 2001, 17, 385–409. [Google Scholar] [CrossRef]
  8. Roughgarden, T.; Tardos, É. How bad is selfish routing? J. ACM 2002, 49, 236–259. [Google Scholar] [CrossRef]
  9. Bilò, D.; Gualà, L.; Leucci, S.; Proietti, G. Network creation games with traceroute-based strategies. Algorithms 2021, 14, 35. [Google Scholar] [CrossRef]
  10. Bukvić, L.; Pašagić Škrinjar, J.; Abramović, B.; Zitrický, V. Route selection decision-making in an intermodal transport network using game theory. Sustainability 2021, 13, 4443. [Google Scholar] [CrossRef]
  11. Oszczypała, M.; Ziółkowski, J.; Małachowski, J.; Lęgas, A. Nash equilibrium and Stackelberg approach for traffic flow optimization in road transportation networks—A case study of Warsaw. Appl. Sci. 2023, 13, 3085. [Google Scholar] [CrossRef]
  12. Hamers, H.; Klijn, F.; Slikker, M. Implementation of optimal schedules in outsourcing with identical suppliers. Math. Method. Oper. Res. 2019, 89, 173–187. [Google Scholar] [CrossRef]
  13. Cohen, J.; Pascual, F. Scheduling tasks from selfish multi-tasks agents. In Proceedings of the Euro-Par 2015: Parallel Processing: 21st International Conference on Parallel and Distributed Computing, Vienna, Austria, 24–28 August 2015; Lecture Notes in Computer Science. Träff, J., Hunold, S., Versaci, F., Eds.; Springer: Berlin/Heidelberg, Germany, 2015; Volume 9233, pp. 183–195. [Google Scholar] [CrossRef]
  14. Koutsoupias, E.; Papadimitriou, C. Worst-case equilibria. In Proceedings of the STACS 99: 16th Annual Symposium on Theoretical Aspects of Computer Science, Trier, Germany, 4–6 March 1999; Lecture Notes in Computer Science. Meinel, C., Tison, S., Eds.; Springer: Berlin/Heidelberg, Germany, 1999; Volume 1563, pp. 404–413. [Google Scholar] [CrossRef]
  15. Awerbuch, B.; Azar, Y.; Richter, Y.; Tsur, D. Tradeoffs in worst-case equilibria. Theor. Comput. Sci. 2006, 361, 200–209. [Google Scholar] [CrossRef]
  16. Azar, Y.; Fleischer, L.; Jain, K.; Mirrokni, V.; Svitkina, Z. Optimal coordination mechanisms for unrelated machine scheduling. Oper. Res. 2015, 63, 489–500. [Google Scholar] [CrossRef]
  17. Bilò, V.; Monaco, G.; Moscardelli, L.; Vinci, C. Nash social welfare in selfish and online load balancing. ACM Trans. Econ. Comput. 2022, 10, 1–41. [Google Scholar] [CrossRef]
  18. Caragiannis, I.; Flammini, M.; Kaklamanis, C.; Kanellopoulos, P.; Moscardelli, L. Tight bounds for selfish and greedy load balancing. Algorithmica 2011, 61, 606–637. [Google Scholar] [CrossRef]
  19. Caragiannis, I. Efficient coordination mechanisms for unrelated machine scheduling. Algorithmica 2013, 66, 512–540. [Google Scholar] [CrossRef]
  20. Caragiannis, I.; Fanelli, A. An almost ideal coordination mechanism for unrelated machine scheduling. Theor. Comput. Syst. 2019, 63, 114–127. [Google Scholar] [CrossRef]
  21. Chen, C.; Xu, Y. Coordination mechanisms for scheduling selfish jobs with favorite machines. J. Comb. Optim. 2020, 40, 333–365. [Google Scholar] [CrossRef]
  22. Christodoulou, G.; Koutsoupias, E.; Nanavati, A. Coordination mechanisms. Theor. Comput. Sci. 2009, 410, 3327–3336. [Google Scholar] [CrossRef]
  23. Czumaj, A.; Vöcking, B. Tight bounds for worst-case equilibria. ACM Trans. Algorithms 2007, 3, 1–17. [Google Scholar] [CrossRef]
  24. Gairing, M.; Lücking, T.; Mavronicolas, M.; Monien, B. Computing Nash equilibria for scheduling on restricted parallel links. Theor. Comput. Syst. 2010, 47, 405–432. [Google Scholar] [CrossRef]
  25. Immorlica, N.; Li, L.E.; Mirrokni, V.S.; Schulz, A.S. Coordination mechanisms for selfish scheduling. Theor. Comput. Sci. 2009, 410, 1589–1598. [Google Scholar] [CrossRef]
  26. Yu, L.; She, K.; Gong, H.; Yu, C. Price of anarchy in parallel processing. Inform. Process. Lett. 2010, 110, 288–293. [Google Scholar] [CrossRef]
  27. Abed, F.; Correa, J.R.; Huang, C.-C. Optimal coordination mechanisms for multi-job scheduling games. In Proceedings of the Algorithms-ESA 2014: 22th Annual European Symposium, Wroclaw, Poland, 8–10 September 2014; Lecture Notes in Computer Science. Schulz, A.S., Wagner, D., Eds.; Springer: Berlin/Heidelberg, Germany, 2014; Volume 8737, pp. 13–24. [Google Scholar] [CrossRef]
  28. Angel, E.; Bampis, E.; Pascual, F.; Thibault, N. Truthfulness for the sum of weighted completion times. In Proceedings of the Computing and Combinatorics—COCOON 2016, Ho Chi Minh City, Vietnam, 2–4 August 2016; Lecture notes in computer science. Dinh, T., Thai, M., Eds.; Springer: Cham, Switzerland, 2016; Volume 9797, pp. 15–26. [Google Scholar] [CrossRef]
  29. Bhattacharya, S.; Im, S.; Kulkarni, J.; Munagala, K. Coordination mechanisms from (almost) all scheduling policies. In Proceedings of the 5th Conference on Innovations in Theoretical Computer Science (ITCS), ACM, New York, NY, USA, 12–14 January 2014; pp. 121–134. [Google Scholar] [CrossRef]
  30. Braat, J.; Hamers, H.; Klijn, F.; Slikker, M. A selfish allocation heuristic in scheduling: Equilibrium and inefficiency bound analysis. Eur. J. Oper. Res. 2019, 273, 634–645. [Google Scholar] [CrossRef]
  31. Caragiannis, I.; Gkatzelis, V.; Vinci, C. Coordination mechanisms, cost-sharing, and approximation algorithms for scheduling. In Proceedings of the Web and Internet Economics: 13th International Conference, WINE 2017, Bangalore, India, 17–20 December 2017; Lecture Notes in Computer Science. R. Devanur, N., Lu, P., Eds.; Springer: Cham, Switzerland, 2017; Volume 10660, pp. 74–87. [Google Scholar] [CrossRef]
  32. Cole, R.; Correa, J.R.; Gkatzelis, V.; Mirrokni, V.; Olver, N. Decentralized utilitarian mechanisms for scheduling games. Games Econ. Behav. 2015, 92, 306–326. [Google Scholar] [CrossRef]
  33. Correa, J.R.; Queyranne, M. Efficiency of equilibria in restricted uniform machine scheduling with total weighted completion time as social cost. Nav. Res. Logist. 2012, 59, 384–395. [Google Scholar] [CrossRef]
  34. Hoeksma, R.; Uetz, M. The price of anarchy for utilitarian scheduling games on related machines. Discret. Optim. 2019, 31, 29–39. [Google Scholar] [CrossRef]
  35. Lee, K.; Leung, J.Y.T.; Pinedo, M.L. Coordination mechanisms for parallel machine scheduling. Eur. J. Oper. Res. 2012, 220, 305–313. [Google Scholar] [CrossRef]
  36. Rahn, M.; Schäfer, G. Bounding the inefficiency of altruism through social contribution games. In Proceedings of the International Conference on Web and Internet Economics, Cambridge, MA, USA, 11–14 December 2013; Lecture Notes in Computer Science. Chen, Y., Immorlica, N., Eds.; Springer: Berlin/Heidelberg, Germany, 2013; Volume 8289, pp. 391–404. [Google Scholar] [CrossRef]
  37. Zhang, L.; Zhang, Y.; Du, D.; Bai, Q. Improved price of anarchy for machine scheduling games with coordination mechanisms. Optim. Lett. 2019, 13, 949–959. [Google Scholar] [CrossRef]
  38. Cohen, J.; Dürr, C.; Nguyen Kim, T. Non-clairvoyant scheduling games. Theor. Comput. Syst. 2011, 49, 3–23. [Google Scholar] [CrossRef]
  39. Aspnes, J.; Azar, Y.; Fiat, A.; Plotkin, S.; Waarts, O. On-line routing of virtual circuits with applications to load balancing and machine scheduling. J. ACM 1997, 44, 486–504. [Google Scholar] [CrossRef]
  40. Cho, Y.; Sahni, S. Bounds for list schedules on uniform processors. SIAM J. Comput. 1980, 9, 91–103. [Google Scholar] [CrossRef]
  41. Finn, G.; Horowitz, E. A linear time approximation algorithm for multiprocessor scheduling. Bit 1979, 19, 312–320. [Google Scholar] [CrossRef]
  42. Graham, R.L.; Lawler, E.L.; Lenstra, J.K.; Rinooy Kan, A.H.G. Optimization and approximation in deterministic sequencing and scheduling: A survey. Ann. Discret. Math. 1979, 5, 287–326. [Google Scholar] [CrossRef]
  43. Pinedo, M.L. Scheduling: Theory, Algorithms, and Systems, 5th ed.; Springer: Berlin/Heidelberg, Germany, 2016; pp. 13–21. [Google Scholar]
  44. Kawaguchi, T.; Kyan, S. Worst case bound of an LRF schedule for the mean weighted flow-time problem. SIAM J. Comput. 1986, 15, 1119–1129. [Google Scholar] [CrossRef]
  45. Muñoz, F.T.; Parra, M.A. Price of anarchy in uniform parallel machines scheduling game with weighted completion time as social goal. RAIRO-Oper. Res. 2024, 58, 1093–1103. [Google Scholar] [CrossRef]
  46. Zhou, X.; Rao, W.; Liu, Y.; Sun, S. A decentralized optimization algorithm for multi-agent job shop scheduling with private information. Mathematics 2024, 12, 971. [Google Scholar] [CrossRef]
  47. Zhang, L.-H.; Lv, D.-Y.; Wang, J.-B. Two-agent slack due-date assignment scheduling with resource allocations and deteriorating jobs. Mathematics 2023, 11, 2737. [Google Scholar] [CrossRef]
  48. Feng, Q.; Li, S. Algorithms for multi-customer scheduling with outsourcing. Mathematics 2022, 10, 1553. [Google Scholar] [CrossRef]
  49. Wu, C.-C.; Gupta, J.N.D.; Lin, W.-C.; Cheng, S.-R.; Chiu, Y.-L.; Chen, J.-H.; Lee, L.-Y. Robust scheduling of two-agent customer orders with scenario-dependent component processing times and release dates. Mathematics 2022, 10, 1545. [Google Scholar] [CrossRef]
  50. Vázquez-Serrano, J.I.; Cárdenas-Barrón, L.E.; Peimbert-García, R.E. Agent scheduling in unrelated parallel machines with sequence- and agent–machine–dependent setup time problem. Mathematics 2021, 9, 2955. [Google Scholar] [CrossRef]
  51. He, R.; Yuan, J. Two-agent preemptive pareto-scheduling to minimize late work and other criteria. Mathematics 2020, 8, 1517. [Google Scholar] [CrossRef]
  52. Zhang, Y.; Geng, Z.; Yuan, J. Two-agent pareto-scheduling of minimizing total weighted completion time and total weighted late work. Mathematics 2020, 8, 2070. [Google Scholar] [CrossRef]
  53. Guo, H.; Li, W.; Deng, B. A survey on fair allocation of chores. Mathematics 2023, 11, 3616. [Google Scholar] [CrossRef]
  54. Eastman, W.L.; Even, S.; Isaacs, I.M. Bounds for the optimal scheduling of n jobs on m processors. Manag. Sci. 1964, 11, 268–279. [Google Scholar] [CrossRef]
  55. Muñoz, F.T.; Latorre-Núñez, G.; Ramos-Maldonado, M. Developing new bounds for the performance guarantee of the jump neighborhood for scheduling jobs on uniformly related machines. Mathematics 2024, 12, 6. [Google Scholar] [CrossRef]
  56. Smith, W.E. Various optimizers for single-stage production. Nav. Res. Logist. Q. 1956, 3, 59–66. [Google Scholar] [CrossRef]
Table 1. Price of anarchy in sequencing games on parallel machine environments for minimizing total weighted completion time. Local sequencing policies: Shortest Processing Time (SPT) and Weighted Shortest Processing Time (WSPT).
Table 1. Price of anarchy in sequencing games on parallel machine environments for minimizing total weighted completion time. Local sequencing policies: Shortest Processing Time (SPT) and Weighted Shortest Processing Time (WSPT).
Scheduling GamePrice of Anarchy ( ρ )Reference
P ( S P T ) | u t = − C j | ∑ C j ρ = 1 [25,35]
P ( W S P T ) | u t = − C j | ∑ w j C j ρ = 1.2071 [1,44]
Q 2 ( S P T ) | u t = − C j | ∑ C j ρ ∈ 1.1830 , 1.6180 [35]
Q 2 ( S P T ) | u t = − C j | ∑ C j ρ ≥ 1.1875 [37]
Q ( S P T ) | u t = − C j | ∑ C j ρ ∈ 1.5820 , 2 [34]
Q m ( S P T ) | u t = − C j | ∑ C j ρ ≤ 2 − 2 ( n + m ) ( n + 1 ) a[37]
Q 2 ( W S P T ) | u t = − C j | ∑ w j C j ρ ≤ s m s 1 + 1 4 [45]
Q m ( W S P T ) | u t = − C j | ∑ w j C j ρ ≤ 3 2 1 − 1 m s m s 1 + 1 m b[45]
Q ( W S P T ) | u t = − C j | ∑ w j C j ρ ≥ 2 [45]
P ( W S P T ) | u t = − C j , M j | ∑ C j c ρ = 4 [32]
P ( W S P T ) | u t = − C j , M j | ∑ w j C j ρ = 4 [32]
Q ( W S P T ) | u t = − C j , M j | ∑ w j C j ρ = 4 [33]
R ( W S P T ) | u t = − C j | ∑ w j C j ρ = 4 [32,33]
a n and m represent the number of jobs and machines, respectively. b  s m and s 1 represent the speed of the fastest and slowest machine, respectively. c  M j denotes machine eligibility restrictions.
Disclaimer/Publisher’s Note: The statements, opinions and data contained in all publications are solely those of the individual author(s) and contributor(s) and not of MDPI and/or the editor(s). MDPI and/or the editor(s) disclaim responsibility for any injury to people or property resulting from any ideas, methods, instructions or products referred to in the content.

Share and Cite

MDPI and ACS Style

Muñoz, F.T.; Linfati, R. Bounding the Price of Anarchy of Weighted Shortest Processing Time Policy on Uniform Parallel Machines. Mathematics 2024, 12, 2223. https://doi.org/10.3390/math12142223

AMA Style

Muñoz FT, Linfati R. Bounding the Price of Anarchy of Weighted Shortest Processing Time Policy on Uniform Parallel Machines. Mathematics. 2024; 12(14):2223. https://doi.org/10.3390/math12142223

Chicago/Turabian Style

Muñoz, Felipe T., and Rodrigo Linfati. 2024. "Bounding the Price of Anarchy of Weighted Shortest Processing Time Policy on Uniform Parallel Machines" Mathematics 12, no. 14: 2223. https://doi.org/10.3390/math12142223

APA Style

Muñoz, F. T., & Linfati, R. (2024). Bounding the Price of Anarchy of Weighted Shortest Processing Time Policy on Uniform Parallel Machines. Mathematics, 12(14), 2223. https://doi.org/10.3390/math12142223

Note that from the first issue of 2016, this journal uses article numbers instead of page numbers. See further details here.

Article Metrics

Back to TopTop