Proportional optimization and fairness
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.
- Just-in-time scheduling. Models and algorithms for computer and manufacturing systems
- Solution of the Liu-Layland problem via bottleneck just-in-time sequencing
- scientific article; zbMATH DE number 5172390
- Proportionate progress: A notion of fairness in resource allocation
- Just-in-time sequencing in mixed-model production systems relating with fair representation in apportionment theory
- Proportionate progress: A notion of fairness in resource allocation
- An optimality-argument for equal weighting
- Webster sequences, apportionment problems, and just-in-time sequencing
- Fair task allocation problem
- Balancing schedules using maximum leximin
- Do balanced words have a short period?
- Fair optimization and networks: a survey
- Routing equal-size messages on a slotted ring
- A branch and bound algorithm for the response time variability problem
- Optimization problems in fair division theory.
- Inequity averse optimization in operational research
- Minimising maximum response time
- scientific article; zbMATH DE number 1903384 (Why is no real title available?)
- Maximin fairness in project budget allocation
- Makespan minimization of multi-slot just-in-time scheduling on single and parallel machines
- Using aggregation to reduce response time variability in cyclic fair sequences
- Solution of the Liu-Layland problem via bottleneck just-in-time sequencing
- Fair apportionment in the view of the Venice Commission's recommendation
This page was built for publication: Proportional optimization and fairness
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q947706)
