System and method for cutting rectangular sheet stock with defects

11858159 ยท 2024-01-02

Assignee

Inventors

Cpc classification

International classification

Abstract

A cutting stock method for a rectangular sheet with defects includes: acquiring information of the rectangular defective sheet, including dimension information of the rectangular sheet and target blocks, and location information of the defects; acquiring a cutting position discrete set of the rectangular sheet; cutting the rectangular sheet according to the cutting position discrete set into a plurality of target blocks; calculating a sum of values of the target blocks, and selecting an optimal cutting solution with the largest sum of values; and cutting the rectangular sheet according to the optimal cutting solution.

Claims

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 wr 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 hr from the height combined point set followed by adding to the y-axis discrete set; wherein the x-axis discrete set R.sup.v(w) and the y-axis discrete set R.sup.v(h), respectively expressed as: R v ( w ) = z N v ( w ) } ; and R v ( h ) = z N v ( h ) } ; wherein = max { z .Math. z N v ( w ) } ; = max { z .Math. z N h ( h ) } ; N v ( w ) = { z .Math. z = .Math. i = 1 n i w i s , 0 z w , i { 0 , 1 , 2 , .Math. } , i I } ; N h ( h ) = { z .Math. z = .Math. i = 1 n i h i s , 0 z h , i { 0 , 1 , 2 , .Math. } , i I } ; w and h represent the width and height of the rectangular defective sheet, respectively; w.sub.i.sup.s and h.sub.i.sup.s represent a width and height of a target block i, respectively; I represents a target block set; N.sup.v(w) represents the width combined point set; N.sup.h(h) represents the height combined point set; custom character represents a maximum point not greater than n in N.sup.v(w); custom character represents a maximum point not greater than n in N.sup.h(h); and .sub.i represents the number of target blocks, and =1, 2, . . . ; and z represents a point in N.sup.h(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 wr and x.sub.j.sup.dr 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 y.sub.j.sup.d of the defect j; finding a maximum point not larger than hr and y.sub.j.sup.dr 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 R.sub.d.sup.v(w) and the y-axis discrete set of the defective first sub-sheet as R.sub.d.sup.h(h), respectively expressed by:
R.sub.d.sup.v(w)=custom characterzN.sub.d.sup.v(w)}; and
R.sub.d.sup.h(h)=custom characterzN.sub.d.sup.h(h)}; wherein N d v ( w ) = N v ( w ) .Math. { z .Math. z = x j d + w j d + v , j D , v N v ( w ) , 0 z w } ; N d h ( h ) = N v ( h ) .Math. { z .Math. z = y j d + h j d + v , j D , v N h ( h ) , 0 z h } ; N v ( w ) = { z .Math. z = .Math. i = 1 n i w i s , 0 z w , i { 0 , 1 , 2 , .Math. } , i I } ; N h ( h ) = { z .Math. z = .Math. i = 1 n i h i s , 0 z h , i { 0 , 1 , 2 , .Math. } , i I } ; = max { z .Math. z N v ( w ) } ; = max { z .Math. z N h ( h ) } ; w and h represent the width and height of the rectangular defective sheet, respectively; w.sub.i.sup.s and h.sub.i.sup.s represent the width and height of the target block I, respectively; I represents the target block set; x.sub.j.sup.d, y.sub.j.sup.d are coordinates of a lower left corner of the defect j; w.sub.j.sup.d and h.sub.j.sup.d are a width and height of the defect j, respectively; and D is a defect set; N.sup.v(w) represents the width combined point set; N.sup.h(h) represents the height combined point set; custom character represents a maximum point not greater than n in N.sup.v(w); custom character represents a maximum point not greater than n in N.sup.h(h); and represents the number of combined target blocks, and =1, 2, . . . ; and z represents a point in N.sup.h(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 .Math. .Math. w w i s .Math. .Math. .Math. h h i s .Math. } .Math. w i s w , h i s h , i = 1 , 2 , .Math. n } ; wherein w.sub.i.sup.s and h.sub.i.sup.s represent a width and height of the target block i, respectively; v.sub.i 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.

2. The cutting stock method of claim 1, wherein the number of the defect on the rectangular defective sheet is D={1, 2, . . . , m}; coordinates of a lower left corner of each defect jD are (x.sub.j.sup.d, y.sub.j.sup.d); and a width and height of each defect are w.sub.j.sup.d and h.sub.j.sup.d, respectively; the rectangular defective sheet has a width of w and a height of h; and I types of target blocks with a width of w.sub.i.sup.s, a height of h.sub.i.sup.s, and a size of v.sub.i are cut from the rectangular defective sheet, and l={1, 2, . . . , n}; the target blocks are not intersected with the defect, and are configured to have a fixed orientation and to be unable to rotate; and dimensions of the rectangular defective sheet, the target blocks and the defect are all integers.

3. A cutting stock system, comprising: a memory; a processor; and a computer program stored on the memory; wherein the computer program is configured to be executed by the processor; and the processor is configured to execute the computer program to implement the cutting stock method of claim 1.

4. A non-transitory computer-readable storage medium, wherein a computer program is stored on the computer-readable storage medium; and the computer program is configured to be executed by a processor to implement the cutting stock method of claim 1.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

(1) The patent or application file contains FIGS. 1-2 executed in color. Copies of this patent or patent application publication with color drawing(s) will be provided by the Office upon request and payment of the necessary fee.

(2) FIG. 1 schematically illustrates a packing pattern for a rectangular defective sheet according to an embodiment of this disclosure;

(3) FIG. 2 schematically illustrates a packing process according to an embodiment of this disclosure;

(4) FIG. 3 is a flow chart of the cutting stock method according to an embodiment of this disclosure;

(5) FIG. 4 is a flow chart of a cutting position searching algorithm for a non-defective sheet according to an embodiment of this disclosure; and

(6) FIG. 5 is a flow chart of a cutting position searching algorithm for a defective board according to an embodiment of this disclosure.

DETAILED DESCRIPTION OF EMBODIMENTS

(7) Technical solutions of this application will be described in detail below with reference to embodiments and accompanying drawings, where the same or similar reference signs indicate the same or similar elements or elements having the same or similar functions. The embodiments described below with reference to the accompanying drawings are exemplary, which are merely intended to explain this application and are not to limit the present disclosure.

(8) As used herein, the terms, such as longitudinal, transverse, upper, lower, front, back, left, right, vertical, horizontal, top, bottom, inside, and outside, are based on the orientation or positional relationships shown in the accompanying drawings, and are merely intended to facilitate and simplify the description of the present disclosure, rather than indicating or implying that the device or element referred to must have a particular orientation, or be constructed and operated in a particular orientation. Therefore, these terms should not be construed as limitations for this application. In addition, terms first and second may explicitly or implicitly indicate the presence of one or more of the features limited thereby. The terms first and second used herein are intended to distinguish these features without implying any order or priority.

(9) In the description of the present disclosure, unless otherwise stated, the term plurality means two or more.

(10) In the description of the present disclosure, unless otherwise specified, the terms mounting, connection, joint should be understood in a broad sense. For example, the term connection can be a fixed connection, removable connection, or integral connection; a mechanical connection or electrical connection; a direct connection or indirect connection through an intermediate medium, or an internal connection of two components. For one of ordinary skill in the art, the specific meaning of the above terms in the description can be understood in specific cases.

(11) A cutting stock method for a rectangular defective sheet will be described in this embodiment referring to FIGS. 1-5.

(12) Provided is a cutting stock method for a rectangular defective sheet, which includes the following steps.

(13) (S1) Information of the rectangular defective sheet is acquired, where the information includes size information of the rectangular defective sheet, size information of a target blocks, and location information of a defect.

(14) (S2) A cutting position discrete set of the rectangular defective sheet is acquired. The rectangular defective sheet is cut once according to the cutting position discrete set to produce two first sub-sheets. If a first sub-sheet is non-defective, step (S3) is performed, otherwise, step (S4) is performed.

(15) (S3) The non-defective first sub-sheet is cut into a plurality of target blocks according to a cutting position discrete set of the non-defective first sub-sheet.

(16) (S4) The first defective first sub-sheet is cut into two second sub-sheets according to a cutting position discrete set of the defective first sub-sheets. If a second sub-sheet is non-defective, step (S3) is performed; and if the second sub-sheet is defective, then step (S4) is repeated.

(17) (S5) A sum of sizes of the plurality of target blocks is calculated. A cutting plan corresponding to the largest sum of sizes is selected as an optimal cutting solution.

(18) (S6) The rectangular defective sheet is cut according to the cutting position discrete set corresponding to the optimal cutting solution.

(19) Specifically, this application provides a cutting stock method aiming at layout problems of the rectangular defective sheet under constraints of guillotine. For a defective sheet or a non-defective sheet, two cutting position search algorithms are respectively adopted herein. Based on the size information of the target block and the location information of the defects, a cutting position discrete set is calculated without losing the optimal solution. The rectangular sheet is cut by using this discrete set, which can significantly reduce the search space of the layout process and thus enhance the layout efficiency in production.

(20) Specifically, in the layout method provided herein, the size information of the rectangular defective sheet and the target block, and the coordinate information of the defects are acquired. Then the cutting position discrete set in the rectangular defective sheet is calculated through the cutting position search algorithm. The rectangular defective sheet is cut according to the points in the discrete set. Each cutting will produce two sub-sheets, including a non-defective sheet and a defective sheet. The type of the sub-sheets is determined after each cutting. If the sub-sheet is non-defective, then the non-defective sub-sheet is cut into the target block as required, and the size of the target block is also calculated. If the sub-sheet is defective, the iterative search continues according to the cutting position discrete set of the defective sub-sheet for the next cutting, so as to gradually divide the defective sub-sheet into multiple non-defective sub-sheets and defective sub-sheets until the area of the defective sub-sheet is approximately equal to the defective region. The sizes of all the obtained target blocks are added up to obtain the sum of the sizes. All possible cutting positions are traversed, and the sum of the sizes of target blocks obtained by each cutting solution is calculated and stored. Different cutting solutions are traversed, the above steps for cutting and calculating and storing the sizes are repeated. Then the maximum sizes obtained by those cutting solutions are compared to find the cutting solution corresponding to the largest sum of sizes as the optimal cutting solution, which is then used for practical production.

(21) The cutting stock method provided herein is applied to solve the layout problems of two-dimensional (2D) rectangular sheets under constraints of guillotine cutting. The guillotine cutting refers to that during cutting, a single cutting action must be made from one side of the rectangular sheet to the opposite side thereof to divide the rectangular sheet into two separate small rectangular blocks, where the set of cutting positioning points is called the discrete set. In this case, the rectangular sheet is cut several times to form a plurality of rectangular sub-sheets, which are neither scrap nor goods and are called sub-sheets. Those sub-sheets are divided into P-sheets (non-defective sheets) and C-sheets (defective sheets), according to whether they contain defects or not. The position where the guillotine cutting is made on the sub-sheets is called the cutting position. The target block is the non-defective sheet cut from the sub-sheets. The size of the target block is set according to the requirements of the product.

(22) In some embodiments, in step (S3), the cutting position discrete set of the non-defective sheet is calculated by a first cutting position search algorithm through the following steps.

(23) The size information of target blocks and the size information of the rectangular defective sheet are acquired. The target blocks are subjected to linear combination according to length and width thereof to produce combined blocks varying in size.

(24) A bottom left vertex of the rectangular defective sheet is set as an origin of Cartesian coordinate system. A width combined point set within a dimensional boundary of the rectangular defective sheet is generated based on linear combinations of width of the target blocks with the origin as reference. A height combined point set within a dimensional boundary of the rectangular defective sheet is generated based on linear combinations of height of the target blocks with the origin as reference.

(25) For an x-axis discrete set of the rectangular defective sheet, each point r in the x-axis discrete set is subtracted from a width w of the rectangular defective sheet. A maximum point not greater than wr is found from the width combined point set, and the maximum point is then added to the x-axis discrete set. Similar operations are performed on a y-axis discrete set of the rectangular defective sheet.

(26) The x-axis discrete set of the rectangular defective sheet is denoted as R.sup.v(w) and the y-axis discrete set of the rectangular defective sheet is denoted as R.sup.v(h), respectively expressed by:

(27) R v ( w ) = z N v ( w ) } ; and R v ( h ) = z N v ( h ) } ; where = max { z .Math. z N v ( w ) } ; = max { z .Math. z N h ( h ) } ; N v ( w ) = { z .Math. z = .Math. i = 1 n i w i s , 0 z w , i { 0 , 1 , 2 , .Math. } , i I } ; N h ( h ) = { z .Math. z = .Math. i = 1 n i w i s , 0 z h , i { 0 , 1 , 2 , .Math. } , i I } ;
w and h represent a width and height of the rectangular defective sheet, respectively; w.sub.i.sup.s and h.sub.i.sup.s represent a width and height of a target block i, respectively; I represents a target block set; N.sup.v(w) represents the width combined point set; N.sup.h(h) represents the height combined point set; custom character represents a maximum point not greater than n in N.sup.v(w); custom character represents a maximum point not greater than n in N.sup.h(h); and represents the number of combined target blocks, and =1, 2, . . . ; and z represents a point in N.sup.h(h).

(28) In some embodiments, in step (S4), the cutting position discrete set of the defective first sub-sheet is calculated by a second cutting position searching algorithm through the following steps.

(29) For an x-axis discrete set of the defective first sub-sheet, each point r in the point set is subtracted from a width w of the rectangular defective sheet and a left boundary of a defect j. A maximum point not larger than wr and x.sub.j.sup.dr is found from the length combined point set, and the maximum point is added to the x-axis discrete set. Similar operations are performed on a y-axis discrete set of the defective first sub-sheet considering a height h of the rectangular defective sheet and a lower boundary y.sub.j.sup.d of defect j.

(30) The x-axis discrete set of the defective first sub-sheet is donated as R.sub.d.sup.v(w) and the y-axis discrete set of the defective first sub-sheet is donated as R.sub.d.sup.h(h), respectively expressed by:

(31) R d v ( w ) = z N d v ( w ) } ; and R d h ( h ) = z N d h ( h ) } ; where N d v ( w ) = N v ( w ) .Math. { z .Math. z = x j d + w j d + v , j D , v N v ( w ) , 0 z w } ; N d h ( h ) = N v ( h ) .Math. { z .Math. z = y j d + h j d + v , j D , v N h ( h ) , 0 z h } ; N v ( w ) = { z .Math. z = .Math. i = 1 n i w i s , 0 z w , i { 0 , 1 , 2 , .Math. } , i I } ; N h ( h ) = { z .Math. z = .Math. i = 1 n i h i s , 0 z h , i { 0 , 1 , 2 , .Math. } , i I } ; = max { z .Math. z N v ( w ) } ; = max { z .Math. z N h ( h ) } ;

(32) w and h represent a width and height of the rectangular defective sheet, respectively; w.sub.i.sup.s and h.sub.i.sup.s represent the width and height of the target block I, respectively; I represents the target block set; x.sub.j.sup.d, y.sub.j.sup.d are coordinates of a lower left corner of the defect j; w.sub.j.sup.d and h.sub.j.sup.d are a length and width of the defect j, respectively; and D is a defect set; N.sup.v(w) represents the width combined point set; N.sup.h(h) represents the height combined point set; custom character represents a maximum point not greater than n in N.sup.v(w); custom character represents a maximum point not greater than n in N.sup.h(h); and a represents the number of combined target blocks, and =1, 2, . . . ; and z represents a point in N.sup.h(h).

(33) Specifically, for the defective sheet, the influence of defects needs to be considered on the basis of the non-defective discrete points. When calculating the combined point, besides the discrete points generated with the bottom left vertex of the cut board as a reference, the x-axis discrete points generated with the right boundary of the defect as a reference and the y-axis discrete points generated with the right boundary of the defect as a reference should be considered.

(34) In some embodiments, in step (S3), the non-defective first sub-sheet is cut through the following steps.

(35) (S31) A cutting position discrete point set within one-half a width of the non-defective first sub-sheet is searched.

(36) (S32) A maximum size of the plurality of target blocks that can be cut from the non-defective first sub-sheet is calculated based on all the linear combinations of width and height of the target blocks.

(37) (S33) The non-defective first sub-sheet is cut according to a cutting position discrete set corresponding to the maximum size.

(38) Specifically, since the non-defective sheet is rectangular, symmetrical, and free of defective regions, the size of the target block can be read directly. Moreover, the cutting position discrete set within one-half the length of the target block can be searched iteratively according to the size of the target block, so as to obtain the cutting plan corresponding to the maximum size of the target block. The non-defective sheet can be divided into a plurality of target blocks according to the cutting positions discrete set, enhancing the searching efficiency.

(39) In some embodiments, the number of the defects on the rectangular defective sheet is D={1, 2, . . . , m}; coordinates of a lower left corner of each defect jD are (x.sub.j.sup.d, y.sub.j.sup.d); and a width and height of each defect are w.sub.j.sup.d and h.sub.j.sup.d, respectively; the rectangular defective sheet has a width of w and a height of h respectively, and I types of target blocks with a width of w.sub.i.sup.s, a height of h.sub.i.sup.s, and a size of v.sub.i are cut from the rectangular defective sheet a constraint of guillotine cutting, and I={1, 2, . . . , n}; the target blocks are not intersected with the defect, and are configured to have a fixed orientation and to be unable to rotate; and dimensions of the rectangular defective sheet, the target blocks and the defect are all integers.

(40) Specifically, the defective regions and target block areas are pre-defined herein to render easy marking for different defective regions and target blocks in the cutting position search algorithm, which facilitates the search and calculation of the algorithm.

(41) In some embodiments, in step (S5), the sum of sizes of the plurality of target blocks is calculated through the following steps.

(42) The non-defective sub-sheet S=(w, h) is cut into rectangular blocks to obtain the maximum sum of sizes from n solutions, expressed by:

(43) g ( w , h ) = max { { v i .Math. .Math. w w i s .Math. .Math. .Math. h h i s .Math. } .Math. w i s w , h i s h , i = 1 , 2 , .Math. n } ;

(44) where w.sub.i.sup.s and h.sub.i.sup.s represent a length and width of the target block i, respectively; v.sub.i represents a size of the target block i; n represents a type of the target block; and w and h represent a length and width of a sub-sheet, respectively.

(45) In this embodiment, the information of the target block and the defective region is input in the algorithm and initialized with g.sub.0=0. The type of sub-boards is determined, and the cutting position discrete set is calculated for the defective and non-defective sheets, respectively. The cutting position discrete set at different locations are traversed and compared. Specifically, the optimal sizes of two sub-sheets g(w.sub.s1, h.sub.s1) and g(w.sub.s2, h.sub.s2) obtained after each cutting are calculated, and g.sub.i is also calculated, where g.sub.i=g(w.sub.s1, h.sub.s1)+g(w.sub.s2, h.sub.s2); and w.sub.s1, h.sub.s1, w.sub.s2, and h.sub.s2 are the position parameters of the target block. The above steps are traversed until the target size g.sub.i is maximum to end the loop and output the maximum size and the corresponding cutting solution. The cutting solution is then applied to the actual cutting process.

(46) This application also provides a cutting stock system, which includes a memory, a processor, and a computer program stored on the memory. The computer program is configured to be executed by the processor. The processor is configured to execute the computer program to implement the cutting stock method.

(47) This application further provides a computer-readable storage medium. The computer program is stored on the computer-readable storage medium. The computer program is configured to be executed by a processor to implement the aforementioned cutting stock method.

(48) Other components and operations of the cutting stock method and system for the defective rectangular sheets provided herein are known to one of ordinary skill in the art and will not be described in detail here.

(49) The modules of the above-mentioned cutting stock system can be implemented as a whole or in part by means of software, hardware and combinations thereof. The modules may be embedded in hardware or in a processor independent of the electronic device, or stored in software in the memory of the electronic device so that the processor can call up and perform the operations corresponding to those modules.

(50) One of ordinary skill in the art can understand that the computer program can instruct the relevant hardware to implement all or part of the operations in the method of the above embodiments. The computer program may be stored in a non-volatile computer readable storage medium and may include aforementioned operations when executed. In addition, any references to memory, storage, databases or other media used herein may include non-volatile and/or volatile memory. Non-volatile memory may include read-only memory (ROM), programmable ROM (PROM), electrically programmable ROM (EPROM), electrically erasable programmable ROM (EEPROM), or flash memory. Volatile memory may include random access memory (RAM) or external cache memory. By way of illustration rather than limitation, RAM is available in various forms, such as static RAM (SRAM), dynamic RAM (DRAM), synchronous DRAM (SDRAM), double data rate SDRAM (DDRSDRAM), enhanced SDRAM (ESDRAM), synchronous link DRAM (SLDRAM), memory bus (Rambus) direct RAM (RDRAM), direct memory bus dynamic RAM (DRDRAM), and memory bus dynamic RAM (RDRAM).

(51) It will be clear to those skilled in the art that, for convenient and brief description, the above-mentioned division of each functional unit and module is given as an example. In actual application, the above-mentioned functions can be assigned to be completed by different functional units and modules as needed, that is, the internal structure of the device is divided into different functional units or modules to complete all or part of the above-described functions.

(52) The above description of embodiments is merely intended to illustrate the technical routes and features of the present disclosure to enable those skilled in the art to understand and implement the technical solutions of the present disclosure. Nonetheless, the present disclosure is not limited to the embodiments described above. All variations or modifications made without departing from the spirit of the disclosure shall fall within the scope of the present disclosure defined by the appended claims.