1# --------------------------------------------------------------------------
2# Source file provided under Apache License, Version 2.0, January 2004,
3# http://www.apache.org/licenses/
4# (c) Copyright IBM Corp. 2015, 2022
5# --------------------------------------------------------------------------
6
7"""
8The RCPSP (Resource-Constrained Project Scheduling Problem) is a generalization
9of the production-specific Job-Shop (see job_shop_basic.py), Flow-Shop
10(see flow_shop.py) and Open-Shop(see open_shop.py) scheduling problems.
11
12Given:
13- a set of q resources with given capacities,
14- a network of precedence constraints between the activities, and
15- for each activity and each resource the amount of the resource
16 required by the activity over its execution,
17the goal of the RCPSP is to find a schedule meeting all the
18constraints whose makespan (i.e., the time at which all activities are
19finished) is minimal.
20
21Please refer to documentation for appropriate setup of solving configuration.
22"""
23
24from docplex.cp.model import *
25import os
26
27#-----------------------------------------------------------------------------
28# Initialize the problem data
29#-----------------------------------------------------------------------------
30
31# Read the input data file.
32# Available files are rcpsp_default, and different rcpsp_XXXXXX.
33# First line contains the number of tasks, and the number of resources.
34# Second line contains the capacities of the resources.
35# The rest of the file consists of one line per task, organized as follows:
36# - duration of the task
37# - the demand on each resource (one integer per resource)
38# - the number of successors followed by the list of successor numbers
39
40filename = os.path.dirname(os.path.abspath(__file__)) + '/data/rcpsp_default.data'
41with open(filename, 'r') as file:
42 NB_TASKS, NB_RESOURCES = [int(v) for v in file.readline().split()]
43 CAPACITIES = [int(v) for v in file.readline().split()]
44 TASKS = [[int(v) for v in file.readline().split()] for i in range(NB_TASKS)]
45
46
47#-----------------------------------------------------------------------------
48# Prepare the data for modeling
49#-----------------------------------------------------------------------------
50
51# Extract duration of each task
52DURATIONS = [TASKS[t][0] for t in range(NB_TASKS)]
53
54# Extract demand of each task
55DEMANDS = [TASKS[t][1:NB_RESOURCES+1] for t in range(NB_TASKS)]
56
57# Extract successors of each task
58SUCCESSORS = [TASKS[t][NB_RESOURCES+2:] for t in range(NB_TASKS)]
59
60
61#-----------------------------------------------------------------------------
62# Build the model
63#-----------------------------------------------------------------------------
64
65# Create model
66mdl = CpoModel()
67
68# Create task interval variables
69tasks = [interval_var(name='T{}'.format(i+1), size=DURATIONS[i]) for i in range(NB_TASKS)]
70
71# Add precedence constraints
72mdl.add(end_before_start(tasks[t], tasks[s-1]) for t in range(NB_TASKS) for s in SUCCESSORS[t])
73
74# Constrain capacity of resources
75mdl.add(sum(pulse(tasks[t], DEMANDS[t][r]) for t in range(NB_TASKS) if DEMANDS[t][r] > 0) <= CAPACITIES[r] for r in range(NB_RESOURCES))
76
77# Minimize end of all tasks
78mdl.add(minimize(max(end_of(t) for t in tasks)))
79
80
81#-----------------------------------------------------------------------------
82# Solve the model and display the result
83#-----------------------------------------------------------------------------
84
85# Solve model
86print('Solving model...')
87res = mdl.solve(FailLimit=100000,TimeLimit=10)
88print('Solution: ')
89res.print_solution()
90
91import docplex.cp.utils_visu as visu
92if res and visu.is_visu_enabled():
93 load = [CpoStepFunction() for j in range(NB_RESOURCES)]
94 for i in range(NB_TASKS):
95 itv = res.get_var_solution(tasks[i])
96 for j in range(NB_RESOURCES):
97 if 0 < DEMANDS[i][j]:
98 load[j].add_value(itv.get_start(), itv.get_end(), DEMANDS[i][j])
99
100 visu.timeline('Solution for RCPSP ' + filename)
101 visu.panel('Tasks')
102 for i in range(NB_TASKS):
103 visu.interval(res.get_var_solution(tasks[i]), i, tasks[i].get_name())
104 for j in range(NB_RESOURCES):
105 visu.panel('R' + str(j+1))
106 visu.function(segments=[(INTERVAL_MIN, INTERVAL_MAX, CAPACITIES[j])], style='area', color='lightgrey')
107 visu.function(segments=load[j], style='area', color=j)
108 visu.show()