Production plan optimization apparatus, method, non-transitory computer readable medium storing program, and control apparatus

Patent metadata

Field	Value
Publication number	US-12468271-B2
Application number	US-202018017242-A
Country	US
Kind code	B2
Filing date	Jul 31, 2020
Priority date	Jul 31, 2020
Publication date	Nov 11, 2025
Grant date	Nov 11, 2025

Abstract

A production plan optimization apparatus includes a traveling salesman problem formulation unit for formulating a problem regarding determining a sequence in which a plurality of workpieces are processed as a traveling salesman problem that satisfies a delivery date constraint based on a delivery date specified for at least one of the plurality of workpieces and a sequence constraint specified for at least one of combinations of the plurality of workpieces and also minimizes a sum of changeover times associated with switching of the workpieces and a processing sequence determination unit for calculating a solution to the traveling salesman problem, by using an annealing processing unit for searching for an optimal solution to a combinatorial optimization problem by simulated annealing or quantum annealing, and determining the sequence in which the plurality of workpieces are processed based on a result of the calculation.

First claim

What is claimed is:

1 . A control apparatus comprising:
at least one memory storing instructions; and at least one processor configured to execute the instructions to:
formulate a problem regarding determining a sequence in which a plurality of workpieces are processed as a traveling salesman problem that satisfies a delivery date constraint based on a delivery date specified for at least one of the plurality of workpieces and a sequence constraint specified for at least one of combinations of the plurality of workpieces and also minimizes a sum of changeover times associated with switching of the workpieces;
calculate a solution to the traveling salesman problem, by using an annealing processing machine for searching for an optimal solution to a combinatorial optimization problem by simulated annealing or quantum annealing, and determine the sequence in which the plurality of workpieces are processed based on a result of the calculation; and
controlling a processing apparatus to physically process the plurality of workpieces according to the sequence determined based on the result of the calculation.

2 . The apparatus according to claim 1 , wherein
the plurality of workpieces are classified into a plurality of groups so that a combination of the workpieces having a short changeover time belongs to the same group, and the at least one processor is further configured to execute the instructions to: determine a sequence in which the plurality of groups are processed as a group sequence, and formulate the problem as the traveling salesman problem that satisfies the delivery date constraint and the sequence constraint including a constraint based on the group sequence and also minimizes the sum.

3 . The apparatus according to claim 1 , wherein
the changeover time between the workpieces belonging to different groups includes a group preparation time required for preparing production of the group to which the workpiece to be switched belongs, and the at least one processor is further configured to execute the instructions to:
formulate a jobshop problem that minimizes a sum of waiting times in a processing apparatus when processing of the group for which the preparation for the production is made is started in the processing apparatus after the preparation for the production has been made outside the processing apparatus, and
use the annealing processing machine to calculate a solution to the jobshop problem and determine the group sequence based on a result of the calculation.

4 . The apparatus according to claim 3 , wherein
the plurality of workpieces are selected from among a plurality of ordered workpieces, and each of the plurality of ordered workpieces is classified into the plurality of groups, and the at least one processor is further configured to execute the instructions to:
generate one or a plurality of blocks combining the ordered workpieces classified into the group for each of the plurality of groups;
calculate, for each of the plurality of blocks, a block processing time required for processing the ordered workpieces included in the block and set a larger one of the block processing time and a predetermined preparation time as the block processing time of the block;
formulate a knapsack problem in which a plurality of processing blocks to be processed are selected from the plurality of blocks so that a sum of the block processing times becomes large within a range of a predetermined operation time or less; and
calculate a solution to the knapsack problem by using the annealing processing machine, select the plurality of processing blocks based on a result of the calculation, and select the plurality of ordered workpieces according to a result of the selection.

5 . The apparatus according to claim 4 , wherein
the delivery date is set for each of the plurality of ordered workpieces, and the at least one processor is further configured to execute the instructions to: formulate the knapsack problem so that the ordered workpiece whose delivery date is a predetermined date is included in one of the plurality of processing blocks.

6 . The apparatus according to claim 4 , wherein
the at least one processor is further configured to execute the instructions to: formulate the knapsack problem so that the number of groups to which the plurality of ordered workpieces belong becomes small.

7 . The production plan optimization apparatus according to claim 4 , wherein
the at least one processor is further configured to execute the instructions to: formulate the knapsack problem so that a sum of preparation waiting times based on a difference between the predetermined preparation time and the block processing time becomes small.

8 . The apparatus according to claim 4 , wherein
the at least one processor is further configured to execute the instructions to: formulate the knapsack problem so that blocks with long changeover times are less likely to be selected.

9 . The control apparatus according to claim 1 , further comprising the annealing processing machine.

10 . A control method for causing a computer to execute:
formulating a problem regarding determining a sequence in which a plurality of workpieces are processed as a traveling salesman problem that satisfies a delivery date constraint based on a delivery date specified for at least one of the plurality of workpieces and a sequence constraint specified for at least one of combinations of the plurality of workpieces and also minimizes a sum of changeover times associated with switching of the workpieces; and calculating a solution to the traveling salesman problem, by using an annealing processing machine for searching for an optimal solution to a combinatorial optimization problem by simulated annealing or quantum annealing, and determining the sequence in which the plurality of workpieces are processed based on a result of the calculation; and controlling a processing apparatus to physically process the plurality of workpieces according to the sequence determined based on the result of the calculation.

11 . A non-transitory computer readable medium storing a control program for causing a computer to execute the control method according to claim 10 .

Assignees

• Nec Corp
• Nec Platforms Ltd

Inventors

• Chishima Hiroshi
• Kaida Masayo

Classifications

• G06Q10/047 Primary

  Optimisation of routes or paths, e.g. travelling salesman problem · CPC title

• G05B2219/32254

  Work sequence, alternative sequence · CPC title

• G05B2219/32064

  Production change over · CPC title

• G05B19/41865

  characterised by job scheduling, process planning, material flow · CPC title

• Y02P90/30

  Computing systems specially adapted for manufacturing · CPC title