Part arrangement optimizing method

• US 5,600,555 A
• Filed: 05/16/1994
• Issued: 02/04/1997
• Est. Priority Date: 05/20/1993
• Status: Expired due to Fees

• Current Assignee: Mitsubishi Denki Kabushiki Kaisha (Mitsubishi Electric Corporation)
• Original Assignee: Mitsubishi Denki Kabushiki Kaisha (Mitsubishi Electric Corporation)
• Inventors: Takahashi, Masanobu, Kyuma, Kazuo
• Primary Examiner(s): Hayes, Gail O.
• Assistant Examiner(s): Yount, Steven R.
• Application Number:
  US08/242,888
• Time in Patent Office: 995 Days
• Field of Search: 364/488-91, 364/148-51, 364/153, 364/156, 364/194, 364/474.13
• US Class Current: 705/1.1
• CPC Class Codes: G06Q 10/043 Optimisation of two dimensional placement, e.g. cutting of clothes or wood

Abstract

The part arrangement optimizing method of the present invention is a part arranging method capable of obtaining part arrangements having smaller evaluation function values rapidly, and the method improves block arrangements so that evaluation function values such as total route lengths become small as much as possible by replacing plural blocks or block sets to determine the arrangements of parts on the basis of the arrangements of the blocks. Furthermore, as aforementioned improving method of the blocks, such a method as assigns expected positional coordinate to each part and arranges a block to a block arranging position near to the expected positional coordinate while renewing the expected positional coordinate so as to be located at the position where the evaluation function value becomes smaller.

Claims

1. A part arrangement optimizing method comprising the steps of:

(a) representing, in a computer memory, each of a plurality of parts to be arranged as a block or as a block set, such that the blocks are uniform in size;

(b) determining arrangements of said blocks and block sets so that evaluation function values corresponding to the plurality of parts are minimized;

(c) determining the arrangement of said parts on the basis of block arrangements determined in step (b); and

(d) arranging said parts on the basis of the arrangement determined in step (c).

3. The part arrangement optimizing method according to claim 1 or 2, wherein step (b) determines said block arrangement so that said evaluation function values are minimized by replacing plural blocks or block sets.

4. The part arrangement optimizing method according to claim 3, wherein step (c) determines said part arrangement with consideration of the extent of the overlap of each part with said blocks representing said part and said evaluation function values.

5. The part arrangement optimizing method according to claim 1 or 2, wherein step (c) determines said part arrangement with consideration of the extent of the overlap of parts with said blocks representing said parts and said evaluation function values.

2. A part arrangement optimizing method comprising the steps of:

(a) representing, in computer memory, each of a plurality of parts to be arranged as a block or as a block set, such that the ratios of the sizes of which are integers;

(b) determining arrangements of said blocks and block sets so that evaluation function values corresponding to the plurality of parts are minimized;

(c) determining the arrangement of said parts on the basis of block arrangements determined in step (b); and

(d) arranging said parts on the basis of the arrangement determined in step (c).

6. A computer implemented part arrangement optimizing method comprising the steps of:

(a) setting part arranging positions where parts are arranged;

(b) introducing dummy parts having no route with any other parts so that the number of said parts becomes equal to the number of said part arranging positions set in step (a);

(c) assigning expected positional coordinate vectors to each of said parts, each expected positional coordinate vector having the same dimensions as those of coordinates of said part arranging positions;

(d) selecting one part arranging position among said part arranging positions;

(e) selecting, among parts not yet selected, one optimum part having a minimal cost function value in said part arranging position selected in step (d);

(f) determining the arrangement of the optimum part selected in step (e) at the part arranging position selected in step (d);

(g) bringing the expected positional coordinates of said optimum part close to the part arranging position selected in step (d);

(h) renewing the expected positional coordinates of parts other than said optimum part in conformity with a restricting condition;

(i) determining the arrangements of all of said parts by repeating the processes from step (d) to step (h) for part arranging positions not yet selected until all of said part arranging positions have been selected;

(j) finally determining a part arrangement having a minimal evaluation function value as a final part arrangement by executing steps (d) to (I) one or more times; and

(k) arranging said parts on the basis of the part arrangement determined in step (j).

7. A part arrangement optimizing method comprising the steps of:

(a) representing, in a computer memory, each of a plurality of parts to be arranged as a block or as a block set, such that the blocks are uniform in size;

(b) supposing a suppositional route between blocks representing the same part differently from an actual route;

(c) setting block arranging positions where blocks are arranged;

(d) introducing dummy blocks having no routes with any other blocks so that the number of said blocks becomes equal to the number of said block arranging positions set in step (c);

(e) assigning to each of said blocks, expected positional coordinate vectors having the same dimensions as those of coordinates of said block arranging positions;

(f) selecting one block arranging position among said block arranging positions;

(g) selecting, among blocks not yet selected, one optimum block having a minimal cost function value in said block arranging position selected in step (f);

(h) determining the arrangement of the optimum block selected in step (g) at the block arranging position selected in step (f);

(i) bringing the expected positional coordinates of said optimum block close to the block arranging position selected in step (f);

(j) renewing the expected positional coordinates of blocks other than said optimum block in conformity with a restricting condition;

(k) determining the arrangements of all of said blocks by repeating the processes from step gel to step (j) for block arranging positions not yet selected until all of said block arranging positions have been selected;

(l) determining a block arrangement having a minimal evaluation function value as a final block arrangement by executing steps (f) to (k) one or more times;

(m) determining said part arrangement on the basis of said block arrangement determined in step (l); and

(n) arranging said parts on the basis of the part arrangement determined in step (m).

9. The part arrangement optimizing method according to claim 7 or 8, wherein step (m) determines said part arrangement with consideration of the extent of the overlap of parts with said blocks representing said parts and said evaluation function values.

8. A part arrangement optimizing method comprising the steps of:

(a) representing, in a computer memory, each of a plurality of parts to be arranged as a block or as a block set, such that the blocks have sizes the ratios of which are integers;

(b) supposing a suppositional route between blocks representing the same part differently from an actual route;

(c) setting block arranging positions where blocks are arranged;

(d) introducing dummy blocks having no routes with any other blocks so that the number of said blocks becomes equal to the number of said block arranging positions set in step (c);

(e) assigning to each of said blocks, expected positional coordinate vectors having the same dimensions as those of coordinates of said block arranging positions;

(f) selecting one block arranging position among said block arranging positions;

(g) selecting, among blocks not vet selected, one optimum block having a minimal cost function value in said block arranging position selected in step (f);

(h) determining the arrangement of the optimum block selected in step (g) at the block arranging position selected in step (f);

(i) bringing the expected positional coordinates of said optimum block close to the block arranging position selected in step (f);

(j) renewing the expected positional coordinates of blocks other than said optimum block in conformity with a restricting condition;

(k) determining the arrangement of all of said blocks by repeating the processes from step (f) to step (j) for block arranging positions not yet selected until of all of said block arranging positions have been selected;

(l) determining a block arrangement having a minimal evaluation function value as a final block arrangement by executing steps (f) to (k) one or more times;

(m) determining said part arrangement on the basis of said block arrangement determined in step (l); and

(n) arranging said parts on the basis of the part arrangement determined in step (m).