Planning method and system

• US 5,651,098 A
• Filed: 10/07/1994
• Issued: 07/22/1997
• Est. Priority Date: 10/07/1993
• Status: Expired due to Term

• Current Assignee: Hitachi Engineering Co.,Ltd (Hitachi, Ltd.)
• Original Assignee: Hitachi Engineering Co.,Ltd (Hitachi, Ltd.)
• Inventors: Nakamura, Kenichi, Hamaguchi, Yukio, Mizutani, Mayumi, Yoshida, Hideo, Inoue, Haruki, Onizawa, Hitoshi, Shiozawa, Masami
• Primary Examiner(s): Hafiz, Tariq R.
• Application Number:
  US08/319,789
• Time in Patent Office: 1,019 Days
• Field of Search: 395/10-13, 395/50-51, 395/60-61, 395/76, 395/904, 395/922, 364/491, 364/468.28, 364/468.2
• US Class Current: 706/13
• CPC Class Codes: G06Q 10/04 Forecasting or optimisation specially adapted for administrative or management purposes, e.g. linear programming or "cutting stock problem" market predictions or forecasting for commercial activities G06Q30/0202

Abstract

A system for making an optimum plan for a given problem at high speed. The system sets a planning problem, etc., prepares an objective function and finalizes a plan for minimizing or maximizing the objective function value, and then stores necessary variables. The system prepares as many parent plans of a first generation as a given number (population), calculates objective function values, sorts plans in descending or ascending order of the objective function values of the plans, when selection numbers are assigned to plans in order of a ratio of the objective function value of each plan to the total of the objective function values of the plans, selects parent plans by using numbers indicated by as many constants as the population determined for each generation as the selection numbers, and replaces two elements, arranged at order positions specified by random numbers, with each other for each of the selected parent plans, to prepare child plans.

Claims

1. A planning system comprising:

input means for accepting at least a given planning problem and values of variables required to solve the planning problem;

optimization means for preparing an objective function representing an item to be minimized or maximized in the planning problem and making a final plan for minimizing or maximizing a value of the prepared objective function; and

means for outputting the final plan;

wherein said optimization means comprises;

means for storing at least a plurality of solution plans to the planning problem,

a plurality of cell processors each for preparing a new plan from a first plan by predetermined manipulation, calculating a difference between objective function values of the first plan and the new plan, comparing the calculated difference with a value of a plan determination variable set for each processing at a predetermined processing count, and if the calculated difference is greater than or equal to the plan determination variable value, adopting the first plan before the manipulation as an optimum plan candidate or if the difference is less than the plan determination variable value, adopting the new plan as an optimum plan candidate,

a cell processor parallel control unit for assigning optimum plan candidates to said cell processors as plans to which the manipulation is applied in response to a percentage of the objective function value of each plan candidate to the total of the objective function values of the plan candidates, and

start control means for staring said cell processors and said cell processor parallel control unit as many times as the predetermined processing count.

2. A planning system comprising:

input means for accepting at least a given planning problem and values of variables required to solve the planning problem;

optimization means for preparing an objective function representing an item to be minimized or maximized in the planning problem and making a final plan for minimizing or maximizing a value of the prepared objective function; and

means for outputting the final plan,

wherein said optimization means comprises;

means for storing at least a plurality of solution plans to the planning problem;

a plurality of cell processors each for preparing a new plan from a first plan by predetermined manipulation, and when the new plan satisfies a predetermined evaluation criterion, adopting the new plan as an optimum plan candidate or when the new plan does not satisfy the predetermined evaluation criterion, adopting the first plan before the manipulation as an optimum plan candidate, and finding an objective function value of the optimum plan candidate,

a cell processor parallel control unit for assigning optimum plan candidates to said cell processors as plans to which the manipulation is applied in response to a percentage of the objective function value of each plan candidate to the total of the objective function values of the plan candidates, and

start control means for starting said cell processors and said cell processor parallel control unit as many times as the predetermined processing count.

3. A planning system comprising:

an optimization processor for preparing an objective function representing an item to be minimized or maximized for a planning problem and performing parallel processing for finding an optimum plan for providing an optimum value of the objective function; and

means for storing at least a predetermined optimum determination value which decreases with a lapse of processing time and is referenced when the optimum plan is found and a predetermined autonomous selection generation value which increases with a lapse of processing time and is referenced when said optimization processor performs parallel processing;

wherein said optimization processor comprises a plurality of processors for performing parallel processing,

each of said plurality of processors comprising;

plan change means for preparing a child plan by predetermined mutation manipulation from a given parent plan,

plan evaluation means for comparing an objective function value of the parent plan with that of the child plan, and

autonomous selection means for updating the parent plan;

wherein said plan evaluation means calculates an objective function value difference between the parent and child plans and if the objective function value difference is less than the predetermined optimum determination value, said plan evaluation means replaces the parent plan with the child plan, and if the child pan is an optimum plan among plans provided by the parallel processing, registering the child plan in said storage means as the best plan, and if the objective function value difference is greater than the optimum determination value, said plan evaluation means holds the parent plan, and

wherein further said autonomous selection means selects the best plan as a new parent plan for the corresponding processor when the time during which no parent plan change has occurred in the corresponding processor is long in comparison with the autonomous selection generation value, which is the predetermined time.

4. A planning system comprising:

an optimization processor for preparing an objective function representing an item to be minimized or maximized for a planning problem and performing parallel processing for finding an optimum plan for providing an optimum value of the objective function; and

means for storing at least a predetermined optimum determination value which decreases with a lapse of processing time and is references when the optimum plan is found and a predetermined autonomous selection generation value which increases with a lapse of processing time and is referenced when said optimization processor performs parallel processing;

wherein said optimization processor comprises a plurality of processors for performing parallel processing,

each of said plurality of processors comprising;

plan change means for preparing a child plan by predetermined mutation manipulation from a given parent plan,

plan evaluation means for comparing an objective function value of the parent plan with that of the child plan, and

autonomous selection means for updating the parent plan;

wherein said plan evaluation means calculates an objective function value difference between the parent an child plans and if the objective function value difference is less than the predetermined optimum determination value, said plan evaluation means replaces the parent plan with the child plan, and

wherein further said autonomous selection means selects an optimum plan among plans updated by said autonomous selection means contained in other processors previously related to the corresponding processor as a new parent plan for the corresponding processor when the time during which no parent plan change has occurred in the corresponding processor is long in comparison with the autonomous selection generation value, which is the predetermined time.