Catálogo de publicaciones - libros

The scheduling problems presented in this book follow from two different application areas: production and computer engineering. The common feature of the considered problems is the fact that it is crucial for the control system to observe the due dates.

We start this chapter with providing some basic concepts in deterministic scheduling theory (Section 2.1). In Section 2.2 we introduce the theory of apportionment, developed by Balinski and Young. This theory originated from the problem of finding a fair representation of states in the US House of Representatives. Some methods of apportionment may be also used to solve scheduling problems, especially schedule balancing problems. We present these applications in Chapter 5.

In this chapter we consider the scheduling problems with minimization of the earliness and tardiness costs, where all tasks should be completed at the same due date. Problems with minimization of the earliness and tardiness costs occur in just-in-time systems as we discuss in Section 1.1.4. Considering a common due date is relevant in the situation where several items constitute a single order, or they are delivered to an assembly line in which the components should all be ready at the same time to avoid storing inventories or delays of deliveries. Since this requirement cannot be fulfilled the scheduling objective is minimization of the earliness and tardiness costs.

In this chapter we consider the just-in-time scheduling problems, where each task has a distinct due date. The due dates may be either problem parameters or decision variables.

The idea of balancing the schedules in order to meet the just-in-time objectives originated in Toyota. Generally speaking, it is required that for every part type the number of units of this part used for assembly remains constant in each time period (). The order of products scheduled on the assembly line allows to determine the number of parts required for assembly, based on the explosion of the bill of material. Thus, the variation of the production volume at the part manufacturing level can be minimized by appropriate scheduling of the finished products on the assembly line.