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