Pegging resources to shipments in a pre-existing production plan

Abstract

In software systems for resource-constrained production planning (RCPP), it is often beneficial to determine a detailed association, or “pegging”, between the resources and the shipments that are enabled by those resources. The method implemented in the software systems is called “Pegging By Explosion” (PBE), for constructing a pegging of a production plan for an RCPP problem. The Pegging By Explosion technique takes a feasible production plan and reconstructs it, using its own specialized incremental allocation technique. A Pegging By Monitoring technique is applied to this reconstruction in order to produce the pegging. The reconstruction is accomplished by a specialized “explosion” technique related to the explosion technique of Material Requirements Planning (MRP).

1 . A computer implemented method for constructing a pegging of a production plan for a resource-constrained production planning (RCPP) problem, comprising the step of constructing the pegging after the production plan has already been generated.  
     
     
         2 . The computer implemented method recited in  claim 1 , wherein the step of constructing the pegging comprises the steps of: 
 reconstructing a modified version of the production plan by an incremental allocation technique, and    then applying a Pegging By Monitoring technique to the reconstructed production plan in order to produce the pegging.    
     
     
         3 . The computer implemented method recited in  claim 2 , wherein the step of reconstructing a modified verison of the production plan is accomplished by a series of “explosion” steps similar to an explosion technique of Material Requirements Planning (MRP).  
     
     
         4 . The computer implemented method recited in  claim 3 , wherein the method is restricted to be used only on Positive Consumption resource-constrained production planning (RCPP) problems and comprises of the steps of: 
 reading in a Positive Consumption RCPP problem,    reading in a feasible production plan for the problem,    either reading in a shipment sequence corresponding to the shipments in the production plan, or computing a default shipment sequence,    initializing the reconstructed production plan to zero,    initializing the pegging to zero,    proceeding through the triples (d*, td*, IncShipVol) in the shipment sequence, with each demand d* in period td*, and performing the following three steps:    employing a specialized explosion technique to construct an incremental production plan (denoted ProdVol I  ( ), StockVol I  ( ), ConsSupVol I  ( ), and ShipVol I  ( )) that specifies a feasible means of enabling a shipment of IncShipVol units to demand d* in period td* without using any resources that have already been pegged,    adding the incremental production plan to the reconstructed production plan, and    pegging the incremental production plan to the current shipment (d*, td*), and    reporting the pegging.    
     
     
         5 . The computer implemented method recited in  claim 4 , wherein the specialized explosion technique comprises the steps of: 
 initializing the incremental production plan to zero,    associating a quantity, ReqVol (r, tr), with each resource r in each period tr,    initializing all values of ReqVol (r, tr) to zero,    setting ShipVol I  (d*, td*) to IncShipVol,    setting ReqVol (DemRes (d*), td*) to IncShipVol,    proceeding through each resource rεAllRes in order of decreasing ResIdx (r) and performing the following five steps:    proceeding through each period trεAllPer in decreasing order and performing the following four steps: 
 netting the requirement against supply,  
 ∀jεProdOpns (r), performing the following step: 
 exploding the requirement to production by operation j, and  
 exploding the requirement to stock in period tr-1.  
 
   
     
     
         6 . The computer implemented method recited in  claim 5 , wherein the step netting the requirement against supply comprises the steps of: 
 setting ConsSupVol I  (r, tr)←Min ((ConsSupVol (r, tr)−ConsSupVol R  (r, tr)), ReqVol (r, tr)), and    setting ReqVol (r, tr)←+−ConsSupVol I  (r, tr),    and wherein the step exploding the requirement to production by operation j comprises the steps of:    setting ProdVol I  (j, tr)←Min ((ProdVol (j, tr)−ProdVol R  (j, tr)), ReqVol (r, tr)),    ∀r′εBOR (j), where BOR is Bill-of-Resources, performing the following three steps: 
 ∀tr′εAllPer, performing the following step: 
 setting ReqVol (r′, tr′)+UsageRate (j, tr, r′, tr′)*ProdVol I  (j, tr),  
 
 setting ReqVol (r, tr)←+−ProdVol I  (j, tr), and  
 wherein the step exploding the requirement to stock in period tr-1 comprises the steps of:  
   if tr=1, doing nothing, but otherwise performing the following three steps: 
 setting StockVol I  (r, tr-1)←Min ((StockVol (r, tr-1)−StockVol R  (r, tr-1)), ReqVol (r, tr)),  
 setting ReqVol (r, tr-1)←+StockVol I  (r, tr-1), and  
 setting ReqVol (r, tr)←+−StockVol I  (r, tr-1).  
   
     
     
         7 . The computer implemented method recited in  claim 6 , wherein the steps netting the requirement against supply, exploding the requirement to production by operation j, and exploding the requirement to stock in period tr-1 are performed in any order, where this method is called Pegging By Explosion Technique for Positive Consumption RCPP Problems, or PC-PBE technique.  
     
     
         8 . The computer implemented method recited in  claim 7  (the PC-PBE technique), used to construct a pegging of a production plan for any RCPP problem, by using the method within the steps of: 
 explicitly constructing an auxiliary problem and production plan identical to the original problem and production plan, except that 
 for each resource, an “auxiliary” operation is added that produces that resource and consumes no resources,  
 the negative consumption of each resource is replaced with production by the auxiliary operation for that resource, and  
 all negative usage rates are set to zero, and  
   applying the PC-PBE technique to the auxiliary problem and production plan, and    transferring the resulting pegging back into the original problem and production plan.    
     
     
         9 . The computer implemented method recited in  claim 7  (the PC-PBE technique). used to construct pegging of a production plan for any RCPP problem, by using the method within the the steps of: 
 conceptually defining the auxiliary problem and production plan identical to the original problem and production plan, except that 
 for each resource, an “auxiliary” operation is added that produces that resource and consumes no resources,  
 the negative consumption of each resource is replaced with production by the auxiliary operation for that resource, and  
 all negative usage rates are set to zero,  
   working with the original problem and production plan, and    performing a sequence of steps that are mathematically equivalent to those that the PC-PBE technique would be performing, if it were being applied to the auxiliary problem and production plan, whereby the method is called the Pegging By Explosion Technique for RCPP Problems, or the PBE technique.    
     
     
         10 . The computer implemented method recited in  claim 9  (the PBE technique). used to construct a pegging of a production plan for a variant of an RCPP problem that has been generalized so as to allow substitution in a Bill-of-Resources (BOR) structure, by using the method within the steps of: 
 conceptually defining a transformed RCPP problem and production plan that is equivalent to the original problem and production plan, but has no substitution,    working with the original problem and production plan, and    performing a sequence of steps that are mathematically equivalent to those that the PBE technique would be performing, if it were being applied to the transformed problem and production plan.    
     
     
         11 . The computer implemented method recited in  claim 9  (the PBE technique), used to construct a pegging of a production plan for a variant of an RCPP problem that has been generalized so as to allow, substitution in a Bill-of-Resources (BOR) structure and to permit violations of the resource constraints, by using the method within the steps of: 
 conceptually defining a transformed RCPP problem and production plan that is equivalent to the original problem and production plan, but has no substitution and does not violate any of the resource constraints,    working with the original problem and production plan, and    performing a sequence of steps that are mathematically equivalent to those that the PBE technique would be performing, if it were being applied to the transformed problem and production plan.    
     
     
         12 . The computer implemented method recited in  claim 11 , specifically applied to construct a pegging of the solution of a Material Requirements Planning problem.  
     
     
         13 . The computer implemented method recited in  claim 7 , wherein the method is restricted to be used only on problems in which Nperiods=1, where the method is made simpler to implement in the following ways: 
 by eliminating the concept of a period from all of the data and notation;    by eliminating the distinction between material resources and capacity resources;    by deleting all references to stock volume (StockVol ( )) and its pegging; and    by removing the exploding the requirement to stock step from the method.    
     
     
         14 . The computer implemented method recited in  claim 7 , wherein the method is restricted to be used only on problems in which each resource can only be produced by at most one operation, where the method is made simpler to implement in the following ways: 
 by eliminating the concept of an operation from all of the data and notation, eliminating all data associated with an operation and replacing it by corresponding data associated with a product, so that, e.g., ProdVol (j, ij) for operation j is replaced by ProdVol (r, tr) for product resource r;    by eliminating the following two steps from method: 
 ∀jεProdOpns (r), performing the following step: 
 exploding the requirement to production by operation j;  
 
   by replacing the above two steps with the following step: 
 exploding the requirement to production, if the resource is a product.  
   
     
     
         15 . The computer implemented method recited in  claim 7 , wherein the method is restricted to be used only on problems in which Nperiods=1 and in which each resource can only be produced by at most one operation, where the method is made simpler to implement in the following ways: 
 by eliminating the concept of a period from all of the data and notation;    by eliminating the distinction between material resources and capacity resources;    by deleting all references to stock volume (StockVol ( )) and its pegging;    by removing the exploding the requirement to stock step from the method,    by eliminating the concept of an operation from all of the data and notation, eliminating all data associated with an operation and replacing it by corresponding data associated with a product, so that, e.g., ProdVol (j, tj) for operation j is replaced by ProdVol (r, tr) for product resource r;    by eliminating the following two steps from method: 
 ∀jεProdOpns (r), performing the following step: 
 exploding the requirement to production by operation j;  
 
   by replacing the above two steps with the following step: 
 exploding the requirement to production, if the resource is a product.  
   
     
     
         16 . A computer readable medium containing code implementing a method for constructing a pegging of a production plan for a resource-constrained production planning (RCPP) problem, said method comprising the step of constructing the pegging after the production plan has already been generated.  
     
     
         17 . The computer readable medium recited in  claim 16 , wherein the step of constructing the pegging comprises the steps of: 
 reconstructing a modified version of the production plan by an incremental allocation technique, and    then applying a Pegging By Monitoring technique to the reconstructed production plan in order to produce the pegging.    
     
     
         18 . The computer readable medium recited in  claim 17 , wherein the step of reconstructing a modified verison of the production plan is accomplished by a series of “explosion” steps similar to an explosion technique of Material Requirements Planning (MRP).  
     
     
         19 . The computer readable medium recited in  claim 18 , wherein the method is restricted to be used only on Positive Consumption resource-constrained production planning (RCPP) problems and comprises of the steps of: 
 reading in a Positive Consumption RCPP problem,    reading in a feasible production plan for the problem,    either reading in a shipment sequence corresponding to the shipments in the production plan, or computing a default shipment sequence,    initializing the reconstructed production plan to zero,    initializing the pegging to zero,    proceeding through the triples (d*, td*, IncShipVol) in the shipment sequence, with each demand d* in period td*, and performing the following three steps: 
 employing a specialized explosion technique to construct an incremental production plan (denoted by ProdVol I  ( ), StockVol I  ( ), ConsSupVol I  ( ), and ShipVol I  ( ) that specifies a feasible means of enabling a shipment of IncShipVol units to demand d* in period td* without using any resources that have already been pegged,  
 adding the incremental production plan to the reconstructed production plan, and  
 pegging the incremental production plan to the current shipment (d*, td*), and  
   reporting the pegging.    
     
     
         20 . The computer readable medium recited in  claim 19 , wherein the specialized explosion technique comprises the steps of: 
 initializing the incremental production plan to zero,    associating a quantity, ReqVol (r, tr), with each resource r in each period tr,    initializing all values of ReqVol (r, tr) to zero,    setting ShipVol I  (d*, td*) to IncShipVol,    setting ReqVol (DemRes (d*), td*) to IncShipVol,    proceeding through each resource rεAllRes in order of decreasing ResIdx (r) and performing the following five steps:    proceeding through each period tr E AllPer in decreasing order and performing the following four steps: 
 netting the requirement against supply,  
 ∀jεProdOpns (r), performing the following step: 
 exploding the requirement to production by operation j, and  
 exploding the requirement to stock in period tr-1.  
 
   
     
     
         21 . The computer readable medium recited in  claim 20 , wherein the step netting the requirement against supply comprises the steps of: 
 setting ConsSupVol I  (r, tr)←Min ((ConsSupVol (r, tr)−ConsSupVol R  (r, tr)), ReqVol (r, tr)), and    setting ReqVol (r, tr)←+−ConsSupVol I  (r, tr),    and wherein the step exploding the requirement to production by operation j comprises the steps of:    setting ProdVol I  (I, tr)←Min ((ProdVol (I, tr)−ProdVol R  (j, tr)), ReqVol (r, tr)),    ∀r′εBOR (j), where BOR is Bill-of-Resources, performing the following three steps: 
 ∀tr′εAllPer, performing the following step: 
 setting ReqVol (r′, tr′)+UsageRate (j, tr, r′, tr′)*ProdVol I  (I, tr),  
 
 setting ReqVol (r, tr)←+−ProdVol I  (j, tr), and  
 wherein the step exploding the requirement to stock in period tr-1 comprises the steps of:  
   if tr=1, doing nothing, but otherwise performing the following three steps: 
 setting StockVol I  (r, tr-1)←Min ((StockVol (r, tr-1)−StockVol R  (r, tr-1)), ReqVol (r, tr)),  
 setting ReqVol (r, tr-1)←+StockVol I  (r, tr-1), and  
 setting ReqVol (r, tr)←+−StockVol I  (r, tr-1).  
   
     
     
         22 . The computer readable medium recited in  claim 20 , wherein the steps netting the requirement against supply, exploding the requirement to production by operation j, and exploding the requirement to stock in period tr-1 are performed in any order, where this method is called Pegging By Explosion Technique for Positive Consumption RCPP Problems, or PC-PBE technique.  
     
     
         23 . The computer readable medium recited in  claim 22  (the code implementing the PC-PBE technique) where in the method is used to construct a pegging of a production plan for any RCPP problem, by using the method within the steps of: 
 explicitly constructing an auxiliary problem and production plan identical to the original problem and production plan, except that 
 for each resource, an “auxiliary” operation is added that produces that resource and consumes no resources,  
 the negative consumption of each resource is replaced with production by the auxiliary operation for that resource, and  
 all negative usage rates are set to zero, and  
   applying the PC-PBE technique to the auxiliary problem and production plan, and    transferring the resulting pegging back into the original problem and production plan.    
     
     
         24 . The computer readable medium recited in  claim 22  (the code implementing the PC-PBE technique), wherein the method is used to construct a pegging of a production plan for any RCPP problem, by using the method within the steps of: 
 conceptually defining the auxiliary problem and production plan identical to the original problem and production plan, except that 
 for each resource, an “auxiliary” operation is added that produces that resource and consumes no resources,  
 the negative consumption of each resource is replaced with production by the auxiliary operation for that resource, and  
 all negative usage rates are set to zero,  
   working with the original problem and production plan, and    performing a sequence of steps that are mathematically equivalent to those that the PC-PBE technique would be performing, if it were being applied to the auxiliary problem and production plan, whereby the method is called Pegging By Explosion Technique for RCPP Problems, or the PBE technique.    
     
     
         25 . The computer readable method medium recited in  claim 24  (the code implementing the PBE technique), wherein the method is used to construct a pegging of a production plan for a variant of an RCPP problem that has been generalized so as to allow substitution in a Bill-of-Resources (BOR) structure, by using the method within the steps of: 
 conceptually defining a transformed RCPP problem and production plan that is equivalent to the original problem and production plan, but has no substitution,    working with the original problem and production plan, and    performing a sequence of steps that are mathematically equivalent to those that the PBE technique would be performing, if it were being applied to the transformed problem and production plan.    
     
     
         26 . The computer readable medium recited in  claim 24  (the code implementing the PBE technique), wherein the method is used to construct a pegging of a production plan for a variant of an RCPP problem that has been generalized so as to allow substitution in a Bill-of-Resources (BOR) structure and to permit violations of the resource constraints, by using the method within the steps of: 
 conceptually defining a transformed RCPP problem and production plan that is equivalent to the original problem and production plan, but has no substitution and does not violate any of the resource constraints,    working with the original problem and production plan, and    performing a sequence of steps that are mathematically equivalent to those that the PBE technique would be performing, if it were being applied to the transformed problem and production plan.    
     
     
         27 . The computer readable medium recited in  claim 26 , specifically applied to construct a pegging of the solution of a Material Requirements Planning problem.  
     
     
         28 . The computer readable medium recited in  claim 22 , wherein the method is restricted to be used only on problems in which Nperiods= 1 , where the method is made simpler to implement in the following ways: 
 by eliminating the concept of a period from all of the data and notation;    by eliminating the distinction between material resources and capacity resources;    by deleting all references to stock volume (StockVol  0 ) and its pegging; and    by removing the exploding the requirement to stock step from the method.    
     
     
         29 . The computer readable medium recited in  claim 22 , wherein the method is restricted to be used only on problems in which each resource can only be produced by at most one operation, where the method is made simpler to implement in the following ways: 
 by eliminating the concept of an operation from all of the data and notation, eliminating all data associated with an operation and replacing it by corresponding data associated with a product, so that, e.g., ProdVol (j, tj) for operation j is replaced by ProdVol (r, tr) for product resource r;    by eliminating the following two steps from method: 
 ∀jεProdOpns (r), performing the following step: 
 exploding the requirement to production by operation j;  
 
   by replacing the above two steps with the following step:    exploding the requirement to production, if the resource is a product.    
     
     
         30 . The computer readable medium recited in  claim 22 , wherein the method is restricted to be used only on problems in which Nperiods=1 and in which each resource can only be produced by at most one operation, where the method is made simpler to implement in the following ways: 
 by eliminating the concept of a period from all of the data and notation;    by eliminating the distinction between material resources and capacity resources;    by deleting all references to stock volume (StockVol ( )) and its pegging;    by removing the exploding the requirement to stock step from the method.    by eliminating the concept of an operation from all of the data and notation, eliminating all data associated with an operation and replacing it by corresponding data associated with a product, so that, e.g., ProdVol (j, tj) for operation j is replaced by ProdVol (r, tr) for product resource r;    by eliminating the following two steps from method: 
 ∀jεProdOpns (r), performing the following step: 
 exploding the requirement to production by operation j;  
 
   by replacing the above two steps with the following step: 
 exploding the requirement to production, if the resource is a product.