Overview
Scheduling with time windows is a fundamental problem in computing area. The decision version of the problem consists in determining whether a set of (n) jobs characterized by their respective release times (r), processing times (p) and deadlines (d) can be scheduled without overlap along a time horizon (H) on a single machine. This problem is relevant both in industry and academia. Because This problem is strongly NP-Complete, we believe that there is no such polynomial-time mapping unless P equals NP.
Useful datasets
In this page, we propose a list of problem instances that we generated to assess the performance of various algorithms/solvers. These problem instances are made on-line available for public use. In fact, we used two different generators to produce these datasets namely random and pseudo-random generators.
Random Generator : the random instances are grouped into data sets corresponding to combinations of various levels of n, U, μ_p , rho_p , and TW where U is the load of the problem instance (also the density of jobs along the scheduling horizon H), μ_p and rho_p are the mean and coefficient of variation of the processing times of the n jobs. TW serves to determine the parameters R and D of the relative range of release and deadlines; i.e., R and D are drawn from a discrete uniform[0, TW ]. The random generator draws n processing times from the Normal(μ_p , σ_p ) rounded to the nearest integer. It sorts the jobs randomly, and computes for each job j, j ∈ N={1,...n}, its starting time S_j and completion time C_j. Consequently, it calculates the release time r_j = S_j − R and the deadline d_j = min{C_j + D, H}. In the following, you will find some instance files that we generated. We generate random problem instances according to four levels of n 1500, 2000, 2500, and 3000 jobs.
Pseudo-random Generator : The pseudo-random generator uses an initial instance I_0 having a given number of jobs and a scheduling horizon H with a known feasible solution S_0 and a list of idle time windows I_0 . It builds new instances out of I_0 by filling idle times with additional jobs. It adds these jobs one by one as follows. It chooses, randomly, an idle time window. We generated 100 problem instances where the size ranges between 7127 and 7226 jobs.
In the following, you will find all generated datasets both random and pseudo-random.