Scheduling jobs of equal length: complexity, facets and computational results

The following problem is studied in this chapter. Given are n jobs, which have to be processed on a single machine within the timespan [0, T]. In our formulation, we assume T to be an integer, and the timespan is discretized into T time periods (or periods) of length one, viz. [0,1], [1, 2],..., [T − 1, T]. Thus, period t refers to the time slot [t − 1, t], t = 1,...,T. The machine can handle at most one job at a time. The processing time, or length, of each job equals p, p ∈ ℕ. The processing cost of each job is an arbitrary function of its start-time: we denote by c _jt the cost of starting job j in period t. The problem is to schedule all jobs so as to minimize the sum of the processing costs. We refer to this problem as problem SEL (Scheduling jobs of Equal Length).