Skip to main content
main-content

Über dieses Buch

Scheduling theory has received a growing interest since its origins in the second half of the 20th century. Developed initially for the study of scheduling problems with a single objective, the theory has been recently extended to problems involving multiple criteria. However, this extension has still left a gap between the classical multi-criteria approaches and some real-life problems in which not all jobs contribute to the evaluation of each criterion.

In this book, we close this gap by presenting and developing multi-agent scheduling models in which subsets of jobs sharing the same resources are evaluated by different criteria. Several scenarios are introduced, depending on the definition and the intersection structure of the job subsets. Complexity results, approximation schemes, heuristics and exact algorithms are discussed for single-machine and parallel-machine scheduling environments. Definitions and algorithms are illustrated with the help of examples and figures.

Inhaltsverzeichnis

Frontmatter

Chapter 1. Multiagent Scheduling Fundamentals

Abstract
This chapter gives a general introduction to multicriteria and multiagent scheduling. Basic concepts from the two research areas are presented and a classification of considered problems, illustrating the presentation by examples, is proposed.
Alessandro Agnetis, Jean-Charles Billaut, Stanisław Gawiejnowicz, Dario Pacciarelli, Ameur Soukhal

Chapter 2. Problems, Algorithms and Complexity

Abstract
In this chapter, the basic notions related to problems, algorithms and complexity are recalled. Some topics related to approximability, problem relaxation and simple reductions between scheduling problems are also discussed. The chapter is composed of eight sections. Basic notions of complexity theory are recalled as well as properties of NP-complete and NP-hard problems. Exact and enumerative algorithms are discussed, and approximation algorithms and approximation schemes are considered. Methods of problems relaxation are presented. Some reductions between scheduling problems are described. The chapter ends with remarks on references.
Alessandro Agnetis, Jean-Charles Billaut, Stanisław Gawiejnowicz, Dario Pacciarelli, Ameur Soukhal

Chapter 3. Single Machine Problems

Abstract
This chapter is devoted to single-machine agent scheduling problems. We present most of the results for the case of two agents (K = 2), for simplicity and because the most of the results found so far in the literature apply to this case. Whenever it is possible, we illustrate how these results can be extended to scenarios with a larger number of agents.
Alessandro Agnetis, Jean-Charles Billaut, Stanisław Gawiejnowicz, Dario Pacciarelli, Ameur Soukhal

Chapter 4. Batching Scheduling Problems

Abstract
In this chapter, we consider batching scheduling problems in the context of agent scheduling. The main feature of these problems is the partition of the set of jobs into a number of subsets of jobs called batches. The chapter is composed of five sections. In Sect.4.1, we introduce basic definitions and notions of batching scheduling. In Sects. 4.2 and 4.3 we discuss two-agent s-batching and two-agent p-batching problems, respectively. We end the chapter with Sects. 4.4 and 4.5 including, respectively, complexity tables and bibliographic remarks.
Alessandro Agnetis, Jean-Charles Billaut, Stanisław Gawiejnowicz, Dario Pacciarelli, Ameur Soukhal

Chapter 5. Parallel Machine Scheduling Problems

Abstract
This chapter, presents some results on scheduling jobs on parallel machines in the Competitive and the Interfering scenarios. First, we study the case where job preemption is allowed, i.e. when the processing of a job can be interrupted and resumed later, possibly on another machine. Next, we study the case without job preemption. The chapter is composed of five sections. In Sect. 5.1, we consider parallel machine scheduling problems without job preemption. In Sects. 5.2 and 5.3, we consider preemptable parallel machine scheduling problems with arbitrary and equal job processing times, respectively. We end the chapter with Sects. 5.4 and 5.5 including, respectively, complexity tables and bibliographic remarks.
Alessandro Agnetis, Jean-Charles Billaut, Stanisław Gawiejnowicz, Dario Pacciarelli, Ameur Soukhal

Chapter 6. Scheduling Problems with Variable Job Processing Times

Abstract
In this chapter, we consider agent scheduling problems in which job processing times are variable. This means that the processing times, contrary to other chapters of the book, are not fixed and may change depending on such parameters as job starting times, job positions in schedule or the amount of resources allocated to jobs. Though problems of this type appear in many applications and non-fixed job processing times are studied in scheduling theory from over a few decades, agent scheduling problems with variable job processing times only recently started to be a new subject of research.
Alessandro Agnetis, Jean-Charles Billaut, Stanisław Gawiejnowicz, Dario Pacciarelli, Ameur Soukhal

Backmatter

Weitere Informationen

Premium Partner

    Bildnachweise