← COIN ResearchClear all queuesภาษาไทย
COIN · ROSE · PERMUTATION OPTIMIZATION

Precedence-Constrained
Scheduling Laboratory

Schedule activities under precedence relations and limited renewable resources using a priority-list permutation and Serial Schedule Generation Scheme. Compare Pareto trade-offs among project duration, tardiness, total completion time and resource leveling.

One evaluator · equal budgetsEvery algorithm shares the same instance, evaluator, seeds and objective-evaluation budget, making the comparison auditable and reproducible.
StatusReady
Runs completed0 / 0
Evaluations—
Best primary—

Benchmark

Results appear after an experiment.

Current: —

Introduction and problem context

Precedence-constrained scheduling appears in construction, software delivery, research, project manufacturing and business workflows. An activity cannot start before its predecessors finish, and even an eligible activity must wait when people, machines or other renewable resources are unavailable.

This laboratory models the single-mode, non-preemptive RCPSP. Every activity has a fixed duration and consumes renewable resources throughout execution. The evaluator does not trade constraint violations against business goals: a Serial Schedule Generation Scheme decodes every priority list into a precedence- and capacity-feasible schedule.

Representation

chromosome π = a permutation of activity IDs
decoder: eligible set → highest-priority activity in π → earliest resource-feasible start

The permutation is a priority list, not a literal execution order. If its first activity still has unfinished predecessors, the decoder selects the highest-ranked eligible activity. This lets COIN, ROSE, HBSA and permutation GA share one representation without repairing the DAG.

Problem formulation, objectives and fitness calculation

Let pⱼ be duration, rⱼₖ demand for renewable resource k, Rₖ capacity, Pⱼ the predecessor set, and Sⱼ/Cⱼ start/completion times.

Cᵢ ≤ Sⱼ ∀ i∈Pⱼ
Σⱼ∈A(t) rⱼₖ ≤ Rₖ ∀k,t
min f₁ = Cmax
min f₂ = Σⱼ max(0,Cⱼ−dⱼ)
min f₃ = maxⱼ max(0,Cⱼ−dⱼ)
min f₄ = Σⱼ Cⱼ
min f₅ = meanₖ Varₜ(Uₖ(t)/Rₖ)

Makespan closes the project early; tardiness protects due dates; total completion time favors early throughput; resource variance smooths utilization. Selecting two or three objectives activates Pareto algorithms under the same evaluation budget.

Benchmark provenance and literature review

PSPLIB by Kolisch and Sprecher is the principal RCPSP benchmark library. The lab now bundles official .sm instance 1_1 at J30, J60, J90 and J120 scale. J30/J60/J90 carry proven optima; J120 exposes its lower bound without mislabeling it as an optimum. Since PSPLIB does not define activity-level due dates, the MO extension deterministically sets them to 110% of precedence-only earliest finish and records that provenance.

Classical approaches range from CPM and priority rules to exact and population methods. Every algorithm shares one SGS and an equal evaluation budget. Results report wall-clock seconds, evaluations per second and microseconds per evaluation alongside solution quality.

References

  1. PSPLIB — Project Scheduling Problem Library.
  2. Kolisch, R. & Sprecher, A. (1997). PSPLIB — A project scheduling problem library. European Journal of Operational Research, 96(1), 205–216. DOI.
  3. Hartmann, S. & Kolisch, R. (2000). Experimental evaluation of state-of-the-art heuristics for the RCPSP. EJOR, 127, 394–407.
  4. Kolisch, R. (1996). Serial and parallel resource-constrained project scheduling methods revisited: theory and computation. EJOR, 90, 320–333.