For the RCPSP, a set of benchmark instances called PSPlib is generated by Kolisch and Sprecher (1997b), Kolisch et al. (1995), and can be found on the web Kolisch and Sprecher (1997a). These instances have been employed in many studies, for example by Demeulemeester and Herroelen (1997), Kolisch and Drexl (1996) and Kolisch et al. (1995). We transform these RCPSP instances into TCPSP instances. We restrict ourself to single mode instances.
To transform the instances from the PSPlib into TCPSP instances, two additional aspects have to be introduced. First, we need to define the overtime and hiring possibilities with their associated costs, and second we need to introduce deadlines.
The TCPSP distinguishes between regular and overtime time units, where the RCPSP has only one type of time units. We let each time unit from the RCPSP correspond to a regular time unit in the TCPSP. In addition, we introduce overtime in a weekly pattern. Day 1 of the week, the Sunday, contains only 8 overtime time units. Day 2 to 6, the weekdays, start with 8 regular time units, followed by 4 overtime time units. Day 7, the Saturday, contains again only 8 overtime time units. This weekly pattern is repeated until the deadline of the instance is reached. All other aspects, like job durations, precedence relations, resource availability, and resource requirements remain unchanged.
To get insight in the quality of the solution generated by the two stage heuristic, we compare the TCPSP solution with the RCPSP solution. A comparison can be made if we set all costs equal to 1 and let the deadline of all jobs be the (best known upper bound to the) minimum makespan of the RCPSP instance. This means that the number of regular time buckets before the deadline in the TCPSP, is exactly the (best known upper bound to the) minimum makespan of the RCPSP instance. The quality of the schedule is given by its costs. If a schedule has zero costs, the two stage heuristic gives the optimal (best known) schedule for the RCPSP instance. If not, the costs of the schedule give an indication on how far we are from the best known schedule, i.e., it gives the amount of irregular capacity used to reach the best known makespan.
Besides choosing the deadline equal to the (best known upper bound the) minimum makespan, which we denote by Cmax, it can be chosen as a fraction of Cmax. By letting the deadline be equal to b.Cmax, where b in [0, 1], the problem becomes tighter and more irregular capacity will be needed. The resulting objective value will indicate the costs to complete the project earlier.
References
- Demeulemeester, E., W. Herroelen. 1997. New benchmark results for the resource-constrained project scheduling problem. Management Science 43 1485–1492.
- Kolisch, R. 1995. Project Scheduling under Resource Constraints. Physica-Verslag.
- Kolisch, R., A. Drexl. 1996. Adaptive search for solving hard project scheduling problems. Naval Research Logistics 43 23–40.
- Kolisch, R., A. Sprecher. 1997a. Project scheduling library - PSPlib. http://129.187.106.231/psplib/.
- Kolisch, R., A. Sprecher. 1997b. PSPLIB a project scheduling problem library. European Journal of Opera- tional Research 96 205–216.
- Kolisch, R., A. Sprecher, A. Drexl. 1995. Characterization and generation of a general class of resourceconstrained project scheduling problems. Management Science 41.