Multicriteria Scheduling

Frontmatter

Introduction

Abstract

Scheduling theory first appears in the mid 1950s.Since then the problems addressed become closer to industrial applications, thus increasing in complexity.

Vincent T’kindt, Jean-Charles Billaut

1. Introduction to scheduling

Abstract

Scheduling problems are encountered in all types of systems, since it is necessary to organise and/or distribute the work between many entities. We find in every book in the literature a definition of a scheduling problem as well as its principal components. Among these definitions we can quote the following one [Carlier and Chrétienne, 1988]:

“Scheduling is to forecast the processing of a work by assigning resources to tasks and fixing their start times. [...] The different components of a scheduling problem are the tasks, the potential constraints, the resources and the objective function.[...] The tasks must be programmed to optimise a specific objective [...] Of course, often it will be more realistic in practice to consider several criteria.”

Vincent T’kindt, Jean-Charles Billaut

2. Complexity of problems and algorithms

Abstract

Complexity theory proposes a set of results and methods to evaluate the intrinsic complexity of the problems. A problem belongs to a class of complexity, which informs us of the complexity of the “best algorithm” able to solve it. Complexity theory brings our attention to decision problems, and is based on languages theory and Turing machines. The reader interested in a very detailed presentation of complexity theory is referred to [Garey and Johnson, 1979] or [Papadimitriou, 1995].

Vincent T’kindt, Jean-Charles Billaut

3. Multicriteria optimisation theory

Abstract

Decision Making arises at all levels in firms. A firm may be described as a “complex system”, and we can make the following remarks ([Boldur, 1982]):

• A complex system can be broken down into sub-systems according to the objectives of the first one (production sub-system, human resources management sub-system, etc.).
• The methods of management must be arranged in order to propose solutions that fit the actual objectives.
• It is necessary to mix different disciplines such as Operational Research, Management and Psychology in order to thoroughly understand and model a complex system.

Vincent T’kindt, Jean-Charles Billaut

4. An approach to multicriteria scheduling problems

Abstract

In the context of production, the planning phase is broken down hierarchically into different levels: strategic, tactical and operational. The production plan at the tactical level determines the quantities of products to make by time period. Its objectives are:

• to satisfy the customers’ requirements, that is to say to supply the customer with the product he wants, in the desired quantity and at the desired date,
• to balance continuously the existing resources and the resources necessary for production, by avoiding underloading as well as overloading,
• to ensure production at lowest cost or at least with maximum profitability.

Vincent T’kindt, Jean-Charles Billaut

5. Single machine Just-in-Time scheduling problems

Abstract

One of the classical objectives in shop scheduling is linked to the respect of the due dates which attend, for example, the meetings with customers on the delivery dates of the manufactured products. For numerous problems, the criterion used in this case is a measure of the tardiness of the finished products, as for example the average tardiness, the maximum tardiness or yet the number of late jobs. Nevertheless, even though, for example, storage of products means a non negligible cost, it is necessary to optimise just as well a criterion linked to the earliness of jobs.

Vincent T’kindt, Jean-Charles Billaut

6. Single machine problems

Abstract

[Hoogeveen, 1992b] studies the general problem of the minimisation of K functions of the completion times, denoted by f _max ⁱ and assumed to be increasing. We have \( f_{\max }^i\left( S \right) = \mathop {\max }\limits_{j = 1, \ldots ,n} f_j^i\left( {{C_j}\left( S \right)} \right) \) with f _j ⁱ being also increasing functions. Hoogeveen proposes an a posteriori algorithm for the \( 1|| \in \left( {f_{\max }^1/f_{\max }^2, \ldots ,f_{\max }^K} \right) \) problem and distinguishes both bicriteria and mul-ticriteria cases.

Vincent T’kindt, Jean-Charles Billaut

7. Shop problems

Abstract

In this section we are interested in multicriteria flowshop scheduling problems with two machines. Each job J _i is processed on the machine M₁ for a duration p _{i ,1} then on the machine M ₂ for a duration p _i,2- In this context, the multicriteria scheduling problem which is addressed the most in the literature involves the minimisation of the criteria math and C _max . Different scheduling problems are derived according to the form of the considered objective function.

Vincent T’kindt, Jean-Charles Billaut

8. Parallel machines problems

Abstract

[Mohri et al., 1999] are interested in a bicriteria scheduling problem where two machines are available to process n independent jobs that can be preempted at any (real) time. Each job J¿ is defined by a processing time p _i and a due date d_i. Without loss of generality we assume that d ₁ ≤ d ₂ ≤ ... ≤ d _n . The aim is to schedule the jobs in such a way that the makespan C _max sind the maximum lateness L _max are minimised. By considering the e constraint approach they provide a characterisation of strictly non dominated criteria vectors. This problem is solvable in polynomial time.

Vincent T’kindt, Jean-Charles Billaut

9. Shop problems with assignment

Abstract

[Fortemps et al., 1996] are interested in a scheduling problem which occurs in the chemical industry, denoted by HF ₃, (P6, P3, 1)|constr|F _ℓ (C _max ,γ(T _i ), δ(VPI)), where constr translates a set of constraints described hereafter. The shop comprises three stages. Each job J _i is defined by a release date, and a due date. Each machine M _j also has an availability date, denoted by R _j .

Vincent T’kindt, Jean-Charles Billaut

Backmatter