Patent ID: 11858159
Assignee: GUANGDONG UNIVERSITY OF TECHNOLOGY
Field: Machine tools (Mechanical engineering)
Classification: CPC B  Y | IPC B

Claim 0:
1. A cutting stock method for a rectangular defective sheet, comprising:
(S1) acquiring information of the rectangular defective sheet, wherein the information comprises size information of the rectangular defective sheet, size information of target blocks, and location information of a defect;
(S2) acquiring a cutting position discrete set of the rectangular defective sheet; cutting the rectangular defective sheet into two first sub-sheets according to the cutting position discrete set; if a first sub-sheet is non-defective, proceeding to step (S3), otherwise, proceeding to step (S4);
(S3) calculating a cutting position discrete set of a non-defective first sub-sheet by using a first cutting position searching algorithm; and cutting the non-defective first sub-sheet into a plurality of target blocks according to the cutting position discrete set of the non-defective first sub-sheet;
wherein the step (S3) is performed through steps of:
(S30) acquiring size information of the plurality of target blocks and the size information of the first sub-sheet; and according to width and height of the plurality of target blocks, producing combined blocks varying in size;
setting a bottom left vertex of the rectangular defective sheet as an origin of a Cartesian coordinate system; generating a width combined point set within a dimensional boundary of the rectangular defective sheet based on the width of the plurality of target blocks with the origin as reference; and generating a height combined point set within the dimensional boundary of the rectangular defective sheet based on the height of the plurality of target blocks with the origin as reference;
for an x-axis discrete set of the rectangular defective sheet, successively subtracting each point r in the x-axis discrete set from a width w of the rectangular defective sheet; finding a maximum point not greater than w−r from the width combined point set followed by adding to the x-axis discrete set; and for a y-axis discrete set of the rectangular defective sheet, successively subtracting each point r in the y-axis discrete set from a height h of the rectangular defective sheet; finding a maximum point not greater than h−r from the height combined point set followed by adding to the y-axis discrete set;
wherein the x-axis discrete set Rv(w) and the y-axis discrete set Rv(h), respectively expressed as:, R
          v
         
         (
         w
         )
        
        =
        
         
                    z
         
         ∈
         
          
           N
           v
          
          (
          w
          )
         
        
       
       }
      
      ;
      and
     
     ⁢
     

     
      
       
        R
        v
       
       (
       h
       )
      
      =
      
       
                z
       
       ∈
       
        
         N
         v
        
        (
        h
        )
       
      
     
    
    }
   
   ;
  
  ⁢
  

  
   
    
     wherein
        
         
    =
    
     max
     ⁢
     
      {
      
       z
       ❘
       
        z
        ∈
        
         
          N
          v
         
         (
         w
         )
        
       
      
      }
     
    
   
   ;
   
        =
    
     max
     ⁢
     
      {
      
       z
       ❘
       
        z
        ∈
        
         
          N
          h
         
         (
         h
         )
        
       
      
      }
     
    
   
   ;
  
  ⁢
  

  
   
    
     
      N
      v
     
     (
     w
     )
    
    =
    
     {
     
      
       
        z
        ❘
        z
       
       =
       
        
         
          ∑
           
         
         
          i
          =
          1
         
         n
        
        ⁢
        
         α
         i
        
        ⁢
        
         w
         i
         s
        
       
      
      ,
      
       0
       ≤
       z
       ≤
       w
      
      ,
      
       
        α
        i
       
       ∈
       
        {
        
         0
         ,
         1
         ,
         2
         ,
         …
        
        }
       
      
      ,
      
       i
       ∈
       I
      
     
     }
    
   
   ;
  
  ⁢
  

  
   
    
     
      N
      h
     
     (
     h
     )
    
    =
    
     {
     
      
       
        z
        ❘
        z
       
       =
       
        
         
          ∑
           
         
         
          i
          =
          1
         
         n
        
        ⁢
        
         α
         i
        
        ⁢
        
         h
         i
         s
        
       
      
      ,
      
       0
       ≤
       z
       ≤
       h
      
      ,
      
       
        α
        i
       
       ∈
       
        {
        
         0
         ,
         1
         ,
         2
         ,
         …
        
        }
       
      
      ,
      
       i
       ∈
       I
      
     
     }
    
   
   ;
  
 

 w and h represent the width and height of the rectangular defective sheet, respectively; wis and his represent a width and height of a target block i, respectively; I represents a target block set; Nv(w) represents the width combined point set; Nh(h) represents the height combined point set;  represents a maximum point not greater than n in Nv(w);  represents a maximum point not greater than n in Nh(h); and αi represents the number of target blocks, and α=1, 2, . . . ; and z represents a point in Nh(h);
(S31) searching for a cutting position discrete set within one-half a width of the non-defective first sub-sheet;
(S32) calculating a maximum size of the plurality of target blocks cut from the non-defective first sub-sheet based on the width and height of the plurality of target blocks; and
(S33) cutting the non-defective first sub-sheet according to a cutting position discrete set corresponding to the maximum size;

(S4) calculating a cutting position discrete set of a defective first sub-sheet by using a second cutting position searching algorithm; and cutting the defective first sub-sheet into two second sub-sheets according to the cutting position discrete set of the defective first sub-sheet; if a second sub-sheet is non-defective, performing step (S3); otherwise, repeating step (S4);
wherein the cutting position discrete set of the defective first sub-sheet is calculated through steps of:
for an x-axis discrete set of the defective first sub-sheet, subtracting each point r in the x-axis discrete set in turn from a width w of the rectangular defective sheet and a left boundary of a defect j; finding a maximum point not larger than w−r and xjd−r from the width combined point set followed by adding to the x-axis discrete set; for a y-axis discrete set of the defective first sub-sheet, subtracting each point r in the y-axis discrete set in turn from a height h of the rectangular defective sheet and a lower boundary yjd of the defect j; finding a maximum point not larger than h−r and yjd−r from the height combined point set followed by adding to the y-axis discrete set; and
defining the x-axis discrete set of the defective first sub-sheet as Rdv(w) and the y-axis discrete set of the defective first sub-sheet as Rdh(h), respectively expressed by:

Rdv(w)=z∈Ndv(w)}; and

Rdh(h)=z∈Ndh(h)};

wherein, N
      d
      v
     
     (
     w
     )
    
    =
    
     
      
       N
       v
      
      (
      w
      )
     
     ⋃
     

     
      {
      
       
        
         z
         ❘
         z
        
        =
        
         
          x
          j
          d
         
         +
         
          w
          j
          d
         
         +
         v
        
       
       ,
       
        j
        ∈
        D
       
       ,
       
        v
        ∈
        
         
          N
          v
         
         (
         w
         )
        
       
       ,
       
        0
        ≤
        z
        ≤
        w
       
      
      }
     
    
   
   ;
  
  ⁢
  

  
   
    
     
      N
      d
      h
     
     (
     h
     )
    
    =
    
     
      
       N
       v
      
      (
      h
      )
     
     ⋃
     
      {
      
       
        
         z
         ❘
         z
        
        =
        
         
          y
          j
          d
         
         +
         
          h
          j
          d
         
         +
         v
        
       
       ,
       
        j
        ∈
        D
       
       ,
       
        v
        ∈
        
         
          N
          h
         
         (
         h
         )
        
       
       ,
       
        0
        ≤
        z
        ≤
        h
       
      
      }
     
    
   
   ;
  
  ⁢
  

  
   
    
     
      N
      v
     
     (
     w
     )
    
    =
    
     {
     
      
       
        z
        ❘
        z
       
       =
       
        
         
          ∑
           
         
         
          i
          =
          1
         
         n
        
        ⁢
        
         α
         i
        
        ⁢
        
         w
         i
         s
        
       
      
      ,
      
       0
       ≤
       z
       ≤
       w
      
      ,
      
       
        α
        i
       
       ∈
       
        {
        
         0
         ,
         1
         ,
         2
         ,
         …
        
        }
       
      
      ,
      
       i
       ∈
       I
      
     
     }
    
   
   ;
  
  ⁢
  

  
   
    
     
      N
      h
     
     (
     h
     )
    
    =
    
     {
     
      
       
        z
        ❘
        z
       
       =
       
        
         
          ∑
           
         
         
          i
          =
          1
         
         n
        
        ⁢
        
         α
         i
        
        ⁢
        
         h
         i
         s
        
       
      
      ,
      
       0
       ≤
       z
       ≤
       h
      
      ,
      
       
        α
        i
       
       ∈
       
        {
        
         0
         ,
         1
         ,
         2
         ,
         …
        
        }
       
      
      ,
      
       i
       ∈
       I
      
     
     }
    
   
   ;
  
  ⁢
  

  
   
        =
    
     max
     ⁢
     
      {
      
       z
       ❘
       
        z
        ∈
        
         
          N
          v
         
         (
         w
         )
        
       
      
      }
     
    
   
   ;
  
  ⁢
  

  
   
        =
    
     max
     ⁢
     
      {
      
       z
       ❘
       
        z
        ∈
        
         
          N
          h
         
         (
         h
         )
        
       
      
      }
     
    
   
   ;
  
 

w and h represent the width and height of the rectangular defective sheet, respectively; wis and his represent the width and height of the target block I, respectively; I represents the target block set; xjd, yjd are coordinates of a lower left corner of the defect j; wjd and hjd are a width and height of the defect j, respectively; and D is a defect set; Nv(w) represents the width combined point set; Nh(h) represents the height combined point set;  represents a maximum point not greater than n in Nv(w);  represents a maximum point not greater than n in Nh(h); and α represents the number of combined target blocks, and α=1, 2, . . . ; and z represents a point in Nh(h);

(S5) calculating a sum of sizes of the plurality of target blocks; and selecting a cutting plan corresponding to the largest sum of numbers as an optimal cutting solution;
wherein the sum of sizes of the plurality of target blocks is calculated through steps of:
for a non-defective sub-sheet S=(w,h), defining g(w,h) as a maximal size obtained by guillotine cutting; and calculating the maximal size g(w,h) through the following equation:, g
    ⁡
    (
    
     w
     ,
     h
    
    )
   
   =
   
    max
    ⁢
    
     {
     
      
       
        {
        
         
          v
          i
         
         ·
         
          ⌊
          
           w
           
            w
            i
            s
           
          
          ⌋
         
         ·
         
          ⌊
          
           h
           
            h
            i
            s
           
          
          ⌋
         
        
        }
       
       ❘
       
        
         w
         i
         s
        
        ≤
        w
       
      
      ,
      
       
        h
        i
        s
       
       ≤
       h
      
      ,
      
       i
       =
       1
      
      ,
      2
      ,
      
       …
       ⁢
         
       n
      
     
     }
    
   
  
  ;
 

wherein wis and his represent a width and height of the target block i, respectively; vi represents a size of the target block i; n represents a type of the target block; and w and h represent a width and height of a sub-sheet, respectively; and
(S6) cutting the rectangular defective sheet according to the cutting position discrete set corresponding to the optimal cutting solution.