45 return containingOp->emitError(
"problem does not include last operation");
47 CpModelBuilder cpModel;
50 DenseMap<Operation *, IntVar> taskStarts;
51 DenseMap<Operation *, IntVar> taskEnds;
52 DenseMap<Problem::ResourceType, SmallVector<IntervalVar, 4>>
53 resourcesToTaskIntervals;
58 for (
auto *task : tasks) {
69 for (
auto item : llvm::enumerate(tasks)) {
70 auto i = item.index();
71 auto *task = item.value();
72 IntVar startVar = cpModel.NewIntVar(Domain(0, horizon))
73 .WithName((Twine(
"start_of_task_") + Twine(i)).str());
74 IntVar endVar = cpModel.NewIntVar(Domain(0, horizon))
75 .WithName((Twine(
"end_of_task_") + Twine(i)).str());
76 taskStarts[task] = startVar;
77 taskEnds[task] = endVar;
80 IntervalVar taskInterval =
81 cpModel.NewIntervalVar(startVar, duration, endVar)
82 .WithName((Twine(
"task_interval_") + Twine(i)).str());
85 if (resourceListOpt) {
86 for (
const auto &resource : *resourceListOpt) {
87 if (
auto limitOpt = prob.
getLimit(resource))
88 resourcesToTaskIntervals[resource].push_back(taskInterval);
95 for (Operation *task : tasks) {
97 Operation *src = dep.getSource();
98 Operation *dst = dep.getDestination();
100 return containingOp->emitError() <<
"dependence cycle detected";
101 cpModel.AddLessOrEqual(taskEnds[src], taskStarts[dst]);
107 for (
auto resourceToTaskIntervals : resourcesToTaskIntervals) {
109 auto capacity = prob.
getLimit(resource);
110 SmallVector<IntervalVar, 4> &taskIntervals =
111 resourceToTaskIntervals.getSecond();
118 CumulativeConstraint cumu = cpModel.AddCumulative(capacity.value());
119 for (
const auto &item : llvm::enumerate(taskIntervals)) {
120 auto i = item.index();
121 auto taskInterval = item.value();
122 IntVar demandVar = cpModel.NewIntVar(Domain(1)).WithName(
123 (Twine(
"demand_") + Twine(i) + Twine(
"_") +
124 Twine(resource.
getAttr().strref()))
129 cpModel.NewFixedSizeIntervalVar(taskInterval.StartExpr(), 1);
130 cumu.AddDemand(start, demandVar);
134 cpModel.Minimize(taskEnds[lastOp]);
138 int numSolutions = 0;
139 model.Add(NewFeasibleSolutionObserver([&](
const CpSolverResponse &r) {
140 LLVM_DEBUG(dbgs() <<
"Solution " << numSolutions <<
'\n');
141 LLVM_DEBUG(dbgs() <<
"Solution status" << r.status() <<
'\n');
145 LLVM_DEBUG(dbgs() <<
"Starting solver\n");
146 const CpSolverResponse response = SolveCpModel(cpModel.Build(), &model);
148 if (response.status() == CpSolverStatus::OPTIMAL ||
149 response.status() == CpSolverStatus::FEASIBLE) {
150 for (
auto *task : tasks)
151 prob.
setStartTime(task, SolutionIntegerValue(response, taskStarts[task]));
155 return containingOp->emitError() <<
"infeasible";