00001 /*************************************************************************** 00002 file : $URL: https://frepple.svn.sourceforge.net/svnroot/frepple/trunk/include/frepple/solver.h $ 00003 version : $LastChangedRevision: 1001 $ $LastChangedBy: jdetaeye $ 00004 date : $LastChangedDate: 2009-07-30 18:21:45 +0200 (Thu, 30 Jul 2009) $ 00005 ***************************************************************************/ 00006 00007 /*************************************************************************** 00008 * * 00009 * Copyright (C) 2007 by Johan De Taeye * 00010 * * 00011 * This library is free software; you can redistribute it and/or modify it * 00012 * under the terms of the GNU Lesser General Public License as published * 00013 * by the Free Software Foundation; either version 2.1 of the License, or * 00014 * (at your option) any later version. * 00015 * * 00016 * This library is distributed in the hope that it will be useful, * 00017 * but WITHOUT ANY WARRANTY; without even the implied warranty of * 00018 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser * 00019 * General Public License for more details. * 00020 * * 00021 * You should have received a copy of the GNU Lesser General Public * 00022 * License along with this library; if not, write to the Free Software * 00023 * Foundation Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307, USA * 00024 * * 00025 ***************************************************************************/ 00026 00027 #ifndef SOLVER_H 00028 #define SOLVER_H 00029 00030 #include "frepple/model.h" 00031 #include <deque> 00032 #include <cmath> 00033 00034 namespace frepple 00035 { 00036 00037 /** @brief This solver implements a heuristic algorithm for planning demands. 00038 * 00039 * One by one the demands are processed. The demand will consume step by step 00040 * any upstream materials, respecting all constraints on its path.<br> 00041 * The solver supports all planning constraints as defined in Solver 00042 * class.<br> 00043 * See the documentation of the different solve methods to understand the 00044 * functionality in more detail. 00045 * 00046 * The logging levels have the following meaning: 00047 * - 0: Silent operation. Default logging level. 00048 * - 1: Show solver progress for each demand. 00049 * - 2: Show the complete ask&reply communication of the solver. 00050 * - 3: Trace the status of all entities. 00051 */ 00052 class SolverMRP : public Solver 00053 { 00054 protected: 00055 /** This variable stores the constraint which the solver should respect. 00056 * By default no constraints are enabled. */ 00057 short constrts; 00058 00059 /** Behavior of this solver method is: 00060 * - It will ask the consuming flows for the required quantity. 00061 * - The quantity asked for takes into account the quantity_per of the 00062 * producing flow. 00063 * - The date asked for takes into account the post-operation time 00064 * of the operation. 00065 */ 00066 DECLARE_EXPORT void solve(const Operation*, void* = NULL); 00067 00068 /** Behavior of this solver method is: 00069 * - Asks each of the routing steps for the requested quantity, starting 00070 * with the last routing step.<br> 00071 * The time requested for the operation is based on the start date of 00072 * the next routing step. 00073 */ 00074 DECLARE_EXPORT void solve(const OperationRouting*, void* = NULL); 00075 00076 /** Behavior of this solver method is: 00077 * - The solver loops through each alternate operation in order of 00078 * priority. On each alternate operation, the solver will try to plan 00079 * the quantity that hasn't been planned on higher priority alternates. 00080 * - As a special case, operations with zero priority are skipped in the 00081 * loop. These operations are considered to be temporarily unavailable. 00082 * - The requested operation can be planned over multiple alternates. 00083 * We don't garantuee that a request is planned using a single alternate 00084 * operation. 00085 * - The solver properly considers the quantity_per of all flows producing 00086 * into the requested buffer, if such a buffer is specified. 00087 */ 00088 DECLARE_EXPORT void solve(const OperationAlternate*,void* = NULL); 00089 00090 /** Behavior of this solver method: 00091 * - No propagation to upstream buffers at all, even if a producing 00092 * operation has been specified. 00093 * - Always give an answer for the full quantity on the requested date. 00094 */ 00095 DECLARE_EXPORT void solve(const BufferInfinite*,void* = NULL); 00096 00097 /** Behavior of this solver method: 00098 * - Consider 0 as the hard minimum limit. It is not possible 00099 * to plan with a 'hard' safety stock reservation. 00100 * - Minimum inventory is treated as a 'wish' inventory. When replenishing 00101 * a buffer we try to satisfy the minimum target. If that turns out 00102 * not to be possible we use whatever available supply for satisfying 00103 * the demand first. 00104 * - Planning for the minimum target is part of planning a demand. There 00105 * is no planning run independent of demand to satisfy the minimum 00106 * target.<br> 00107 * E.g. If a buffer has no demand on it, the solver won't try to 00108 * replenish to the minimum target.<br> 00109 * E.g. If the minimum target increases after the latest date required 00110 * for satisfying a certain demand that change will not be considered. 00111 * - The solver completely ignores the maximum target. 00112 */ 00113 DECLARE_EXPORT void solve(const Buffer*, void* = NULL); 00114 00115 /** Behavior of this solver method: 00116 * - When the inventory drops below the minimum inventory level, a new 00117 * replenishment is triggered. 00118 * The replenishment brings the inventory to the maximum level again. 00119 * - The minimum and maximum inventory are soft-constraints. The actual 00120 * inventory can go lower than the minimum or exceed the maximum. 00121 * - The minimum, maximum and multiple size of the replenishment are 00122 * hard constraints, and will always be respected. 00123 * - A minimum and maximum interval between replenishment is also 00124 * respected as a hard constraint. 00125 * - No propagation to upstream buffers at all, even if a producing 00126 * operation has been specified. 00127 * - The minimum calendar isn't used by the solver. 00128 */ 00129 DECLARE_EXPORT void solve(const BufferProcure*, void* = NULL); 00130 00131 /** Behavior of this solver method: 00132 * - This method simply passes on the request to the referenced buffer. 00133 * It is called from a solve(Operation*) method and passes on the 00134 * control to a solve(Buffer*) method. 00135 * @see checkOperationMaterial 00136 */ 00137 DECLARE_EXPORT void solve(const Flow*, void* = NULL); 00138 00139 /** Behavior of this solver method: 00140 * - The operationplan is checked for a capacity overload. When detected 00141 * it is moved to an earlier date. 00142 * - This move can be repeated until no capacity is found till a suitable 00143 * time slot is found. If the fence and/or leadtime constraints are 00144 * enabled they can restrict the feasible moving time.<br> 00145 * If a feasible timeslot is found, the method exits here. 00146 * - If no suitable time slot can be found at all, the operation plan is 00147 * put on its original date and we now try to move it to a feasible 00148 * later date. Again, successive moves are possible till a suitable 00149 * slot is found or till we reach the end of the horizon. 00150 * The result of the search is returned as the answer-date to the 00151 * solver. 00152 */ 00153 DECLARE_EXPORT void solve(const Resource*, void* = NULL); 00154 00155 /** Behavior of this solver method: 00156 * - Always return OK. 00157 */ 00158 DECLARE_EXPORT void solve(const ResourceInfinite*,void* = NULL); 00159 00160 /** Behavior of this solver method: 00161 * - This method simply passes on the request to the referenced resource. 00162 * With the current model structure it could easily be avoided (and 00163 * thus gain a bit in performance), but we wanted to include it anyway 00164 * to make the solver as generic and future-proof as possible. 00165 * @see checkOperationCapacity 00166 */ 00167 DECLARE_EXPORT void solve(const Load*, void* = NULL); 00168 00169 /** Behavior of this solver method: 00170 * - Respects the following demand planning policies:<br> 00171 * 1) Maximum allowed lateness 00172 * 2) Minimum shipment quantity 00173 * This method is normally called from within the main solve method, but 00174 * it can also be called independently to plan a certain demand. 00175 * @see solve 00176 */ 00177 DECLARE_EXPORT void solve(const Demand*, void* = NULL); 00178 00179 public: 00180 /** This is the main solver method that will appropriately call the other 00181 * solve methods.<br> 00182 * The demands in the model will all be sorted with the criteria defined in 00183 * the demand_comparison() method. For each of demand the solve(Demand*) 00184 * method is called to plan it. 00185 */ 00186 DECLARE_EXPORT void solve(void *v = NULL); 00187 00188 /** Constructor. */ 00189 SolverMRP(const string& n) : 00190 Solver(n), constrts(0), maxparallel(0), lazydelay(86400L) {} 00191 00192 /** Destructor. */ 00193 virtual ~SolverMRP() {} 00194 00195 DECLARE_EXPORT void writeElement(XMLOutput*, const Keyword&, mode=DEFAULT) const; 00196 DECLARE_EXPORT void endElement(XMLInput& pIn, const Attribute& pAttr, const DataElement& pElement); 00197 00198 virtual const MetaClass& getType() const {return *metadata;} 00199 static DECLARE_EXPORT const MetaClass* metadata; 00200 virtual size_t getSize() const {return sizeof(SolverMRP);} 00201 00202 /** Static constant for the LEADTIME constraint type.<br> 00203 * The numeric value is 1. 00204 * @see MATERIAL 00205 * @see CAPACITY 00206 * @see FENCE 00207 */ 00208 static const short LEADTIME = 1; 00209 00210 /** Static constant for the MATERIAL constraint type.<br> 00211 * The numeric value is 2. 00212 * @see LEADTIME 00213 * @see CAPACITY 00214 * @see FENCE 00215 */ 00216 static const short MATERIAL = 2; 00217 00218 /** Static constant for the CAPACITY constraint type.<br> 00219 * The numeric value is 4. 00220 * @see MATERIAL 00221 * @see LEADTIME 00222 * @see FENCE 00223 */ 00224 static const short CAPACITY = 4; 00225 00226 /** Static constant for the FENCE constraint type.<br> 00227 * The numeric value is 8. 00228 * @see MATERIAL 00229 * @see CAPACITY 00230 * @see LEADTIME 00231 */ 00232 static const short FENCE = 8; 00233 00234 /** Update the constraints to be considered by this solver. This field may 00235 * not be applicable for all solvers. */ 00236 void setConstraints(short i) {constrts = i;} 00237 00238 /** Returns the constraints considered by the solve. */ 00239 short getConstraints() const {return constrts;} 00240 00241 /** Returns true if this solver respects the operation release fences. 00242 * The solver isn't allowed to create any operation plans within the 00243 * release fence. 00244 */ 00245 bool isFenceConstrained() const {return (constrts & FENCE)>0;} 00246 00247 /** Returns true if this solver respects the current time of the plan. 00248 * The solver isn't allowed to create any operation plans in the past. 00249 */ 00250 bool isLeadtimeConstrained() const {return (constrts & LEADTIME)>0;} 00251 bool isMaterialConstrained() const {return (constrts & MATERIAL)>0;} 00252 bool isCapacityConstrained() const {return (constrts & CAPACITY)>0;} 00253 00254 /** Returns true if any constraint is relevant for the solver. */ 00255 bool isConstrained() const {return constrts>0;} 00256 00257 /** This function defines the order in which the demands are being 00258 * planned.<br> 00259 * The following sorting criteria are appplied in order: 00260 * - demand priority: smaller priorities first 00261 * - demand due date: earlier due dates first 00262 * - demand quantity: smaller quantities first 00263 */ 00264 static DECLARE_EXPORT bool demand_comparison(const Demand*, const Demand*); 00265 00266 /** Update the number of parallel solver threads.<br> 00267 * The default value depends on whether the solver is run in verbose mode 00268 * or not: 00269 * - In normal mode the solver uses as many threads as specified by 00270 * the environment variable NUMBER_OF_PROCESSORS. 00271 * - In verbose mode the solver runs in a single thread to avoid 00272 * mangling the debugging output of different threads. 00273 */ 00274 void setMaxParallel(int i) 00275 { 00276 if (i >= 1) maxparallel = i; 00277 else throw DataException("Invalid number of parallel solver threads"); 00278 } 00279 00280 /** Return the number of threads used for planning. */ 00281 int getMaxParallel() const 00282 { 00283 // Or: Explicitly specified number of threads 00284 if (maxparallel) return maxparallel; 00285 // Or: Default number of threads 00286 else return getLogLevel()>0 ? 1 : Environment::getProcessors(); 00287 } 00288 00289 /** Return the time increment between requests when the answered reply 00290 * date isn't usable. */ 00291 TimePeriod getLazyDelay() const {return lazydelay;} 00292 00293 /** Update the time increment between requests when the answered reply 00294 * date isn't usable. */ 00295 void setLazyDelay(TimePeriod l) 00296 { 00297 if (l > 0L) lazydelay = l; 00298 else throw DataException("Invalid lazy delay"); 00299 } 00300 00301 private: 00302 typedef map < int, deque<Demand*>, less<int> > classified_demand; 00303 typedef classified_demand::iterator cluster_iterator; 00304 classified_demand demands_per_cluster; 00305 00306 /** Number of parallel solver threads.<br> 00307 * The default value depends on whether the solver is run in verbose mode 00308 * or not: 00309 * - In normal mode the solver uses NUMBER_OF_PROCESSORS threads. 00310 * - In verbose mode the solver runs in a single thread to avoid 00311 * mangling the debugging output of different threads. 00312 */ 00313 int maxparallel; 00314 00315 /** Time increments for a lazy replan.<br> 00316 * The solver is expected to return always a next-feasible date when the 00317 * request can't be met. The solver can then retry the request with an 00318 * updated request date. In some corner cases and in case of a bug it is 00319 * possible that no valid date is returned. The solver will then try the 00320 * request with a request date incremented by this value.<br> 00321 * The default value is 1 day. 00322 */ 00323 TimePeriod lazydelay; 00324 00325 protected: 00326 /** @brief This class is used to store the solver status during the 00327 * ask-reply calls of the solver. 00328 * 00329 */ 00330 struct State 00331 { 00332 /** Points to the demand being planned. */ 00333 Demand* curDemand; 00334 00335 /** Points to the current owner operationplan. This is used when 00336 * operations are nested. */ 00337 OperationPlan* curOwnerOpplan; 00338 00339 /** Points to the current buffer. */ 00340 Buffer* curBuffer; 00341 00342 /** A flag to force the resource solver to move the operationplan to 00343 * a later date where it is feasible.<br> 00344 * Admittedly this is an ugly hack... 00345 */ 00346 bool forceLate; 00347 00348 /** This is the quantity we are asking for. */ 00349 double q_qty; 00350 00351 /** This is the date we are asking for. */ 00352 Date q_date; 00353 00354 /** This is the maximum date we are asking for.<br> 00355 * In case of a post-operation time there is a difference between 00356 * q_date and q_date_max. 00357 */ 00358 Date q_date_max; 00359 00360 /** This is the quantity we can get by the requested Date. */ 00361 double a_qty; 00362 00363 /** This is the Date when we can get extra availability. */ 00364 Date a_date; 00365 00366 /** This is a pointer to a LoadPlan. It is used for communication 00367 * between the Operation-Solver and the Resource-Solver. */ 00368 LoadPlan* q_loadplan; 00369 00370 /** This is a pointer to a FlowPlan. It is used for communication 00371 * between the Operation-Solver and the Buffer-Solver. */ 00372 FlowPlan* q_flowplan; 00373 00374 /** A pointer to an operationplan currently being solved. */ 00375 OperationPlan* q_operationplan; 00376 00377 /** Cost of the reply.<br> 00378 * Only the direct cost should be returned in this field. 00379 */ 00380 double a_cost; 00381 00382 /** Penalty associated with the reply.<br> 00383 * This field contains indirect costs and other penalties that are 00384 * not strictly related to the request. Examples are setup costs, 00385 * inventory carrying costs, ... 00386 */ 00387 double a_penalty; 00388 }; 00389 00390 /** @brief This class is a helper class of the SolverMRP class. 00391 * 00392 * It stores the solver state maintained by each solver thread. 00393 * @see SolverMRP 00394 */ 00395 class SolverMRPdata : public CommandList 00396 { 00397 friend class SolverMRP; 00398 public: 00399 SolverMRP* getSolver() const {return sol;} 00400 00401 /** Constructor. */ 00402 SolverMRPdata(SolverMRP* s, int c, deque<Demand*>& d) 00403 : sol(s), cluster(c), demands(d), 00404 state(statestack), prevstate(statestack-1) {} 00405 00406 /** Verbose mode is inherited from the solver. */ 00407 unsigned short getLogLevel() const {return sol ? sol->getLogLevel() : 0;} 00408 00409 /** This function runs a single planning thread. Such a thread will loop 00410 * through the following steps: 00411 * - Use the method next_cluster() to find another unplanned cluster. 00412 * - Exit the thread if no more cluster is found. 00413 * - Sort all demands in the cluster, using the demand_comparison() 00414 * method. 00415 * - Loop through the sorted list of demands and plan each of them. 00416 * During planning the demands exceptions are caught, and the 00417 * planning loop will simply move on to the next demand. 00418 * In this way, an error in a part of the model doesn't ruin the 00419 * complete plan. 00420 * @see demand_comparison 00421 * @see next_cluster 00422 */ 00423 virtual DECLARE_EXPORT void execute(); 00424 00425 virtual const MetaClass& getType() const {return *SolverMRP::metadata;} 00426 virtual size_t getSize() const {return sizeof(SolverMRPdata);} 00427 00428 bool getVerbose() const 00429 { 00430 throw LogicException("Use the method SolverMRPdata::getLogLevel() instead of SolverMRPdata::getVerbose()"); 00431 } 00432 00433 /** Add a new state to the status stack. */ 00434 inline void push(double q = 0.0, Date d = Date::infiniteFuture) 00435 { 00436 if (state >= statestack + MAXSTATES) 00437 throw RuntimeException("Maximum recursion depth exceeded"); 00438 ++state; 00439 ++prevstate; 00440 state->q_qty = q; 00441 state->q_date = d; 00442 state->curOwnerOpplan = NULL; 00443 state->q_loadplan = NULL; 00444 state->q_flowplan = NULL; 00445 state->q_operationplan = NULL; 00446 state->a_cost = 0.0; 00447 state->a_penalty = 0.0; 00448 } 00449 00450 /** Removes a state from the status stack. */ 00451 inline void pop() 00452 { 00453 if (--state < statestack) 00454 throw LogicException("State stack empty"); 00455 --prevstate; 00456 } 00457 00458 /** Pointer to the current solver status. */ 00459 State* state; 00460 00461 /** Pointer to the solver status one level higher on the stack. */ 00462 State* prevstate; 00463 00464 private: 00465 static const int MAXSTATES = 256; 00466 00467 /** Points to the solver. */ 00468 SolverMRP* sol; 00469 00470 /** An identifier of the cluster being replanned. Note that it isn't 00471 * always the complete cluster that is being planned. 00472 */ 00473 int cluster; 00474 00475 /** A deque containing all demands to be (re-)planned. */ 00476 deque<Demand*>& demands; 00477 00478 /** Stack of solver status information. */ 00479 State statestack[MAXSTATES]; 00480 }; 00481 00482 /** This function will check all constraints for an operationplan 00483 * and propagate it upstream. The check does NOT check eventual 00484 * sub operationplans. 00485 * The return value is a flag whether the operationplan is 00486 * acceptable (sometimes in reduced quantity) or not. 00487 */ 00488 DECLARE_EXPORT bool checkOperation(OperationPlan*, SolverMRPdata& data); 00489 00490 /** Verifies whether this operationplan violates the leadtime 00491 * constraints. */ 00492 DECLARE_EXPORT bool checkOperationLeadtime(OperationPlan*, SolverMRPdata&, bool); 00493 00494 /** Verifies whether this operationplan violates the capacity constraint. 00495 * In case it does the operationplan is moved to an earlier or later 00496 * feasible date. 00497 */ 00498 DECLARE_EXPORT void checkOperationCapacity(OperationPlan*, SolverMRPdata&); 00499 }; 00500 00501 00502 class PythonSolverMRP : public FreppleClass<PythonSolverMRP,PythonSolver,SolverMRP> 00503 { 00504 public: 00505 PythonSolverMRP(SolverMRP* p) 00506 : FreppleClass<PythonSolverMRP,PythonSolver,SolverMRP>(p) {} 00507 virtual DECLARE_EXPORT PyObject* getattro(const Attribute&); 00508 virtual DECLARE_EXPORT int setattro(const Attribute&, const PythonObject&); 00509 }; 00510 00511 00512 /** @brief This class holds functions that used for maintenance of the solver 00513 * code. 00514 */ 00515 class LibrarySolver 00516 { 00517 public: 00518 static void initialize(); 00519 }; 00520 00521 00522 } // end namespace 00523 00524 00525 #endif