this repo has no description
dekker.one
1/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2/*
3 * Main authors:
4 * Christian Schulte <schulte@gecode.org>
5 * Guido Tack <tack@gecode.org>
6 *
7 * Copyright:
8 * Christian Schulte, 2009
9 * Guido Tack, 2010
10 *
11 * This file is part of Gecode, the generic constraint
12 * development environment:
13 * http://www.gecode.org
14 *
15 * Permission is hereby granted, free of charge, to any person obtaining
16 * a copy of this software and associated documentation files (the
17 * "Software"), to deal in the Software without restriction, including
18 * without limitation the rights to use, copy, modify, merge, publish,
19 * distribute, sublicense, and/or sell copies of the Software, and to
20 * permit persons to whom the Software is furnished to do so, subject to
21 * the following conditions:
22 *
23 * The above copyright notice and this permission notice shall be
24 * included in all copies or substantial portions of the Software.
25 *
26 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
27 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
28 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
29 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
30 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
31 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
32 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
33 *
34 */
35
36#ifndef GECODE_INT_CUMULATIVE_HH
37#define GECODE_INT_CUMULATIVE_HH
38
39#include <gecode/int/task.hh>
40#include <gecode/int/unary.hh>
41
42/**
43 * \namespace Gecode::Int::Cumulative
44 *
45 * The edge-finding and overload-checking algorithms and data structures
46 * follow (mostly):
47 * Petr Vilím, Max Energy Filtering Algorithm for Discrete
48 * Cumulative Resources, CP-AI-OR, 2009.
49 * Petr Vilím, Edge Finding Filtering Algorithm for Discrete
50 * Cumulative Resources in O(kn log n), CP, 2009.
51 *
52 * \brief %Scheduling for cumulative resources
53 */
54
55namespace Gecode { namespace Int { namespace Cumulative {
56
57 /// Throw exception if multiplication of \a x and \a y overflows
58 void mul_check(long long int x, long long int y);
59
60 /// Throw exception if multiplication of \a x, \a y, and \a z overflows
61 void mul_check(long long int x, long long int y, long long int z);
62
63}}}
64
65#include <gecode/int/cumulative/limits.hpp>
66
67namespace Gecode { namespace Int { namespace Cumulative {
68
69 /// Cumulative (mandatory) task with fixed processing time
70 class ManFixPTask : public Unary::ManFixPTask {
71 protected:
72 /// Required capacity
73 int _c;
74 public:
75 /// \name Constructors and initialization
76 //@{
77 /// Default constructor
78 ManFixPTask(void);
79 /// Initialize task with start time \a s, processing time \a p, and required resource \a c
80 ManFixPTask(IntVar s, int p, int c);
81 /// Initialize task with start time \a s, processing time \a p, and required resource \a c
82 void init(IntVar s, int p, int c);
83 /// Initialize from task \a t
84 void init(const ManFixPTask& t);
85 //@}
86
87 /// \name Value access
88 //@{
89 /// Return required capacity
90 int c(void) const;
91 /// Return required energy
92 long long int e(void) const;
93 //@}
94
95 /// \name Cloning
96 //@{
97 /// Update this task to be a clone of task \a t
98 void update(Space& home, ManFixPTask& t);
99 //@}
100
101 };
102
103 /**
104 * \brief Print task in format est:[p,c]:lct
105 * \relates ManFixPTask
106 */
107 template<class Char, class Traits>
108 std::basic_ostream<Char,Traits>&
109 operator <<(std::basic_ostream<Char,Traits>& os, const ManFixPTask& t);
110
111 /// Cumulative (mandatory) task with fixed processing, start or end time
112 class ManFixPSETask : public Unary::ManFixPSETask {
113 protected:
114 /// Required capacity
115 int _c;
116 public:
117 /// \name Constructors and initialization
118 //@{
119 /// Default constructor
120 ManFixPSETask(void);
121 /**
122 * \brief Initialize task
123 *
124 * Depending on \a t, \a s is either the end time (if \a t is FIXS)
125 * or the start time of the task, \a p is the fixed parameter,
126 * and \a c is the required capacity.
127 */
128 ManFixPSETask(TaskType t, IntVar s, int p, int c);
129 /**
130 * \brief Initialize task
131 *
132 * Depending on \a t, \a s is either the end time (if \a t is FIXS)
133 * or the start time of the task, \a p is the fixed parameter,
134 * and \a c is the required capacity.
135 */
136 void init(TaskType t, IntVar s, int p, int c);
137 /// Initialize from task \a t
138 void init(const ManFixPSETask& t);
139 //@}
140
141 /// \name Value access
142 //@{
143 /// Return required capacity
144 int c(void) const;
145 /// Return required energy
146 long long int e(void) const;
147 //@}
148
149 /// \name Cloning
150 //@{
151 /// Update this task to be a clone of task \a t
152 void update(Space& home, ManFixPSETask& t);
153 //@}
154
155 };
156
157 /**
158 * \brief Print task in format est:[p,c]:lct
159 * \relates ManFixPSETask
160 */
161 template<class Char, class Traits>
162 std::basic_ostream<Char,Traits>&
163 operator <<(std::basic_ostream<Char,Traits>& os, const ManFixPSETask& t);
164
165 /// Cumulative (mandatory) task with flexible processing time
166 class ManFlexTask : public Unary::ManFlexTask {
167 protected:
168 /// Required capacity
169 int _c;
170 public:
171 /// \name Constructors and initialization
172 //@{
173 /// Default constructor
174 ManFlexTask(void);
175 /// Initialize with start time \a s, processing time \a p, end time \a e
176 ManFlexTask(IntVar s, IntVar p, IntVar e, int c);
177 /// Initialize with start time \a s, processing time \a p, end time \a e
178 void init(IntVar s, IntVar p, IntVar e, int c);
179 /// Initialize from task \a t
180 void init(const ManFlexTask& t);
181 //@}
182
183 /// \name Value access
184 //@{
185 /// Return required capacity
186 int c(void) const;
187 /// Return required energy
188 long long int e(void) const;
189 //@}
190
191 /// \name Cloning
192 //@{
193 /// Update this task to be a clone of task \a t
194 void update(Space& home, ManFlexTask& t);
195 //@}
196
197 };
198
199 /**
200 * \brief Print task in format est:[p,c]:lct
201 * \relates ManFlexTask
202 */
203 template<class Char, class Traits>
204 std::basic_ostream<Char,Traits>&
205 operator <<(std::basic_ostream<Char,Traits>& os, const ManFlexTask& t);
206
207
208 /// Cumulative optional task with fixed processing time
209 class OptFixPTask : public ManToOptTask<ManFixPTask> {
210 protected:
211 using ManToOptTask<ManFixPTask>::_m;
212 public:
213 /// \name Constructors and initialization
214 //@{
215 /// Default constructor
216 OptFixPTask(void);
217 /// Initialize with start time \a s, processing time \a p, required capacity \a c, and mandatory flag \a m
218 OptFixPTask(IntVar s, int p, int c, BoolVar m);
219 /// Initialize with start time \a s, processing time \a p, required capacity \a c, and mandatory flag \a m
220 void init(IntVar s, int p, int c, BoolVar m);
221 //@}
222 /// Cast to corresponding unary task
223 operator Unary::OptFixPTask (void);
224 };
225
226 /**
227 * \brief Print optional task in format est:[p,c]:lct:m
228 * \relates OptFixPTask
229 */
230 template<class Char, class Traits>
231 std::basic_ostream<Char,Traits>&
232 operator <<(std::basic_ostream<Char,Traits>& os, const OptFixPTask& t);
233
234 /// Cumulative optional task with fixed processing, start or end time
235 class OptFixPSETask : public ManToOptTask<ManFixPSETask> {
236 protected:
237 using ManToOptTask<ManFixPSETask>::_m;
238 public:
239 /// \name Constructors and initialization
240 //@{
241 /// Default constructor
242 OptFixPSETask(void);
243 /// Initialize with start time \a s, processing time \a p, required capacity \a c, and mandatory flag \a m
244 OptFixPSETask(TaskType t, IntVar s, int p, int c, BoolVar m);
245 /// Initialize with start time \a s, processing time \a p, required capacity \a c, and mandatory flag \a m
246 void init(TaskType t, IntVar s, int p, int c, BoolVar m);
247 //@}
248 /// Cast to corresponding unary task
249 operator Unary::OptFixPSETask (void);
250 };
251
252 /**
253 * \brief Print optional task in format est:[p,c]:lct:m
254 * \relates OptFixPSETask
255 */
256 template<class Char, class Traits>
257 std::basic_ostream<Char,Traits>&
258 operator <<(std::basic_ostream<Char,Traits>& os, const OptFixPSETask& t);
259
260 /// %Cumulative optional task with flexible processing time
261 class OptFlexTask : public ManToOptTask<ManFlexTask> {
262 protected:
263 using ManToOptTask<ManFlexTask>::_m;
264 public:
265 /// \name Constructors and initialization
266 //@{
267 /// Default constructor
268 OptFlexTask(void);
269 /// Initialize with start time \a s, processing time \a p, end time \a e, and mandatory flag \a m
270 OptFlexTask(IntVar s, IntVar p, IntVar e, int c, BoolVar m);
271 /// Initialize with start time \a s, processing time \a p, end time \a e, and mandatory flag \a m
272 void init(IntVar s, IntVar p, IntVar e, int c, BoolVar m);
273 //@}
274 /// Cast to corresponding unary task
275 operator Unary::OptFlexTask (void);
276 };
277
278 /**
279 * \brief Print optional task in format est:lst:pmin:pmax:c:ect:lct:m
280 * \relates OptFlexTask
281 */
282 template<class Char, class Traits>
283 std::basic_ostream<Char,Traits>&
284 operator <<(std::basic_ostream<Char,Traits>& os, const OptFlexTask& t);
285
286}}}
287
288#include <gecode/int/cumulative/task.hpp>
289
290namespace Gecode { namespace Int { namespace Cumulative {
291
292 /// Forward mandatory fixed task view
293 typedef ManFixPTask ManFixPTaskFwd;
294
295 /// Backward (dual) mandatory fixed task view
296 typedef FwdToBwd<ManFixPTaskFwd> ManFixPTaskBwd;
297
298 /// Forward mandatory fixed task view
299 typedef ManFixPSETask ManFixPSETaskFwd;
300
301 /// Backward (dual) mandatory fixed task view
302 typedef FwdToBwd<ManFixPSETaskFwd> ManFixPSETaskBwd;
303
304 /// Forward optional fixed task view
305 typedef OptFixPTask OptFixPTaskFwd;
306
307 /// Backward (dual) optional fixed task view
308 typedef FwdToBwd<OptFixPTaskFwd> OptFixPTaskBwd;
309
310 /// Forward optional fixed task view
311 typedef OptFixPSETask OptFixPSETaskFwd;
312
313 /// Backward (dual) optional fixed task view
314 typedef FwdToBwd<OptFixPSETaskFwd> OptFixPSETaskBwd;
315
316 /// Forward mandatory flexible task view
317 typedef ManFlexTask ManFlexTaskFwd;
318
319 /// Backward (dual) mandatory flexible task view
320 typedef FwdToBwd<ManFlexTaskFwd> ManFlexTaskBwd;
321
322 /// Forward optional flexible task view
323 typedef OptFlexTask OptFlexTaskFwd;
324
325 /// Backward (dual) optional flexible task view
326 typedef FwdToBwd<OptFlexTaskFwd> OptFlexTaskBwd;
327
328
329 /**
330 * \brief Print backward task view in format est:p:lct
331 * \relates ManFixPTaskBwd
332 */
333 template<class Char, class Traits>
334 std::basic_ostream<Char,Traits>&
335 operator <<(std::basic_ostream<Char,Traits>& os, const ManFixPTaskBwd& t);
336
337 /**
338 * \brief Print backward task view in format est:p:lct
339 * \relates ManFixPSETaskBwd
340 */
341 template<class Char, class Traits>
342 std::basic_ostream<Char,Traits>&
343 operator <<(std::basic_ostream<Char,Traits>& os, const ManFixPSETaskBwd& t);
344
345 /**
346 * \brief Print optional backward task view in format est:p:lct:m
347 * \relates OptFixPTaskBwd
348 */
349 template<class Char, class Traits>
350 std::basic_ostream<Char,Traits>&
351 operator <<(std::basic_ostream<Char,Traits>& os, const OptFixPTaskBwd& t);
352
353 /**
354 * \brief Print optional backward task view in format est:p:lct:m
355 * \relates OptFixPSETaskBwd
356 */
357 template<class Char, class Traits>
358 std::basic_ostream<Char,Traits>&
359 operator <<(std::basic_ostream<Char,Traits>& os, const OptFixPSETaskBwd& t);
360
361}}}
362
363#include <gecode/int/cumulative/task-view.hpp>
364
365namespace Gecode { namespace Int {
366
367 /// Task view traits for forward task views
368 template<>
369 class TaskViewTraits<Cumulative::ManFixPTaskFwd> {
370 public:
371 /// The task type
372 typedef Cumulative::ManFixPTask Task;
373 };
374
375 /// Task view traits for backward task views
376 template<>
377 class TaskViewTraits<Cumulative::ManFixPTaskBwd> {
378 public:
379 /// The task type
380 typedef Cumulative::ManFixPTask Task;
381 };
382
383 /// Task view traits for forward task views
384 template<>
385 class TaskViewTraits<Cumulative::ManFixPSETaskFwd> {
386 public:
387 /// The task type
388 typedef Cumulative::ManFixPSETask Task;
389 };
390
391 /// Task view traits for backward task views
392 template<>
393 class TaskViewTraits<Cumulative::ManFixPSETaskBwd> {
394 public:
395 /// The task type
396 typedef Cumulative::ManFixPSETask Task;
397 };
398
399 /// Task view traits for forward optional task views
400 template<>
401 class TaskViewTraits<Cumulative::OptFixPTaskFwd> {
402 public:
403 /// The task type
404 typedef Cumulative::OptFixPTask Task;
405 };
406
407 /// Task view traits for backward task views
408 template<>
409 class TaskViewTraits<Cumulative::OptFixPTaskBwd> {
410 public:
411 /// The task type
412 typedef Cumulative::OptFixPTask Task;
413 };
414
415 /// Task view traits for forward optional task views
416 template<>
417 class TaskViewTraits<Cumulative::OptFixPSETaskFwd> {
418 public:
419 /// The task type
420 typedef Cumulative::OptFixPSETask Task;
421 };
422
423 /// Task view traits for backward task views
424 template<>
425 class TaskViewTraits<Cumulative::OptFixPSETaskBwd> {
426 public:
427 /// The task type
428 typedef Cumulative::OptFixPSETask Task;
429 };
430
431 /// Task view traits for forward task views
432 template<>
433 class TaskViewTraits<Cumulative::ManFlexTaskFwd> {
434 public:
435 /// The task type
436 typedef Cumulative::ManFlexTask Task;
437 };
438
439 /// Task view traits for backward task views
440 template<>
441 class TaskViewTraits<Cumulative::ManFlexTaskBwd> {
442 public:
443 /// The task type
444 typedef Cumulative::ManFlexTask Task;
445 };
446
447 /// Task view traits for forward optional task views
448 template<>
449 class TaskViewTraits<Cumulative::OptFlexTaskFwd> {
450 public:
451 /// The task type
452 typedef Cumulative::OptFlexTask Task;
453 };
454
455 /// Task view traits for backward task views
456 template<>
457 class TaskViewTraits<Cumulative::OptFlexTaskBwd> {
458 public:
459 /// The task type
460 typedef Cumulative::OptFlexTask Task;
461 };
462
463
464 /// Task traits for mandatory fixed tasks
465 template<>
466 class TaskTraits<Cumulative::ManFixPTask> {
467 public:
468 /// The forward task view type
469 typedef Cumulative::ManFixPTaskFwd TaskViewFwd;
470 /// The backward task view type
471 typedef Cumulative::ManFixPTaskBwd TaskViewBwd;
472 /// The corresponding unary task type
473 typedef Unary::ManFixPTask UnaryTask;
474 };
475
476 /// Task traits for mandatory fixed tasks
477 template<>
478 class TaskTraits<Cumulative::ManFixPSETask> {
479 public:
480 /// The forward task view type
481 typedef Cumulative::ManFixPSETaskFwd TaskViewFwd;
482 /// The backward task view type
483 typedef Cumulative::ManFixPSETaskBwd TaskViewBwd;
484 /// The corresponding unary task type
485 typedef Unary::ManFixPSETask UnaryTask;
486 };
487
488 /// Task traits for optional fixed tasks
489 template<>
490 class TaskTraits<Cumulative::OptFixPTask> {
491 public:
492 /// The forward task view type
493 typedef Cumulative::OptFixPTaskFwd TaskViewFwd;
494 /// The backward task view type
495 typedef Cumulative::OptFixPTaskBwd TaskViewBwd;
496 /// The corresponding mandatory task
497 typedef Cumulative::ManFixPTask ManTask;
498 /// The corresponding unary task type
499 typedef Unary::OptFixPTask UnaryTask;
500 };
501
502 /// Task traits for optional fixed tasks
503 template<>
504 class TaskTraits<Cumulative::OptFixPSETask> {
505 public:
506 /// The forward task view type
507 typedef Cumulative::OptFixPSETaskFwd TaskViewFwd;
508 /// The backward task view type
509 typedef Cumulative::OptFixPSETaskBwd TaskViewBwd;
510 /// The corresponding mandatory task
511 typedef Cumulative::ManFixPSETask ManTask;
512 /// The corresponding unary task type
513 typedef Unary::OptFixPSETask UnaryTask;
514 };
515
516 /// Task traits for mandatory flexible tasks
517 template<>
518 class TaskTraits<Cumulative::ManFlexTask> {
519 public:
520 /// The forward task view type
521 typedef Cumulative::ManFlexTaskFwd TaskViewFwd;
522 /// The backward task view type
523 typedef Cumulative::ManFlexTaskBwd TaskViewBwd;
524 /// The corresponding unary task type
525 typedef Unary::ManFlexTask UnaryTask;
526 };
527
528 /// Task traits for optional flexible tasks
529 template<>
530 class TaskTraits<Cumulative::OptFlexTask> {
531 public:
532 /// The forward task view type
533 typedef Cumulative::OptFlexTaskFwd TaskViewFwd;
534 /// The backward task view type
535 typedef Cumulative::OptFlexTaskBwd TaskViewBwd;
536 /// The corresponding mandatory task
537 typedef Cumulative::ManFlexTask ManTask;
538 /// The corresponding unary task type
539 typedef Unary::OptFlexTask UnaryTask;
540 };
541
542}}
543
544namespace Gecode { namespace Int { namespace Cumulative {
545
546 /// Node for an omega tree
547 class OmegaNode {
548 public:
549 /// Energy for subtree
550 long long int e;
551 /// Energy envelope for subtree
552 long long int env;
553 /// Initialize node from left child \a l and right child \a r
554 void init(const OmegaNode& l, const OmegaNode& r);
555 /// Update node from left child \a l and right child \a r
556 void update(const OmegaNode& l, const OmegaNode& r);
557 };
558
559 /// Omega trees for computing ect of task sets
560 template<class TaskView>
561 class OmegaTree : public TaskTree<TaskView,OmegaNode> {
562 protected:
563 using TaskTree<TaskView,OmegaNode>::tasks;
564 using TaskTree<TaskView,OmegaNode>::leaf;
565 using TaskTree<TaskView,OmegaNode>::root;
566 using TaskTree<TaskView,OmegaNode>::init;
567 using TaskTree<TaskView,OmegaNode>::update;
568 /// Capacity
569 int c;
570 public:
571 /// Initialize tree for tasks \a t and capacity \a c
572 OmegaTree(Region& r, int c, const TaskViewArray<TaskView>& t);
573 /// Insert task with index \a i
574 void insert(int i);
575 /// Remove task with index \a i
576 void remove(int i);
577 /// Return energy envelope of all tasks
578 long long int env(void) const;
579 };
580
581 /// Node for an extended omega tree
582 class ExtOmegaNode : public OmegaNode {
583 public:
584 /// Energy envelope for subtree
585 long long int cenv;
586 /// Initialize node from left child \a l and right child \a r
587 void init(const ExtOmegaNode& l, const ExtOmegaNode& r);
588 /// Update node from left child \a l and right child \a r
589 void update(const ExtOmegaNode& l, const ExtOmegaNode& r);
590 };
591
592 /// Omega trees for computing ect of task sets
593 template<class TaskView>
594 class ExtOmegaTree : public TaskTree<TaskView,ExtOmegaNode> {
595 protected:
596 using TaskTree<TaskView,ExtOmegaNode>::tasks;
597 using TaskTree<TaskView,ExtOmegaNode>::leaf;
598 using TaskTree<TaskView,ExtOmegaNode>::root;
599 using TaskTree<TaskView,ExtOmegaNode>::init;
600 using TaskTree<TaskView,ExtOmegaNode>::update;
601 using TaskTree<TaskView,ExtOmegaNode>::node;
602 using TaskTree<TaskView,ExtOmegaNode>::n_leaf;
603 using TaskTree<TaskView,ExtOmegaNode>::n_left;
604 using TaskTree<TaskView,ExtOmegaNode>::left;
605 using TaskTree<TaskView,ExtOmegaNode>::n_right;
606 using TaskTree<TaskView,ExtOmegaNode>::right;
607 using TaskTree<TaskView,ExtOmegaNode>::n_root;
608 using TaskTree<TaskView,ExtOmegaNode>::n_parent;
609 using TaskTree<TaskView,ExtOmegaNode>::n_nodes;
610 using TaskTree<TaskView,ExtOmegaNode>::_leaf;
611 /// Capacity
612 int c, ci;
613 public:
614 /// Initialize tree for tasks \a t and capacity \a c
615 template<class Node>
616 ExtOmegaTree(Region& r, int c, const TaskTree<TaskView,Node>& t);
617 /// Initialize tasks for current capacity \a ci
618 void init(int ci);
619 /// Compute update for task with index \a i
620 long long int env(int i);
621 };
622
623
624 /// Node for an omega lambda tree
625 class OmegaLambdaNode : public OmegaNode {
626 public:
627 /// Undefined task
628 static const int undef = -1;
629 /// Energy for subtree
630 long long int le;
631 /// Energy envelope for subtree
632 long long int lenv;
633 /// Node which is responsible for le
634 int resLe;
635 /// Node which is responsible for lenv
636 int resLenv;
637 /// Initialize node from left child \a l and right child \a r
638 void init(const OmegaLambdaNode& l, const OmegaLambdaNode& r);
639 /// Update node from left child \a l and right child \a r
640 void update(const OmegaLambdaNode& l, const OmegaLambdaNode& r);
641 };
642
643 /// Omega-lambda trees for computing ect of task sets
644 template<class TaskView>
645 class OmegaLambdaTree : public TaskTree<TaskView,OmegaLambdaNode> {
646 protected:
647 using TaskTree<TaskView,OmegaLambdaNode>::tasks;
648 using TaskTree<TaskView,OmegaLambdaNode>::leaf;
649 using TaskTree<TaskView,OmegaLambdaNode>::root;
650 using TaskTree<TaskView,OmegaLambdaNode>::init;
651 using TaskTree<TaskView,OmegaLambdaNode>::update;
652 /// Capacity
653 int c;
654 public:
655 /// Initialize tree for tasks \a t and capcity \a c with all tasks included in omega
656 OmegaLambdaTree(Region& r, int c, const TaskViewArray<TaskView>& t);
657 /// Shift task with index \a i from omega to lambda
658 void shift(int i);
659 /// Remove task with index \a i from lambda
660 void lremove(int i);
661 /// Whether has responsible task
662 bool lempty(void) const;
663 /// Return responsible task
664 int responsible(void) const;
665 /// Return energy envelope of all tasks
666 long long int env(void) const;
667 /// Return energy envelope of all tasks excluding lambda tasks
668 long long int lenv(void) const;
669 };
670
671}}}
672
673#include <gecode/int/cumulative/tree.hpp>
674
675namespace Gecode { namespace Int { namespace Cumulative {
676
677 /// Check for subsumption (all tasks must be assigned)
678 template<class Task>
679 ExecStatus
680 subsumed(Space& home, Propagator& p, int c, TaskArray<Task>& t);
681
682 /// Check mandatory tasks \a t for overload
683 template<class ManTask>
684 ExecStatus overload(Space& home, int c, TaskArray<ManTask>& t);
685
686 /// Perform time-tabling propagation
687 template<class Task, class Cap>
688 ExecStatus timetabling(Space& home, Propagator& p, Cap c,
689 TaskArray<Task>& t);
690
691 /// Propagate by edge-finding
692 template<class Task>
693 ExecStatus edgefinding(Space& home, int c, TaskArray<Task>& t);
694
695 /**
696 * \brief Scheduling propagator for cumulative resource with mandatory tasks
697 *
698 * Requires \code #include <gecode/int/cumulative.hh> \endcode
699 * \ingroup FuncIntProp
700 */
701 template<class ManTask, class Cap, class PL>
702 class ManProp : public TaskProp<ManTask,PL> {
703 protected:
704 using TaskProp<ManTask,PL>::t;
705 /// Resource capacity
706 Cap c;
707 /// Constructor for creation
708 ManProp(Home home, Cap c, TaskArray<ManTask>& t);
709 /// Constructor for cloning \a p
710 ManProp(Space& home, ManProp& p);
711 public:
712 /// Perform copying during cloning
713 virtual Actor* copy(Space& home);
714 /// Perform propagation
715 virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
716 /// Post propagator that schedules tasks on cumulative resource
717 static ExecStatus post(Home home, Cap c, TaskArray<ManTask>& t);
718 /// Delete propagator and return its size
719 virtual size_t dispose(Space& home);
720 };
721
722 /**
723 * \brief Scheduling propagator for cumulative resource with optional tasks
724 *
725 * Requires \code #include <gecode/int/cumulative.hh> \endcode
726 * \ingroup FuncIntProp
727 */
728 template<class OptTask, class Cap, class PL>
729 class OptProp : public TaskProp<OptTask,PL> {
730 protected:
731 using TaskProp<OptTask,PL>::t;
732 /// Resource capacity
733 Cap c;
734 /// Constructor for creation
735 OptProp(Home home, Cap c, TaskArray<OptTask>& t);
736 /// Constructor for cloning \a p
737 OptProp(Space& home, OptProp& p);
738 public:
739 /// Perform copying during cloning
740 virtual Actor* copy(Space& home);
741 /// Perform propagation
742 virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
743 /// Post propagator that schedules tasks on cumulative resource
744 static ExecStatus post(Home home, Cap c, TaskArray<OptTask>& t);
745 /// Delete propagator and return its size
746 virtual size_t dispose(Space& home);
747 };
748
749 /// Post mandatory task propagator according to propagation level
750 template<class ManTask, class Cap>
751 ExecStatus
752 cmanpost(Home home, Cap c, TaskArray<ManTask>& t, IntPropLevel ipl);
753
754 /// Post optional task propagator according to propagation level
755 template<class OptTask, class Cap>
756 ExecStatus
757 coptpost(Home home, Cap c, TaskArray<OptTask>& t, IntPropLevel ipl);
758
759}}}
760
761#include <gecode/int/cumulative/time-tabling.hpp>
762#include <gecode/int/cumulative/subsumption.hpp>
763#include <gecode/int/cumulative/overload.hpp>
764#include <gecode/int/cumulative/edge-finding.hpp>
765#include <gecode/int/cumulative/man-prop.hpp>
766#include <gecode/int/cumulative/opt-prop.hpp>
767#include <gecode/int/cumulative/post.hpp>
768
769#endif
770
771// STATISTICS: int-prop