View article

The Test Laboratory Scheduling Problem (TLSP) arises in a real-world industrial test laboratory, where a large number of activities in multiple projects has to be scheduled, subject to several legal and operational constraints. It is an extension of the well-known (Multi-Mode) Resource-Constrained Project Scheduling Problem ((M) RCPSP)(see eg [2, 5]) which, in addition to other extensions, includes several unique features. Most importantly, the activities to be scheduled (jobs) are not monolithic, but composed of multiple smaller units called tasks and derive all their properties from the tasks they contain. The grouping of tasks into jobs must be determined by the solver as part of the solution process. A similar concept exists in the form of batch scheduling (eg [14, 12]) or schedule-dependent setup times (eg [8, 9]). The difference is that in these settings, tasks are scheduled directly and batches arise implicitly from the final schedule. TLSP also uses heterogeneous resources, with general restrictions on which units of a resource can be used for each task. While usually, variants of RCPSPS assume a homogeneous resource model, similar restrictions can be found in the Multi-Skill RCPSP (MSPSP)[1], where each resource unit possesses a set of skills and requirements are also formulated in terms of skills.