Multicriteria Scheduling [Hardcover]

Vincent T'kindt (Author), Jean-Charles Billaut (Author), H. Scott (Translator)

Book Description

Publication Date: August 26, 2002 | ISBN-10: 3540436170 | ISBN-13: 978-3540436171 | Edition: 1

Scheduling and multicriteria optimisation theory have been subject, separately, to numerous studies. Since the last fifteen years, multicriteria scheduling problems have been subject to a growing interest. However, a gap between multicriteria scheduling approaches and multicriteria optimisation field exists. This book is a first attempt to collect the elementary of multicriteria optimisation theory and the basic models and algorithms of multicriteria scheduling. It is composed of numerous illustrations, algorithms and examples which may help the reader in understanding the presented concepts.

Editorial Reviews

Review

From the reviews of the second edition:

"The book is devoted to a particular class of scheduling problems, namely, to those that involve multiple criteria for the evaluation of the constructed schedules. This approach is highly motivated by practical needs, several examples of which illustrate the thesis well. … The book is complemented by two appendices presenting, respectively, the notation of scheduling problems and a synthetic summary of the results presented. Summing up, I consider this book being a valuable introduction to the interesting field of multicriteria scheduling problems … ." (Jacek Blazewicz, Zentralblatt MATH, Vol. 1126 (3), 2008)

--This text refers to an alternate Hardcover edition.

Language Notes

Text: English (translation)
Original Language: French

Product Details

• Hardcover: 319 pages
• Publisher: Springer; 1 edition (August 26, 2002)
• Language: English
• ISBN-10: 3540436170
• ISBN-13: 978-3540436171
• Product Dimensions: 9.4 x 6.6 x 0.9 inches
• Shipping Weight: 1.3 pounds
• Average Customer Review: 5.0 out of 5 stars  See all reviews (1 customer review)
• Amazon Best Sellers Rank: #7,548,697 in Books (See Top 100 in Books)

More About the Author

Discover books, learn about writers, read author blogs, and more.

Customer Reviews

Most Helpful Customer Reviews

2 of 2 people found the following review helpful:

5.0 out of 5 stars Scheduling Theory made easy, August 29, 2007

By 

ART SEDIGHI (Old Bethpage, NY United States) - See all my reviews

This review is from: Multicriteria Scheduling: Theory, Models and Algorithms (Hardcover)

Scheduling is the concept of sharing a scarce resource amongst users without starving any of the users, and at best gives the impression that every user has access to all of what that resource has to offer. This poses a challenge when the numbers of users increase dramatically or the duration of the jobs varies greatly. What makes this challenge even greater is that scheduling problems are mostly NP-Complete, with a very limited number of scenarios that are considered to fall under the P-type problem domain.

Single criterion scheduling are problems where the reader is interested in maximizing or minimizing only one thing or criteria (minimize the flow time, or minimizing the completion time). Many scenarios, machine shop or other wise, require more than criterions to be optimized. For example on a multi-processing machine, you want to minimize startup time and at the same time minimize completion time of all the tasks. There are times where these two criterions conflict - i.e. you might need to suspend a task thus delaying its completion time in order to start a newly arrived task. The point is that "sacrifices" must be made, and that is the point of heuristic-type algorithms; they aim to minimize the overall sacrifice one has to make in order to optimize everything near-perfectly. This does not always work, however, but considering the problem domain, it is a very good attempt at solving the unsolvable.

Multicriteria Scheduling: Theory, Models and Algorithms, by Vincent T'kindt and Jean-Chalres Billaut is the latest book that covers scheduling and more specifically multicriteria scheduling in research and applications thereof very well. The first edition of the text which was published in 2002, the authors mainly focused on the field of multicriteria scheduling along with all the algorithms, models, etc, that described the field. Being the first complete text dedicated to multicriteria scheduling and optimization, there were lots to talk about and even more has been developed in the past five or so years. For the second edition of the text, the authors builds and refines the first editions with new research results, new findings and many new algorithms. A number of chapters were rewritten such as Just-in-Time Scheduling problems (chapter 5), and the rest revised to include follow-up information and comments.

For those unfamiliar with the topic at hand, the authors spend the first couple of chapters talking about scheduling, its complexities and then delve into multicriteria scheduling and problems. If you have never heard or seen any scheduling problems, the first two chapters are a must; otherwise, it is still a good review as the authors use these chapters as the basis for later discussions. As you might expect, multicriteria scheduling shares a number of ideas from multicriteria optimization and theory. A chapter is dedicated to this topic as it is required notion for the rest of the text.

One addition to the this edition of the text which clearly demonstrates the authors' deep understanding of the topic both in research and commercial arena is chapter 6: Robustness consideration! Being in the field of Grid and HPC, I come across a number of texts that cover the area, but none have ever even attempted to cover robustness of an algorithm. In this chapter, the authors depict a number of algorithms discussed and discuss variation of that algorithm and it would hold up under different scenarios which directly reflect what one would see a real-application.

The area of Scheduling is an exciting area of research which has direct application in many aspects of Computer Science. Multicriteria Scheduling: Theory, Models and Algorithms covers the topic of scheduling and more specifically the applications of optimization problems in scheduling very well. The authors guide the reader thru numerous algorithms much of which is used everyday is various applications.