solveroperation.cpp
Go to the documentation of this file.
00001 /*************************************************************************** 00002 file : $URL: https://frepple.svn.sourceforge.net/svnroot/frepple/trunk/src/solver/solveroperation.cpp $ 00003 version : $LastChangedRevision: 1505 $ $LastChangedBy: jdetaeye $ 00004 date : $LastChangedDate: 2011-08-26 18:55:08 +0200 (Fri, 26 Aug 2011) $ 00005 ***************************************************************************/ 00006 00007 /*************************************************************************** 00008 * * 00009 * Copyright (C) 2007-2011 by Johan De Taeye, frePPLe bvba * 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., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 * 00024 * USA * 00025 * * 00026 ***************************************************************************/ 00027 00028 #define FREPPLE_CORE 00029 #include "frepple/solver.h" 00030 namespace frepple 00031 { 00032 00033 00034 DECLARE_EXPORT void SolverMRP::checkOperationCapacity 00035 (OperationPlan* opplan, SolverMRP::SolverMRPdata& data) 00036 { 00037 unsigned short constrainedLoads = 0; 00038 for (OperationPlan::LoadPlanIterator h=opplan->beginLoadPlans(); 00039 h!=opplan->endLoadPlans(); ++h) 00040 if (h->getResource()->getType() != *(ResourceInfinite::metadata) 00041 && h->isStart() && h->getLoad()->getQuantity() != 0.0) 00042 { 00043 if (++constrainedLoads > 1) break; 00044 } 00045 DateRange orig; 00046 00047 // Loop through all loadplans, and solve for the resource. 00048 // This may move an operationplan early or late. 00049 Problem* curConstraint = data.planningDemand->getConstraints().top(); 00050 do 00051 { 00052 data.planningDemand->getConstraints().pop(curConstraint); 00053 orig = opplan->getDates(); 00054 for (OperationPlan::LoadPlanIterator h=opplan->beginLoadPlans(); 00055 h!=opplan->endLoadPlans() && opplan->getDates()==orig; ++h) 00056 { 00057 data.state->q_operationplan = opplan; 00058 data.state->q_loadplan = &*h; 00059 data.state->q_qty = h->getQuantity(); 00060 data.state->q_date = h->getDate(); 00061 // Call the load solver - which will call the resource solver. 00062 if (h->getLoad()->getQuantity() != 0.0) 00063 h->getLoad()->solve(*this,&data); 00064 } 00065 } 00066 // Imagine there are multiple loads. As soon as one of them is moved, we 00067 // need to redo the capacity check for the ones we already checked. 00068 // Repeat until no load has touched the opplan, or till proven infeasible. 00069 // No need to reloop if there is only a single load (= 2 loadplans) 00070 while (constrainedLoads>1 && opplan->getDates()!=orig && (data.state->a_qty!=0.0 || data.state->forceLate)); 00071 } 00072 00073 00074 DECLARE_EXPORT bool SolverMRP::checkOperation 00075 (OperationPlan* opplan, SolverMRP::SolverMRPdata& data) 00076 { 00077 // The default answer... 00078 data.state->a_date = Date::infiniteFuture; 00079 data.state->a_qty = data.state->q_qty; 00080 00081 // Handle unavailable time. 00082 // Note that this unavailable time is checked also in an unconstrained plan. 00083 // This means that also an unconstrained plan can plan demand late! 00084 if (opplan->getQuantity() == 0.0) 00085 { 00086 // It is possible that the operation could not be created properly. 00087 // This happens when the operation is not available for enough time. 00088 // Eg. A fixed time operation needs 10 days on jan 20 on an operation 00089 // that is only available only 2 days since the start of the horizon. 00090 // Resize to the minimum quantity 00091 opplan->setQuantity(0.0001,false); 00092 // Move to the earliest start date 00093 opplan->setStart(Plan::instance().getCurrent()); 00094 // Pick up the earliest date we can reply back 00095 data.state->a_date = opplan->getDates().getEnd(); 00096 data.state->a_qty = 0.0; 00097 return false; 00098 } 00099 00100 // Check the leadtime constraints 00101 if (data.constrainedPlanning && !checkOperationLeadtime(opplan,data,true)) 00102 // This operationplan is a wreck. It is impossible to make it meet the 00103 // leadtime constraints 00104 return false; 00105 00106 // Set a bookmark in the command list. 00107 CommandManager::Bookmark* topcommand = data.setBookmark(); 00108 00109 // Temporary variables 00110 DateRange orig_dates = opplan->getDates(); 00111 bool okay = true; 00112 Date a_date; 00113 double a_qty; 00114 Date orig_q_date = data.state->q_date; 00115 double orig_opplan_qty = data.state->q_qty; 00116 double q_qty_Flow; 00117 Date q_date_Flow; 00118 bool incomplete; 00119 bool tmp_forceLate = data.state->forceLate; 00120 bool isPlannedEarly; 00121 DateRange matnext; 00122 00123 // Loop till everything is okay. During this loop the quanity and date of the 00124 // operationplan can be updated, but it cannot be split or deleted. 00125 data.state->forceLate = false; 00126 do 00127 { 00128 if (isCapacityConstrained()) 00129 { 00130 // Verify the capacity. This can move the operationplan early or late. 00131 checkOperationCapacity(opplan,data); 00132 // Return false if no capacity is available 00133 if (data.state->a_qty==0.0) return false; 00134 } 00135 00136 // Check material 00137 data.state->q_qty = opplan->getQuantity(); 00138 data.state->q_date = opplan->getDates().getEnd(); 00139 a_qty = opplan->getQuantity(); 00140 a_date = data.state->q_date; 00141 incomplete = false; 00142 matnext.setStart(Date::infinitePast); 00143 matnext.setEnd(Date::infiniteFuture); 00144 00145 // Loop through all flowplans // @todo need some kind of coordination run here!!! see test alternate_flow_1 00146 for (OperationPlan::FlowPlanIterator g=opplan->beginFlowPlans(); 00147 g!=opplan->endFlowPlans(); ++g) 00148 if (g->getFlow()->isConsumer()) 00149 { 00150 // Switch back to the main alternate if this flowplan was already // @todo is this really required? If yes, in this place? 00151 // planned on an alternate 00152 if (g->getFlow()->getAlternate()) 00153 g->setFlow(g->getFlow()->getAlternate()); 00154 00155 // Trigger the flow solver, which will call the buffer solver 00156 data.state->q_flowplan = &*g; 00157 q_qty_Flow = - data.state->q_flowplan->getQuantity(); // @todo flow quantity can change when using alternate flows -> move to flow solver! 00158 q_date_Flow = data.state->q_flowplan->getDate(); 00159 g->getFlow()->solve(*this,&data); 00160 00161 // Validate the answered quantity 00162 if (data.state->a_qty < q_qty_Flow) 00163 { 00164 // Update the opplan, which is required to (1) update the flowplans 00165 // and to (2) take care of lot sizing constraints of this operation. 00166 g->setQuantity(-data.state->a_qty, true); 00167 a_qty = opplan->getQuantity(); 00168 incomplete = true; 00169 00170 // Validate the answered date of the most limiting flowplan. 00171 // Note that the delay variable only reflects the delay due to 00172 // material constraints. If the operationplan is moved early or late 00173 // for capacity constraints, this is not included. 00174 if (data.state->a_date < Date::infiniteFuture) 00175 { 00176 OperationPlanState at = opplan->getOperation()->setOperationPlanParameters( 00177 opplan, 0.01, data.state->a_date, Date::infinitePast, false, false 00178 ); 00179 if (at.end < matnext.getEnd()) matnext = DateRange(at.start, at.end); 00180 //xxxif (matnext.getEnd() <= orig_q_date) logger << "STRANGE" << matnext << " " << orig_q_date << " " << at.second << " " << opplan->getQuantity() << endl; 00181 } 00182 00183 // Jump out of the loop if the answered quantity is 0. 00184 if (a_qty <= ROUNDING_ERROR) 00185 { 00186 // @TODO disabled To speed up the planning the constraining flow is moved up a 00187 // position in the list of flows. It'll thus be checked earlier 00188 // when this operation is asked again 00189 //const_cast<Operation::flowlist&>(g->getFlow()->getOperation()->getFlows()).promote(g->getFlow()); 00190 // There is absolutely no need to check other flowplans if the 00191 // operationplan quantity is already at 0. 00192 break; 00193 } 00194 } 00195 else if (data.state->a_qty >+ q_qty_Flow + ROUNDING_ERROR) 00196 // Never answer more than asked. 00197 // The actual operationplan could be bigger because of lot sizing. 00198 a_qty = - q_qty_Flow / g->getFlow()->getQuantity(); 00199 } 00200 00201 isPlannedEarly = opplan->getDates().getEnd() < orig_dates.getEnd(); 00202 00203 if (matnext.getEnd() != Date::infiniteFuture && a_qty <= ROUNDING_ERROR 00204 && matnext.getEnd() <= data.state->q_date_max && matnext.getEnd() > orig_q_date) 00205 { 00206 // The reply is 0, but the next-date is still less than the maximum 00207 // ask date. In this case we will violate the post-operation -soft- 00208 // constraint. 00209 data.state->q_date = matnext.getEnd(); 00210 orig_q_date = data.state->q_date; 00211 data.state->q_qty = orig_opplan_qty; 00212 data.state->a_date = Date::infiniteFuture; 00213 data.state->a_qty = data.state->q_qty; 00214 opplan->getOperation()->setOperationPlanParameters( 00215 opplan, orig_opplan_qty, Date::infinitePast, matnext.getEnd() 00216 ); 00217 okay = false; 00218 // Pop actions from the command "stack" in the command list 00219 data.rollback(topcommand); 00220 // Echo a message 00221 if (data.getSolver()->getLogLevel()>1) 00222 logger << indent(opplan->getOperation()->getLevel()) 00223 << " Retrying new date." << endl; 00224 } 00225 else if (matnext.getEnd() != Date::infiniteFuture && a_qty <= ROUNDING_ERROR 00226 && matnext.getStart() < a_date) 00227 { 00228 // The reply is 0, but the next-date is not too far out. 00229 // If the operationplan would fit in a smaller timeframe we can potentially 00230 // create a non-zero reply... 00231 // Resize the operationplan 00232 opplan->getOperation()->setOperationPlanParameters( 00233 opplan, orig_opplan_qty, matnext.getStart(), 00234 a_date 00235 ); 00236 if (opplan->getDates().getStart() >= matnext.getStart() 00237 && opplan->getDates().getEnd() <= a_date 00238 && opplan->getQuantity() > ROUNDING_ERROR) 00239 { 00240 // It worked 00241 orig_dates = opplan->getDates(); 00242 data.state->q_date = orig_dates.getEnd(); 00243 data.state->q_qty = opplan->getQuantity(); 00244 data.state->a_date = Date::infiniteFuture; 00245 data.state->a_qty = data.state->q_qty; 00246 okay = false; 00247 // Pop actions from the command stack in the command list 00248 data.rollback(topcommand); 00249 // Echo a message 00250 if (data.getSolver()->getLogLevel()>1) 00251 logger << indent(opplan->getOperation()->getLevel()) 00252 << " Retrying with a smaller quantity: " 00253 << opplan->getQuantity() << endl; 00254 } 00255 else 00256 { 00257 // It didn't work 00258 opplan->setQuantity(0); 00259 okay = true; 00260 } 00261 } 00262 else 00263 okay = true; 00264 } 00265 while (!okay); // Repeat the loop if the operation was moved and the 00266 // feasibility needs to be rechecked. 00267 00268 if (a_qty <= ROUNDING_ERROR && !data.state->forceLate 00269 && isPlannedEarly 00270 && matnext.getStart() != Date::infiniteFuture 00271 && matnext.getStart() != Date::infinitePast 00272 && (data.constrainedPlanning && isCapacityConstrained())) 00273 { 00274 // The operationplan was moved early (because of a resource constraint) 00275 // and we can't properly trust the reply date in such cases... 00276 // We want to enforce rechecking the next date. 00277 00278 // Move the operationplan to the next date where the material is feasible 00279 opplan->getOperation()->setOperationPlanParameters 00280 (opplan, orig_opplan_qty, matnext.getStart(), Date::infinitePast); 00281 00282 // Move the operationplan to a later date where it is feasible. 00283 data.state->forceLate = true; 00284 checkOperationCapacity(opplan,data); 00285 00286 // Reply of this function 00287 a_qty = 0.0; 00288 matnext.setEnd(opplan->getDates().getEnd()); 00289 } 00290 00291 // Compute the final reply 00292 data.state->a_date = incomplete ? matnext.getEnd() : Date::infiniteFuture; 00293 data.state->a_qty = a_qty; 00294 data.state->forceLate = tmp_forceLate; 00295 if (a_qty > ROUNDING_ERROR) 00296 return true; 00297 else 00298 { 00299 // Undo the plan 00300 data.rollback(topcommand); 00301 return false; 00302 } 00303 } 00304 00305 00306 DECLARE_EXPORT bool SolverMRP::checkOperationLeadtime 00307 (OperationPlan* opplan, SolverMRP::SolverMRPdata& data, bool extra) 00308 { 00309 // No lead time constraints 00310 if (!data.constrainedPlanning || (!isFenceConstrained() && !isLeadtimeConstrained())) 00311 return true; 00312 00313 // Compute offset from the current date: A fence problem uses the release 00314 // fence window, while a leadtimeconstrained constraint has an offset of 0. 00315 // If both constraints apply, we need the bigger of the two (since it is the 00316 // most constraining date. 00317 Date threshold = Plan::instance().getCurrent(); 00318 if (isFenceConstrained() 00319 && !(isLeadtimeConstrained() && opplan->getOperation()->getFence()<0L)) 00320 threshold += opplan->getOperation()->getFence(); 00321 00322 // Check the setup operationplan 00323 OperationPlanState original(opplan); 00324 bool ok = true; 00325 bool checkSetup = true; 00326 00327 // If there are alternate loads we take the best case and assume that 00328 // at least one of those can give us a zero-time setup. 00329 // When evaluating the leadtime when solving for capacity we don't use 00330 // this assumption. The resource solver takes care of the constraints. 00331 if (extra && isCapacityConstrained()) 00332 for (Operation::loadlist::const_iterator j = opplan->getOperation()->getLoads().begin(); 00333 j != opplan->getOperation()->getLoads().end(); ++j) 00334 if (j->hasAlternates()) 00335 { 00336 checkSetup = false; 00337 break; 00338 } 00339 if (checkSetup) 00340 { 00341 OperationPlan::iterator i(opplan); 00342 if (i != opplan->end() 00343 && i->getOperation() == OperationSetup::setupoperation 00344 && i->getDates().getStart() < threshold) 00345 { 00346 // The setup operationplan is violating the lead time and/or fence 00347 // constraint. We move it to start on the earliest allowed date, 00348 // which automatically also moves the owner operationplan. 00349 i->setStart(threshold); 00350 threshold = i->getDates().getEnd(); 00351 ok = false; 00352 } 00353 } 00354 00355 // Compare the operation plan start with the threshold date 00356 if (ok && opplan->getDates().getStart() >= threshold) 00357 // There is no problem 00358 return true; 00359 00360 // Compute how much we can supply in the current timeframe. 00361 // In other words, we try to resize the operation quantity to fit the 00362 // available timeframe: used for e.g. time-per operations 00363 // Note that we allow the complete post-operation time to be eaten 00364 if (extra) 00365 // Leadtime check during operation resolver 00366 opplan->getOperation()->setOperationPlanParameters( 00367 opplan, opplan->getQuantity(), 00368 threshold, 00369 original.end + opplan->getOperation()->getPostTime(), 00370 false 00371 ); 00372 else 00373 // Leadtime check during capacity resolver 00374 opplan->getOperation()->setOperationPlanParameters( 00375 opplan, opplan->getQuantity(), 00376 threshold, 00377 original.end, 00378 true 00379 ); 00380 00381 // Check the result of the resize 00382 if (opplan->getDates().getStart() >= threshold 00383 && (!extra || opplan->getDates().getEnd() <= data.state->q_date_max) 00384 && opplan->getQuantity() > ROUNDING_ERROR) 00385 { 00386 // Resizing did work! The operation now fits within constrained limits 00387 data.state->a_qty = opplan->getQuantity(); 00388 data.state->a_date = opplan->getDates().getEnd(); 00389 // Acknowledge creation of operationplan 00390 return true; 00391 } 00392 else 00393 { 00394 // This operation doesn't fit at all within the constrained window. 00395 data.state->a_qty = 0.0; 00396 // Resize to the minimum quantity 00397 if (opplan->getQuantity() + ROUNDING_ERROR < opplan->getOperation()->getSizeMinimum()) 00398 opplan->setQuantity(0.0001,false); 00399 // Move to the earliest start date 00400 opplan->setStart(threshold); 00401 // Pick up the earliest date we can reply back 00402 data.state->a_date = opplan->getDates().getEnd(); 00403 // Set the quantity to 0 (to make sure the buffer doesn't see the supply). 00404 opplan->setQuantity(0.0); 00405 00406 // Log the constraint 00407 if (data.logConstraints) 00408 data.planningDemand->getConstraints().push( 00409 (threshold == Plan::instance().getCurrent()) ? 00410 ProblemBeforeCurrent::metadata : 00411 ProblemBeforeFence::metadata, 00412 opplan->getOperation(), original.start, original.end, 00413 original.quantity 00414 ); 00415 00416 // Deny creation of the operationplan 00417 return false; 00418 } 00419 } 00420 00421 00422 DECLARE_EXPORT void SolverMRP::solve(const Operation* oper, void* v) 00423 { 00424 // Make sure we have a valid operation 00425 assert(oper); 00426 00427 SolverMRPdata* data = static_cast<SolverMRPdata*>(v); 00428 OperationPlan *z; 00429 00430 // Call the user exit 00431 if (userexit_operation) userexit_operation.call(oper, PythonObject(data->constrainedPlanning)); 00432 00433 // Find the flow for the quantity-per. This can throw an exception if no 00434 // valid flow can be found. 00435 double flow_qty_per = 1.0; 00436 if (data->state->curBuffer) 00437 { 00438 Flow* f = oper->findFlow(data->state->curBuffer, data->state->q_date); 00439 if (f && f->getQuantity()>0.0) 00440 flow_qty_per = f->getQuantity(); 00441 else 00442 // The producing operation doesn't have a valid flow into the current 00443 // buffer. Either it is missing or it is producing a negative quantity. 00444 throw DataException("Invalid producing operation '" + oper->getName() 00445 + "' for buffer '" + data->state->curBuffer->getName() + "'"); 00446 } 00447 00448 // Message 00449 if (data->getSolver()->getLogLevel()>1) 00450 logger << indent(oper->getLevel()) << " Operation '" << oper->getName() 00451 << "' is asked: " << data->state->q_qty << " " << data->state->q_date << endl; 00452 00453 // Find the current list of constraints 00454 Problem* topConstraint = data->planningDemand->getConstraints().top(); 00455 double originalqty = data->state->q_qty; 00456 00457 // Subtract the post-operation time 00458 Date prev_q_date_max = data->state->q_date_max; 00459 data->state->q_date_max = data->state->q_date; 00460 data->state->q_date -= oper->getPostTime(); 00461 00462 // Create the operation plan. 00463 if (data->state->curOwnerOpplan) 00464 { 00465 // There is already an owner and thus also an owner command 00466 assert(!data->state->curDemand); 00467 z = oper->createOperationPlan( 00468 data->state->q_qty / flow_qty_per, 00469 Date::infinitePast, data->state->q_date, data->state->curDemand, 00470 data->state->curOwnerOpplan, 0 00471 ); 00472 } 00473 else 00474 { 00475 // There is no owner operationplan yet. We need a new command. 00476 CommandCreateOperationPlan *a = 00477 new CommandCreateOperationPlan( 00478 oper, data->state->q_qty / flow_qty_per, 00479 Date::infinitePast, data->state->q_date, data->state->curDemand, 00480 data->state->curOwnerOpplan 00481 ); 00482 data->state->curDemand = NULL; 00483 z = a->getOperationPlan(); 00484 data->add(a); 00485 } 00486 assert(z); 00487 00488 // Check the constraints 00489 data->getSolver()->checkOperation(z,*data); 00490 data->state->q_date_max = prev_q_date_max; 00491 00492 // Multiply the operation reqply with the flow quantity to get a final reply 00493 if (data->state->curBuffer) data->state->a_qty *= flow_qty_per; 00494 00495 // Ignore any constraints if we get a complete reply. 00496 // Sometimes constraints are flagged due to a pre- or post-operation time. 00497 // Such constraints ultimately don't result in lateness and can be ignored. 00498 if (data->state->a_qty >= originalqty - ROUNDING_ERROR) 00499 data->planningDemand->getConstraints().pop(topConstraint); 00500 00501 // Check positive reply quantity 00502 assert(data->state->a_qty >= 0); 00503 00504 // Increment the cost 00505 if (data->state->a_qty > 0.0) 00506 data->state->a_cost += z->getQuantity() * oper->getCost(); 00507 00508 // Message 00509 if (data->getSolver()->getLogLevel()>1) 00510 logger << indent(oper->getLevel()) << " Operation '" << oper->getName() 00511 << "' answers: " << data->state->a_qty << " " << data->state->a_date 00512 << " " << data->state->a_cost << " " << data->state->a_penalty << endl; 00513 } 00514 00515 00516 // No need to take post- and pre-operation times into account 00517 DECLARE_EXPORT void SolverMRP::solve(const OperationRouting* oper, void* v) 00518 { 00519 SolverMRPdata* data = static_cast<SolverMRPdata*>(v); 00520 00521 // Call the user exit 00522 if (userexit_operation) userexit_operation.call(oper, PythonObject(data->constrainedPlanning)); 00523 00524 // Message 00525 if (data->getSolver()->getLogLevel()>1) 00526 logger << indent(oper->getLevel()) << " Routing operation '" << oper->getName() 00527 << "' is asked: " << data->state->q_qty << " " << data->state->q_date << endl; 00528 00529 // Find the total quantity to flow into the buffer. 00530 // Multiple suboperations can all produce into the buffer. 00531 double flow_qty = 1.0; 00532 if (data->state->curBuffer) 00533 { 00534 flow_qty = 0.0; 00535 Flow *f = oper->findFlow(data->state->curBuffer, data->state->q_date); 00536 if (f) flow_qty += f->getQuantity(); 00537 for (Operation::Operationlist::const_iterator 00538 e = oper->getSubOperations().begin(); 00539 e != oper->getSubOperations().end(); 00540 ++e) 00541 { 00542 f = (*e)->findFlow(data->state->curBuffer, data->state->q_date); 00543 if (f) flow_qty += f->getQuantity(); 00544 } 00545 if (flow_qty <= 0.0) 00546 throw DataException("Invalid producing operation '" + oper->getName() 00547 + "' for buffer '" + data->state->curBuffer->getName() + "'"); 00548 } 00549 // Because we already took care of it... @todo not correct if the suboperation is again a owning operation 00550 data->state->curBuffer = NULL; 00551 double a_qty(data->state->q_qty / flow_qty); 00552 00553 // Create the top operationplan 00554 CommandCreateOperationPlan *a = new CommandCreateOperationPlan( 00555 oper, a_qty, Date::infinitePast, 00556 data->state->q_date, data->state->curDemand, data->state->curOwnerOpplan, false 00557 ); 00558 data->state->curDemand = NULL; 00559 00560 // Make sure the subopplans know their owner & store the previous value 00561 OperationPlan *prev_owner_opplan = data->state->curOwnerOpplan; 00562 data->state->curOwnerOpplan = a->getOperationPlan(); 00563 00564 // Loop through the steps 00565 Date max_Date; 00566 TimePeriod delay; 00567 Date top_q_date(data->state->q_date); 00568 Date q_date; 00569 for (Operation::Operationlist::const_reverse_iterator 00570 e = oper->getSubOperations().rbegin(); 00571 e != oper->getSubOperations().rend() && a_qty > 0.0; 00572 ++e) 00573 { 00574 // Plan the next step 00575 data->state->q_qty = a_qty; 00576 data->state->q_date = data->state->curOwnerOpplan->getDates().getStart(); 00577 q_date = data->state->q_date; 00578 (*e)->solve(*this,v); // @todo if the step itself has child operations, the curOwnerOpplan field is changed here!!! 00579 a_qty = data->state->a_qty; 00580 00581 // Update the top operationplan 00582 data->state->curOwnerOpplan->setQuantity(a_qty,true); 00583 00584 // Maximum for the next date 00585 if (data->state->a_date != Date::infiniteFuture) 00586 { 00587 if (delay < data->state->a_date - q_date) 00588 delay = data->state->a_date - q_date; 00589 OperationPlanState at = data->state->curOwnerOpplan->getOperation()->setOperationPlanParameters( 00590 data->state->curOwnerOpplan, 0.01, //data->state->curOwnerOpplan->getQuantity(), 00591 data->state->a_date, Date::infinitePast, false, false 00592 ); 00593 if (at.end > max_Date) max_Date = at.end; 00594 } 00595 } 00596 00597 // Check the flows and loads on the top operationplan. 00598 // This can happen only after the suboperations have been dealt with 00599 // because only now we know how long the operation lasts in total. 00600 // Solving for the top operationplan can resize and move the steps that are 00601 // in the routing! 00602 /** @todo moving routing opplan doesn't recheck for feasibility of steps... */ 00603 data->state->curOwnerOpplan->createFlowLoads(); 00604 if (data->state->curOwnerOpplan->getQuantity() > 0.0) 00605 { 00606 data->state->q_qty = a_qty; 00607 data->state->q_date = data->state->curOwnerOpplan->getDates().getEnd(); 00608 data->getSolver()->checkOperation(data->state->curOwnerOpplan,*data); 00609 a_qty = data->state->a_qty; 00610 // The reply date is the combination of the reply date of all steps and the 00611 // reply date of the top operationplan. 00612 if (data->state->a_date > max_Date && data->state->a_date != Date::infiniteFuture) 00613 max_Date = data->state->a_date; 00614 } 00615 data->state->a_date = (max_Date ? max_Date : Date::infiniteFuture); 00616 if (data->state->a_date < data->state->q_date) 00617 data->state->a_date = data->state->q_date; 00618 00619 // Multiply the operationplan quantity with the flow quantity to get the 00620 // final reply quantity 00621 data->state->a_qty = a_qty * flow_qty; 00622 00623 // Add to the list (even if zero-quantity!) 00624 if (!prev_owner_opplan) data->add(a); 00625 00626 // Increment the cost 00627 if (data->state->a_qty > 0.0) 00628 data->state->a_cost += data->state->curOwnerOpplan->getQuantity() * oper->getCost(); 00629 00630 // Make other operationplans don't take this one as owner any more. 00631 // We restore the previous owner, which could be NULL. 00632 data->state->curOwnerOpplan = prev_owner_opplan; 00633 00634 // Check positive reply quantity 00635 assert(data->state->a_qty >= 0); 00636 00637 if (data->state->a_date <= top_q_date && delay > TimePeriod(0L)) 00638 // At least one of the steps is late, but the reply date at the overall routing level is not late. 00639 // This causes trouble, so we enforce a lateness of at least one hour. @todo not very cool/performant/generic... 00640 data->state->a_date = top_q_date + delay; // TimePeriod(3600L); 00641 00642 // Check reply date is later than requested date 00643 assert(data->state->a_date >= data->state->q_date); 00644 00645 // Message 00646 if (data->getSolver()->getLogLevel()>1) 00647 logger << indent(oper->getLevel()) << " Routing operation '" << oper->getName() 00648 << "' answers: " << data->state->a_qty << " " << data->state->a_date << " " 00649 << data->state->a_cost << " " << data->state->a_penalty << endl; 00650 } 00651 00652 00653 // No need to take post- and pre-operation times into account 00654 // @todo This method should only be allowed to create 1 operationplan 00655 DECLARE_EXPORT void SolverMRP::solve(const OperationAlternate* oper, void* v) 00656 { 00657 SolverMRPdata *data = static_cast<SolverMRPdata*>(v); 00658 Date origQDate = data->state->q_date; 00659 double origQqty = data->state->q_qty; 00660 Buffer *buf = data->state->curBuffer; 00661 Demand *d = data->state->curDemand; 00662 00663 // Call the user exit 00664 if (userexit_operation) userexit_operation.call(oper, PythonObject(data->constrainedPlanning)); 00665 00666 unsigned int loglevel = data->getSolver()->getLogLevel(); 00667 SearchMode search = oper->getSearch(); 00668 00669 // Message 00670 if (loglevel>1) 00671 logger << indent(oper->getLevel()) << " Alternate operation '" << oper->getName() 00672 << "' is asked: " << data->state->q_qty << " " << data->state->q_date << endl; 00673 00674 // Make sure sub-operationplans know their owner & store the previous value 00675 OperationPlan *prev_owner_opplan = data->state->curOwnerOpplan; 00676 00677 // Find the flow into the requesting buffer for the quantity-per 00678 double top_flow_qty_per = 0.0; 00679 bool top_flow_exists = false; 00680 if (buf) 00681 { 00682 Flow* f = oper->findFlow(buf, data->state->q_date); 00683 if (f && f->getQuantity() > 0.0) 00684 { 00685 top_flow_qty_per = f->getQuantity(); 00686 top_flow_exists = true; 00687 } 00688 } 00689 00690 // Control the planning mode 00691 bool originalPlanningMode = data->constrainedPlanning; 00692 data->constrainedPlanning = true; 00693 00694 // Remember the top constraint 00695 bool originalLogConstraints = data->logConstraints; 00696 Problem* topConstraint = data->planningDemand->getConstraints().top(); 00697 00698 // Try all alternates: 00699 // - First, all alternates that are fully effective in the order of priority. 00700 // - Next, the alternates beyond their effective end date. 00701 // We loop through these since they can help in meeting a demand on time, 00702 // but using them will also create extra inventory or delays. 00703 double a_qty = data->state->q_qty; 00704 bool effectiveOnly = true; 00705 Date a_date = Date::infiniteFuture; 00706 Date ask_date; 00707 Operation *firstAlternate = NULL; 00708 double firstFlowPer; 00709 while (a_qty > 0) 00710 { 00711 // Evaluate all alternates 00712 bool plannedAlternate = false; 00713 double bestAlternateValue = DBL_MAX; 00714 double bestAlternateQuantity = 0; 00715 Operation* bestAlternateSelection = NULL; 00716 double bestFlowPer; 00717 Date bestQDate; 00718 for (Operation::Operationlist::const_iterator altIter 00719 = oper->getSubOperations().begin(); 00720 altIter != oper->getSubOperations().end(); ) 00721 { 00722 // Set a bookmark in the command list. 00723 CommandManager::Bookmark* topcommand = data->setBookmark(); 00724 bool nextalternate = true; 00725 00726 // Operations with 0 priority are considered unavailable 00727 const OperationAlternate::alternateProperty& props 00728 = oper->getProperties(*altIter); 00729 00730 // Filter out alternates that are not suitable 00731 if (props.first == 0.0 00732 || (effectiveOnly && !props.second.within(data->state->q_date)) 00733 || (!effectiveOnly && props.second.getEnd() > data->state->q_date) 00734 ) 00735 { 00736 ++altIter; 00737 if (altIter == oper->getSubOperations().end() && effectiveOnly) 00738 { 00739 // Prepare for a second iteration over all alternates 00740 effectiveOnly = false; 00741 altIter = oper->getSubOperations().begin(); 00742 } 00743 continue; 00744 } 00745 00746 // Establish the ask date 00747 ask_date = effectiveOnly ? origQDate : props.second.getEnd(); 00748 00749 // Find the flow into the requesting buffer. It may or may not exist, since 00750 // the flow could already exist on the top operationplan 00751 double sub_flow_qty_per = 0.0; 00752 if (buf) 00753 { 00754 Flow* f = (*altIter)->findFlow(buf, ask_date); 00755 if (f && f->getQuantity() > 0.0) 00756 sub_flow_qty_per = f->getQuantity(); 00757 else if (!top_flow_exists) 00758 { 00759 // Neither the top nor the sub operation have a flow in the buffer, 00760 // we're in trouble... 00761 // Restore the planning mode 00762 data->constrainedPlanning = originalPlanningMode; 00763 throw DataException("Invalid producing operation '" + oper->getName() 00764 + "' for buffer '" + buf->getName() + "'"); 00765 } 00766 } 00767 else 00768 // Default value is 1.0, if no matching flow is required 00769 sub_flow_qty_per = 1.0; 00770 00771 // Remember the first alternate 00772 if (!firstAlternate) 00773 { 00774 firstAlternate = *altIter; 00775 firstFlowPer = sub_flow_qty_per + top_flow_qty_per; 00776 } 00777 00778 // Constraint tracking 00779 if (*altIter != firstAlternate) 00780 // Only enabled on first alternate 00781 data->logConstraints = false; 00782 else 00783 { 00784 // Forget previous constraints if we are replanning the first alternate 00785 // multiple times 00786 data->planningDemand->getConstraints().pop(topConstraint); 00787 // Potentially keep track of constraints 00788 data->logConstraints = originalLogConstraints; 00789 } 00790 00791 // Create the top operationplan. 00792 // Note that both the top- and the sub-operation can have a flow in the 00793 // requested buffer 00794 CommandCreateOperationPlan *a = new CommandCreateOperationPlan( 00795 oper, a_qty, Date::infinitePast, ask_date, 00796 d, prev_owner_opplan, false 00797 ); 00798 if (!prev_owner_opplan) data->add(a); 00799 00800 // Create a sub operationplan 00801 data->state->q_date = ask_date; 00802 data->state->curDemand = NULL; 00803 data->state->curOwnerOpplan = a->getOperationPlan(); 00804 data->state->curBuffer = NULL; // Because we already took care of it... @todo not correct if the suboperation is again a owning operation 00805 data->state->q_qty = a_qty / (sub_flow_qty_per + top_flow_qty_per); 00806 00807 // Solve constraints on the sub operationplan 00808 double beforeCost = data->state->a_cost; 00809 double beforePenalty = data->state->a_penalty; 00810 if (search == PRIORITY) 00811 { 00812 // Message 00813 if (loglevel) 00814 logger << indent(oper->getLevel()) << " Alternate operation '" << oper->getName() 00815 << "' tries alternate '" << *altIter << "' " << endl; 00816 (*altIter)->solve(*this,v); 00817 } 00818 else 00819 { 00820 data->getSolver()->setLogLevel(0); 00821 try {(*altIter)->solve(*this,v);} 00822 catch (...) 00823 { 00824 data->getSolver()->setLogLevel(loglevel); 00825 // Restore the planning mode 00826 data->constrainedPlanning = originalPlanningMode; 00827 data->logConstraints = originalLogConstraints; 00828 throw; 00829 } 00830 data->getSolver()->setLogLevel(loglevel); 00831 } 00832 double deltaCost = data->state->a_cost - beforeCost; 00833 double deltaPenalty = data->state->a_penalty - beforePenalty; 00834 data->state->a_cost = beforeCost; 00835 data->state->a_penalty = beforePenalty; 00836 00837 // Keep the lowest of all next-date answers on the effective alternates 00838 if (effectiveOnly && data->state->a_date < a_date && data->state->a_date > ask_date) 00839 a_date = data->state->a_date; 00840 00841 // Now solve for loads and flows of the top operationplan. 00842 // Only now we know how long that top-operation lasts in total. 00843 if (data->state->a_qty > ROUNDING_ERROR) 00844 { 00845 // Multiply the operation reply with the flow quantity to obtain the 00846 // reply to return 00847 data->state->q_qty = data->state->a_qty; 00848 data->state->q_date = origQDate; 00849 data->state->curOwnerOpplan->createFlowLoads(); 00850 data->getSolver()->checkOperation(data->state->curOwnerOpplan,*data); 00851 data->state->a_qty *= (sub_flow_qty_per + top_flow_qty_per); 00852 00853 // Combine the reply date of the top-opplan with the alternate check: we 00854 // need to return the minimum next-date. 00855 if (data->state->a_date < a_date && data->state->a_date > ask_date) 00856 a_date = data->state->a_date; 00857 } 00858 00859 // Message 00860 if (loglevel && search != PRIORITY) 00861 logger << indent(oper->getLevel()) << " Alternate operation '" << oper->getName() 00862 << "' evaluates alternate '" << *altIter << "': quantity " << data->state->a_qty 00863 << ", cost " << deltaCost << ", penalty " << deltaPenalty << endl; 00864 00865 // Process the result 00866 if (search == PRIORITY) 00867 { 00868 // Undo the operationplans of this alternate 00869 if (data->state->a_qty < ROUNDING_ERROR) data->rollback(topcommand); 00870 00871 // Prepare for the next loop 00872 a_qty -= data->state->a_qty; 00873 plannedAlternate = true; 00874 00875 // As long as we get a positive reply we replan on this alternate 00876 if (data->state->a_qty > 0) nextalternate = false; 00877 00878 // Are we at the end already? 00879 if (a_qty < ROUNDING_ERROR) 00880 { 00881 a_qty = 0.0; 00882 break; 00883 } 00884 } 00885 else 00886 { 00887 double val = 0.0; 00888 switch (search) 00889 { 00890 case MINCOST: 00891 val = deltaCost / data->state->a_qty; 00892 break; 00893 case MINPENALTY: 00894 val = deltaPenalty / data->state->a_qty; 00895 break; 00896 case MINCOSTPENALTY: 00897 val = (deltaCost + deltaPenalty) / data->state->a_qty; 00898 break; 00899 default: 00900 LogicException("Unsupported search mode for alternate operation '" 00901 + oper->getName() + "'"); 00902 } 00903 if (data->state->a_qty > ROUNDING_ERROR && ( 00904 val + ROUNDING_ERROR < bestAlternateValue 00905 || (fabs(val - bestAlternateValue) < ROUNDING_ERROR 00906 && data->state->a_qty > bestAlternateQuantity) 00907 )) 00908 { 00909 // Found a better alternate 00910 bestAlternateValue = val; 00911 bestAlternateSelection = *altIter; 00912 bestAlternateQuantity = data->state->a_qty; 00913 bestFlowPer = sub_flow_qty_per + top_flow_qty_per; 00914 bestQDate = ask_date; 00915 } 00916 // This was only an evaluation 00917 data->rollback(topcommand); 00918 } 00919 00920 // Select the next alternate 00921 if (nextalternate) 00922 { 00923 ++altIter; 00924 if (altIter == oper->getSubOperations().end() && effectiveOnly) 00925 { 00926 // Prepare for a second iteration over all alternates 00927 effectiveOnly = false; 00928 altIter = oper->getSubOperations().begin(); 00929 } 00930 } 00931 } // End loop over all alternates 00932 00933 // Replan on the best alternate 00934 if (bestAlternateQuantity > ROUNDING_ERROR && search != PRIORITY) 00935 { 00936 // Message 00937 if (loglevel) 00938 logger << indent(oper->getLevel()) << " Alternate operation '" << oper->getName() 00939 << "' chooses alternate '" << bestAlternateSelection << "' " << search << endl; 00940 00941 // Create the top operationplan. 00942 // Note that both the top- and the sub-operation can have a flow in the 00943 // requested buffer 00944 CommandCreateOperationPlan *a = new CommandCreateOperationPlan( 00945 oper, a_qty, Date::infinitePast, bestQDate, 00946 d, prev_owner_opplan, false 00947 ); 00948 if (!prev_owner_opplan) data->add(a); 00949 00950 // Recreate the ask 00951 data->state->q_qty = a_qty / bestFlowPer; 00952 data->state->q_date = bestQDate; 00953 data->state->curDemand = NULL; 00954 data->state->curOwnerOpplan = a->getOperationPlan(); 00955 data->state->curBuffer = NULL; // Because we already took care of it... @todo not correct if the suboperation is again a owning operation 00956 00957 // Create a sub operationplan and solve constraints 00958 bestAlternateSelection->solve(*this,v); 00959 00960 // Now solve for loads and flows of the top operationplan. 00961 // Only now we know how long that top-operation lasts in total. 00962 data->state->q_qty = data->state->a_qty; 00963 data->state->q_date = origQDate; 00964 data->state->curOwnerOpplan->createFlowLoads(); 00965 data->getSolver()->checkOperation(data->state->curOwnerOpplan,*data); 00966 00967 // Multiply the operation reply with the flow quantity to obtain the 00968 // reply to return 00969 data->state->a_qty *= bestFlowPer; 00970 00971 // Combine the reply date of the top-opplan with the alternate check: we 00972 // need to return the minimum next-date. 00973 if (data->state->a_date < a_date && data->state->a_date > ask_date) 00974 a_date = data->state->a_date; 00975 00976 // Prepare for the next loop 00977 a_qty -= data->state->a_qty; 00978 00979 // Are we at the end already? 00980 if (a_qty < ROUNDING_ERROR) 00981 { 00982 a_qty = 0.0; 00983 break; 00984 } 00985 } 00986 else 00987 // No alternate can plan anything any more 00988 break; 00989 00990 } // End while loop until the a_qty > 0 00991 00992 // Forget any constraints if we are not short or are planning unconstrained 00993 if (a_qty < ROUNDING_ERROR || !originalLogConstraints) 00994 data->planningDemand->getConstraints().pop(topConstraint); 00995 00996 // Unconstrained plan: If some unplanned quantity remains, switch to 00997 // unconstrained planning on the first alternate. 00998 // If something could be planned, we expect the caller to re-ask this 00999 // operation. 01000 if (!originalPlanningMode && fabs(origQqty - a_qty) < ROUNDING_ERROR && firstAlternate) 01001 { 01002 // Switch to unconstrained planning 01003 data->constrainedPlanning = false; 01004 data->logConstraints = false; 01005 01006 // Message 01007 if (loglevel) 01008 logger << indent(oper->getLevel()) << " Alternate operation '" << oper->getName() 01009 << "' plans unconstrained on alternate '" << firstAlternate << "' " << search << endl; 01010 01011 // Create the top operationplan. 01012 // Note that both the top- and the sub-operation can have a flow in the 01013 // requested buffer 01014 CommandCreateOperationPlan *a = new CommandCreateOperationPlan( 01015 oper, a_qty, Date::infinitePast, origQDate, 01016 d, prev_owner_opplan, false 01017 ); 01018 if (!prev_owner_opplan) data->add(a); 01019 01020 // Recreate the ask 01021 data->state->q_qty = a_qty / firstFlowPer; 01022 data->state->q_date = origQDate; 01023 data->state->curDemand = NULL; 01024 data->state->curOwnerOpplan = a->getOperationPlan(); 01025 data->state->curBuffer = NULL; // Because we already took care of it... @todo not correct if the suboperation is again a owning operation 01026 01027 // Create a sub operationplan and solve constraints 01028 firstAlternate->solve(*this,v); 01029 01030 // Expand flows of the top operationplan. 01031 data->state->q_qty = data->state->a_qty; 01032 data->state->q_date = origQDate; 01033 data->state->curOwnerOpplan->createFlowLoads(); 01034 data->getSolver()->checkOperation(data->state->curOwnerOpplan,*data); 01035 01036 // Fully planned 01037 a_qty = 0.0; 01038 data->state->a_date = origQDate; 01039 } 01040 01041 // Set up the reply 01042 data->state->a_qty = origQqty - a_qty; // a_qty is the unplanned quantity 01043 data->state->a_date = a_date; 01044 assert(data->state->a_qty >= 0); 01045 assert(data->state->a_date >= data->state->q_date); 01046 01047 // Restore the planning mode 01048 data->constrainedPlanning = originalPlanningMode; 01049 data->logConstraints = originalLogConstraints; 01050 01051 // Increment the cost 01052 if (data->state->a_qty > 0.0) 01053 data->state->a_cost += data->state->curOwnerOpplan->getQuantity() * oper->getCost(); 01054 01055 // Make sure other operationplans don't take this one as owner any more. 01056 // We restore the previous owner, which could be NULL. 01057 data->state->curOwnerOpplan = prev_owner_opplan; 01058 01059 // Message 01060 if (loglevel>1) 01061 logger << indent(oper->getLevel()) << " Alternate operation '" << oper->getName() 01062 << "' answers: " << data->state->a_qty << " " << data->state->a_date 01063 << " " << data->state->a_cost << " " << data->state->a_penalty << endl; 01064 } 01065 01066 01067 }