in the following format:
This page is not updated anymore. We just keep it online because many researchers still ask us for our data. Good luck !
@Misc{resource-constrained-scheduling-instances-page,
author = {C.C.B. Cavalcante and C. C. de Souza},
title = {Scheduling Problem under Labour Constraints -- Benchmarks},
howpublished = {{\tt www.ic.unicamp.br/\raisebox{-0.6ex}{\~{ }}cid/SPLC/SPLC.html}},
}
The Scheduling Problem under Labour Constraints (SPLC) is one of those problems usually found in Resource Constrained Project Scheduling (RCPS). The SPLC can be described as follows:
There is a set of orders, each of one is assigned to a single machine and is split up into several identical jobs. Each job consists of a sequence of tasks of duration 1 that must be executed one immediately after the other. The tasks of a job for a given order have a demand for labour defined by a labour requirement profile. All jobs of an order must be executed in the same machine and the order cannot be preempted (one order cannot have its execution interrupted to start the execution of another order assigned to the same machine). There are precedence relations between jobs, and there is a limit in the total number of workers available, in each period, to keep the jobs running.
The goal is to find a minimum makespan schedule - a schedule that minimizes the completion time of all jobs - that satisfies job precedence relations and that respects the labour constraints (labour usage cannot exceed the limit available in each period). SPLC is NP-hard in general.
This particular RCPS problem models a practical situation which, to our knowledge, was first studied in the project PAMIPS . SPLC and other related problems are discussed in "J. Kallrath and J. M. Wilson, 1997, Business Optimisation Using Mathematical Programming, Macmillan Press, UK. ISBN 0-333-67623-8". This reference also contains a solution of the instance Ins_10o_88j_A (L=24) (see Section Instances below).
Although a lot of work can be found in the literature of the classical Resource Constrained Project Scheduling, much less is reported specifically on the SPLC. Nevertheless, some research about SPLC is being done. This includes different approaches like Mixed Integer Programming Formulation, Constraint Net Propagation and Heuristic Methods like Tabu Search.
Our purpose here is to provide some instances of the SPLC, in order to make possible the comparison between the different strategies used in the search for good solutions of this problem. By doing so, we hope to establish a communication channel between researchers interested in the SPLC and, perhaps, to help in future design and development of new approaches.
We will do our best to maintain this home page. Participants are encouraged to send us comments and suggestions. Data sets and the format of submitted results are better explained in the next sections.
Thanks for you cooperation !
Cristina C. B. Cavalcante
Cid Carvalho de Souza
In order to generate the instances data set, we implemented a random instance generator with the following characteristics:
Instance with m orders, where each order has between mJ and MJ identical
jobs. The jobs in a given order have the same duration, randomly chosen
between md and Md. The labour requirement of each task of a job is chosen
from the set {2, 3, (4), 6, (12), (18)}, where numbers in brackets are
less frequent. The precedence graph describing the relations between jobs
is built in such a way that jobs from different orders are related with
probability p if they belong to consecutive orders. Jobs from non-consecutive
orders cannot be related. Precedence relations between jobs in the same
order are implicit.
The output of the random instance generator is written in a file with name:
Ins_< number of orders >o_< number of jobs >j_< letter >.dat
where letter is A, B, C,... and is used to distinguish different instances
with the same number of orders and the same number of jobs.
The .dat file, output of the random instance generator, has the following format (comments lines begin with % and are not include in the data files) :
The instances should be tested for different numbers of available workers (L). Typical values of L are 18, 21, 24, 27 and 30.
New results can be sent by mail to
in the following format:
Please, mail to
for any questions and/or comments.
Clique here for a list of known references (in BibTex format) on the SPLC.
(see also the book cited at the beginning of this page).
We would like to express our gratitude to the following persons who had contributed with comments, results and suggestions:
Scheduling Problem under Labour Constraints -- Benchmarks WWW Home Page
maintained by Cristina C. B. Cavalcante & Cid Carvalho de Souza.
Last updated February, 2000.
.