00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038
00039
00040 #ifndef __GECODE_SCHEDULING_CUMULATIVE_HH__
00041 #define __GECODE_SCHEDULING_CUMULATIVE_HH__
00042
00043 #include <gecode/scheduling/task.hh>
00044 #include <gecode/scheduling/unary.hh>
00045
00059 namespace Gecode { namespace Scheduling { namespace Cumulative {
00060
00062 class ManFixPTask : public Unary::ManFixPTask {
00063 protected:
00065 int _c;
00066 public:
00068
00069
00070 ManFixPTask(void);
00072 ManFixPTask(IntVar s, int p, int c);
00074 void init(IntVar s, int p, int c);
00076 void init(const ManFixPTask& t);
00078
00080
00081
00082 int c(void) const;
00084 double e(void) const;
00086
00088
00089
00090 void update(Space& home, bool share, ManFixPTask& t);
00092
00093 };
00094
00099 template<class Char, class Traits>
00100 std::basic_ostream<Char,Traits>&
00101 operator <<(std::basic_ostream<Char,Traits>& os, const ManFixPTask& t);
00102
00104 class ManFixPSETask : public Unary::ManFixPSETask {
00105 protected:
00107 int _c;
00108 public:
00110
00111
00112 ManFixPSETask(void);
00120 ManFixPSETask(TaskType t, IntVar s, int p, int c);
00128 void init(TaskType t, IntVar s, int p, int c);
00130 void init(const ManFixPSETask& t);
00132
00134
00135
00136 int c(void) const;
00138 double e(void) const;
00140
00142
00143
00144 void update(Space& home, bool share, ManFixPSETask& t);
00146
00147 };
00148
00153 template<class Char, class Traits>
00154 std::basic_ostream<Char,Traits>&
00155 operator <<(std::basic_ostream<Char,Traits>& os, const ManFixPSETask& t);
00156
00158 class ManFlexTask : public Unary::ManFlexTask {
00159 protected:
00161 int _c;
00162 public:
00164
00165
00166 ManFlexTask(void);
00168 ManFlexTask(IntVar s, IntVar p, IntVar e, int c);
00170 void init(IntVar s, IntVar p, IntVar e, int c);
00172 void init(const ManFlexTask& t);
00174
00176
00177
00178 int c(void) const;
00180 double e(void) const;
00182
00184
00185
00186 void update(Space& home, bool share, ManFlexTask& t);
00188
00189 };
00190
00195 template<class Char, class Traits>
00196 std::basic_ostream<Char,Traits>&
00197 operator <<(std::basic_ostream<Char,Traits>& os, const ManFlexTask& t);
00198
00199
00201 class OptFixPTask : public ManToOptTask<ManFixPTask> {
00202 protected:
00203 using ManToOptTask<ManFixPTask>::_m;
00204 public:
00206
00207
00208 OptFixPTask(void);
00210 OptFixPTask(IntVar s, int p, int c, BoolVar m);
00212 void init(IntVar s, int p, int c, BoolVar m);
00214 };
00215
00220 template<class Char, class Traits>
00221 std::basic_ostream<Char,Traits>&
00222 operator <<(std::basic_ostream<Char,Traits>& os, const OptFixPTask& t);
00223
00225 class OptFixPSETask : public ManToOptTask<ManFixPSETask> {
00226 protected:
00227 using ManToOptTask<ManFixPSETask>::_m;
00228 public:
00230
00231
00232 OptFixPSETask(void);
00234 OptFixPSETask(TaskType t, IntVar s, int p, int c, BoolVar m);
00236 void init(TaskType t, IntVar s, int p, int c, BoolVar m);
00238 };
00239
00244 template<class Char, class Traits>
00245 std::basic_ostream<Char,Traits>&
00246 operator <<(std::basic_ostream<Char,Traits>& os, const OptFixPSETask& t);
00247
00249 class OptFlexTask : public ManToOptTask<ManFlexTask> {
00250 protected:
00251 using ManToOptTask<ManFlexTask>::_m;
00252 public:
00254
00255
00256 OptFlexTask(void);
00258 OptFlexTask(IntVar s, IntVar p, IntVar e, int c, BoolVar m);
00260 void init(IntVar s, IntVar p, IntVar e, int c, BoolVar m);
00262 };
00263
00268 template<class Char, class Traits>
00269 std::basic_ostream<Char,Traits>&
00270 operator <<(std::basic_ostream<Char,Traits>& os, const OptFlexTask& t);
00271
00272 }}}
00273
00274 #include <gecode/scheduling/cumulative/task.hpp>
00275
00276 namespace Gecode { namespace Scheduling { namespace Cumulative {
00277
00279 typedef ManFixPTask ManFixPTaskFwd;
00280
00282 typedef FwdToBwd<ManFixPTaskFwd> ManFixPTaskBwd;
00283
00285 typedef ManFixPSETask ManFixPSETaskFwd;
00286
00288 typedef FwdToBwd<ManFixPSETaskFwd> ManFixPSETaskBwd;
00289
00291 typedef OptFixPTask OptFixPTaskFwd;
00292
00294 typedef FwdToBwd<OptFixPTaskFwd> OptFixPTaskBwd;
00295
00297 typedef OptFixPSETask OptFixPSETaskFwd;
00298
00300 typedef FwdToBwd<OptFixPSETaskFwd> OptFixPSETaskBwd;
00301
00303 typedef ManFlexTask ManFlexTaskFwd;
00304
00306 typedef FwdToBwd<ManFlexTaskFwd> ManFlexTaskBwd;
00307
00309 typedef OptFlexTask OptFlexTaskFwd;
00310
00312 typedef FwdToBwd<OptFlexTaskFwd> OptFlexTaskBwd;
00313
00314
00319 template<class Char, class Traits>
00320 std::basic_ostream<Char,Traits>&
00321 operator <<(std::basic_ostream<Char,Traits>& os, const ManFixPTaskBwd& t);
00322
00327 template<class Char, class Traits>
00328 std::basic_ostream<Char,Traits>&
00329 operator <<(std::basic_ostream<Char,Traits>& os, const ManFixPSETaskBwd& t);
00330
00335 template<class Char, class Traits>
00336 std::basic_ostream<Char,Traits>&
00337 operator <<(std::basic_ostream<Char,Traits>& os, const OptFixPTaskBwd& t);
00338
00343 template<class Char, class Traits>
00344 std::basic_ostream<Char,Traits>&
00345 operator <<(std::basic_ostream<Char,Traits>& os, const OptFixPSETaskBwd& t);
00346
00347 }}}
00348
00349 #include <gecode/scheduling/cumulative/task-view.hpp>
00350
00351 namespace Gecode { namespace Scheduling {
00352
00354 template<>
00355 class TaskViewTraits<Cumulative::ManFixPTaskFwd> {
00356 public:
00358 typedef Cumulative::ManFixPTask Task;
00359 };
00360
00362 template<>
00363 class TaskViewTraits<Cumulative::ManFixPTaskBwd> {
00364 public:
00366 typedef Cumulative::ManFixPTask Task;
00367 };
00368
00370 template<>
00371 class TaskViewTraits<Cumulative::ManFixPSETaskFwd> {
00372 public:
00374 typedef Cumulative::ManFixPSETask Task;
00375 };
00376
00378 template<>
00379 class TaskViewTraits<Cumulative::ManFixPSETaskBwd> {
00380 public:
00382 typedef Cumulative::ManFixPSETask Task;
00383 };
00384
00386 template<>
00387 class TaskViewTraits<Cumulative::OptFixPTaskFwd> {
00388 public:
00390 typedef Cumulative::OptFixPTask Task;
00391 };
00392
00394 template<>
00395 class TaskViewTraits<Cumulative::OptFixPTaskBwd> {
00396 public:
00398 typedef Cumulative::OptFixPTask Task;
00399 };
00400
00402 template<>
00403 class TaskViewTraits<Cumulative::OptFixPSETaskFwd> {
00404 public:
00406 typedef Cumulative::OptFixPSETask Task;
00407 };
00408
00410 template<>
00411 class TaskViewTraits<Cumulative::OptFixPSETaskBwd> {
00412 public:
00414 typedef Cumulative::OptFixPSETask Task;
00415 };
00416
00418 template<>
00419 class TaskViewTraits<Cumulative::ManFlexTaskFwd> {
00420 public:
00422 typedef Cumulative::ManFlexTask Task;
00423 };
00424
00426 template<>
00427 class TaskViewTraits<Cumulative::ManFlexTaskBwd> {
00428 public:
00430 typedef Cumulative::ManFlexTask Task;
00431 };
00432
00434 template<>
00435 class TaskViewTraits<Cumulative::OptFlexTaskFwd> {
00436 public:
00438 typedef Cumulative::OptFlexTask Task;
00439 };
00440
00442 template<>
00443 class TaskViewTraits<Cumulative::OptFlexTaskBwd> {
00444 public:
00446 typedef Cumulative::OptFlexTask Task;
00447 };
00448
00449
00451 template<>
00452 class TaskTraits<Cumulative::ManFixPTask> {
00453 public:
00455 typedef Cumulative::ManFixPTaskFwd TaskViewFwd;
00457 typedef Cumulative::ManFixPTaskBwd TaskViewBwd;
00458 };
00459
00461 template<>
00462 class TaskTraits<Cumulative::ManFixPSETask> {
00463 public:
00465 typedef Cumulative::ManFixPSETaskFwd TaskViewFwd;
00467 typedef Cumulative::ManFixPSETaskBwd TaskViewBwd;
00468 };
00469
00471 template<>
00472 class TaskTraits<Cumulative::OptFixPTask> {
00473 public:
00475 typedef Cumulative::OptFixPTaskFwd TaskViewFwd;
00477 typedef Cumulative::OptFixPTaskBwd TaskViewBwd;
00479 typedef Cumulative::ManFixPTask ManTask;
00480 };
00481
00483 template<>
00484 class TaskTraits<Cumulative::OptFixPSETask> {
00485 public:
00487 typedef Cumulative::OptFixPSETaskFwd TaskViewFwd;
00489 typedef Cumulative::OptFixPSETaskBwd TaskViewBwd;
00491 typedef Cumulative::ManFixPSETask ManTask;
00492 };
00493
00495 template<>
00496 class TaskTraits<Cumulative::ManFlexTask> {
00497 public:
00499 typedef Cumulative::ManFlexTaskFwd TaskViewFwd;
00501 typedef Cumulative::ManFlexTaskBwd TaskViewBwd;
00502 };
00503
00505 template<>
00506 class TaskTraits<Cumulative::OptFlexTask> {
00507 public:
00509 typedef Cumulative::OptFlexTaskFwd TaskViewFwd;
00511 typedef Cumulative::OptFlexTaskBwd TaskViewBwd;
00513 typedef Cumulative::ManFlexTask ManTask;
00514 };
00515
00516 }}
00517
00518 namespace Gecode { namespace Scheduling { namespace Cumulative {
00519
00521 class OmegaNode {
00522 public:
00524 double e;
00526 double env;
00528 void init(const OmegaNode& l, const OmegaNode& r);
00530 void update(const OmegaNode& l, const OmegaNode& r);
00531 };
00532
00534 template<class TaskView>
00535 class OmegaTree : public TaskTree<TaskView,OmegaNode> {
00536 protected:
00537 using TaskTree<TaskView,OmegaNode>::tasks;
00538 using TaskTree<TaskView,OmegaNode>::leaf;
00539 using TaskTree<TaskView,OmegaNode>::root;
00540 using TaskTree<TaskView,OmegaNode>::init;
00541 using TaskTree<TaskView,OmegaNode>::update;
00543 int c;
00544 public:
00546 OmegaTree(Region& r, int c, const TaskViewArray<TaskView>& t);
00548 void insert(int i);
00550 void remove(int i);
00552 double env(void) const;
00553 };
00554
00556 class ExtOmegaNode : public OmegaNode {
00557 public:
00559 double cenv;
00561 void init(const ExtOmegaNode& l, const ExtOmegaNode& r);
00563 void update(const ExtOmegaNode& l, const ExtOmegaNode& r);
00564 };
00565
00567 template<class TaskView>
00568 class ExtOmegaTree : public TaskTree<TaskView,ExtOmegaNode> {
00569 protected:
00570 using TaskTree<TaskView,ExtOmegaNode>::tasks;
00571 using TaskTree<TaskView,ExtOmegaNode>::leaf;
00572 using TaskTree<TaskView,ExtOmegaNode>::root;
00573 using TaskTree<TaskView,ExtOmegaNode>::init;
00574 using TaskTree<TaskView,ExtOmegaNode>::update;
00575 using TaskTree<TaskView,ExtOmegaNode>::node;
00576 using TaskTree<TaskView,ExtOmegaNode>::n_leaf;
00577 using TaskTree<TaskView,ExtOmegaNode>::n_left;
00578 using TaskTree<TaskView,ExtOmegaNode>::left;
00579 using TaskTree<TaskView,ExtOmegaNode>::n_right;
00580 using TaskTree<TaskView,ExtOmegaNode>::right;
00581 using TaskTree<TaskView,ExtOmegaNode>::n_root;
00582 using TaskTree<TaskView,ExtOmegaNode>::n_parent;
00583 using TaskTree<TaskView,ExtOmegaNode>::n_nodes;
00584 using TaskTree<TaskView,ExtOmegaNode>::_leaf;
00586 int c, ci;
00587 public:
00589 template<class Node>
00590 ExtOmegaTree(Region& r, int c, const TaskTree<TaskView,Node>& t);
00592 void init(int ci);
00594 double env(int i);
00595 };
00596
00597
00599 class OmegaLambdaNode : public OmegaNode {
00600 public:
00602 static const int undef = -1;
00604 double le;
00606 double lenv;
00608 int resLe;
00610 int resLenv;
00612 void init(const OmegaLambdaNode& l, const OmegaLambdaNode& r);
00614 void update(const OmegaLambdaNode& l, const OmegaLambdaNode& r);
00615 };
00616
00618 template<class TaskView>
00619 class OmegaLambdaTree : public TaskTree<TaskView,OmegaLambdaNode> {
00620 protected:
00621 using TaskTree<TaskView,OmegaLambdaNode>::tasks;
00622 using TaskTree<TaskView,OmegaLambdaNode>::leaf;
00623 using TaskTree<TaskView,OmegaLambdaNode>::root;
00624 using TaskTree<TaskView,OmegaLambdaNode>::init;
00625 using TaskTree<TaskView,OmegaLambdaNode>::update;
00627 int c;
00628 public:
00630 OmegaLambdaTree(Region& r, int c, const TaskViewArray<TaskView>& t);
00632 void shift(int i);
00634 void lremove(int i);
00636 bool lempty(void) const;
00638 int responsible(void) const;
00640 double env(void) const;
00642 double lenv(void) const;
00643 };
00644
00645 }}}
00646
00647 #include <gecode/scheduling/cumulative/tree.hpp>
00648
00649 namespace Gecode { namespace Scheduling { namespace Cumulative {
00650
00652 template<class Task>
00653 ExecStatus basic(Space& home, Propagator& p, int c, TaskArray<Task>& t);
00654
00656 template<class ManTask>
00657 ExecStatus overload(Space& home, int c, TaskArray<ManTask>& t);
00658
00660 template<class Task>
00661 ExecStatus edgefinding(Space& home, int c, TaskArray<Task>& t);
00662
00669 template<class ManTask>
00670 class ManProp : public TaskProp<ManTask,Int::PC_INT_DOM> {
00671 protected:
00672 using TaskProp<ManTask,Int::PC_INT_DOM>::t;
00674 int c;
00676 ManProp(Home home, int c, TaskArray<ManTask>& t);
00678 ManProp(Space& home, bool shared, ManProp& p);
00679 public:
00681 virtual Actor* copy(Space& home, bool share);
00683 virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
00685 static ExecStatus post(Home home, int c, TaskArray<ManTask>& t);
00687 virtual size_t dispose(Space& home);
00688 };
00689
00696 template<class OptTask>
00697 class OptProp : public TaskProp<OptTask,Int::PC_INT_DOM> {
00698 protected:
00699 using TaskProp<OptTask,Int::PC_INT_DOM>::t;
00701 int c;
00703 OptProp(Home home, int c, TaskArray<OptTask>& t);
00705 OptProp(Space& home, bool shared, OptProp& p);
00706 public:
00708 virtual Actor* copy(Space& home, bool share);
00710 virtual ExecStatus propagate(Space& home, const ModEventDelta& med);
00712 static ExecStatus post(Home home, int c, TaskArray<OptTask>& t);
00714 virtual size_t dispose(Space& home);
00715 };
00716
00717 }}}
00718
00719 #include <gecode/scheduling/cumulative/basic.hpp>
00720 #include <gecode/scheduling/cumulative/overload.hpp>
00721 #include <gecode/scheduling/cumulative/edge-finding.hpp>
00722 #include <gecode/scheduling/cumulative/man-prop.hpp>
00723 #include <gecode/scheduling/cumulative/opt-prop.hpp>
00724
00725 #endif
00726
00727