Proportional optimization and fairness (Q947706): Difference between revisions

The problem studied in the book is the one dealing with the very important question arising in scheduling theory: ``How to allocate resources to competing tasks that the assignment is ``fair''?'' Then an additional question arises: ``What is the meaning of fairness in this context?'' Here, the author gives a very comprehensive answer based on the apportionment theory. The proposed algorithm have their roots in house monotone methods and the results are especially welcome in the area of just-in-time scheduling. The book is a very solid piece of work with a thorough introduction to the field followed by a detailed presentation of several important topics. It is composed of 11 chapters complemented by an extensive bibliography and an index. Chapter 1 quotes in a very brief way basic definitions used throughout the book. Chapter 2 briefly reviews main results of the apportionment theory used in the remainder of the book. It emphasizes the axiomatic approach to the apportionment problem and to the construction of the just-in-ime sequences. The approach relies on the divisor methods, in particular parametric methods. Chapter 3 considers the problems of deviation minimization, the total and the maximum deviation, as tools for obtaining just-in-time sequences. It formulates these problems as nonlinear integer optimization and presents efficient algorithms for their solution. The algorithms are based on the concept of ideal positions, closely related to the Webster's apportionment method. Chapter 4 proves that there exist cyclic solutions that minimize the total deviation for symmetric point deviation functions, the same is shown for the maximum deviation. It also proves that limiting optimization to the sequences with the bottleneck deviation not exceeding. Chapter 5 gives a more efficient algorithm for the maximum absolute deviation (referred to as bottleneck) deviation. The absolute value function of deviation results in optimal bottleneck being always less than 1, and allows to develop strong upper and lower bounds on the optimal bottleneck. These bound and other properties of the bottleneck optimal just-in-time sequences are used in the application to the Liu-Layland problem, a of on the classical problem in deadline scheduling area. Chapter 6 further exploits the properties of just-in-time sequences with small bottleneck deviations, which are understood as those less than 1/2. The question is what are the instances that admit this small bottleneck deviation? The answer given in the chapter is that there is only one, called the power-of-two instance that results in this small bottleneck deviation for \(n>3\). The chapter also shows the connections between the small bottleneck deviation problem and the famous Fraenkel's conjecture. Chapter 7 addresses the response time variability minimization problem, where the average response time for a client is a reciprocal of its desirable rate. Thus, being as close as possible to the average response time aims at achieving the ``as evenly as possible'' goal. The response time variability is one of the main objectives in stride scheduling as well. The chapter shows that the problem is \(\text{NP}=\text{hard}\), proposes exact and heuristic solutions, and reports computational experiments with the latter. Chapter 8 proves that the optimal bottleneck sequences make tasks progress at the rates close enough to the tasks' processing time to request interval ratios so that solve the Liu-Layland problem. It also gives necessary conditions for the apportionment divisor methods to solve the Liu-Layland problem, and proves that the quota divisor methods solve the Liu-Layland problem as well. Chapter 9 focuses on the problem of constructing just-in-time sequences for supply chains so that the temporal capacity constraints imposed by suppliers are respected. The constraints are modeled by giving the limiting, supply-dependent proportions \(p:q\) that at most \(p\) out of any \(q\) models delivered by the supply chain must be supplied by a particular supplier. Though the problem of finding such a sequence is NP-hard in the strong sense, the chapter discusses a number of approaches: synchronized delivery and periodic synchronized delivery for better balancing workloads in supply chains. Chapter 10 looks into the problem of fairness in fair queueing and stride scheduling. It shows that both use the Jefferson's and Adams' method of apportionment, and both are peer-to-peer fair. However, the chapter also argues that the Webster's method could prove a better yet untested choice for fair queueing and stride scheduling. Finally, Chapter 11 extends the models developed in Chapters 2, 3, and 9 to manufacturing environments with variable processing and set-up times. Summing up, the book contains an up-to-date presentation of different approaches addressing the problem of fair and just-in-time scheduling. Written by the expert in the field, it is a must for those interested in the above area.