Consider a scheduling problem (P) which consists of a set of jobs to be performed within a limited number of time periods. For each job, we know its duration as an integer number of time periods, and preemptions are allowed. The goal is to assign the required number of time periods to each job while minimizing the assignment and incompatibility costs. When a job is performed within a time period, an assignment cost is encountered, which depends on the involved job and on the considered time period. In addition, for some pairs of jobs, incompatibility costs are encountered if they are performed within common time periods. (P) can be seen as an extension of the multi‐coloring problem. We propose various solution methods for (P) (namely a greedy algorithm, a descent method, a tabu search and a genetic local search), as well as an exact approach. All these methods are compared on different types of instances.
