Optimizing manufacturing schedule with time-dependent energy cost

Patent metadata

Field	Value
Publication number	US-10048669-B2
Application number	US-201615014473-A
Country	US
Kind code	B2
Filing date	Feb 3, 2016
Priority date	Feb 3, 2016
Publication date	Aug 14, 2018
Grant date	Aug 14, 2018

Abstract

A method of manufacturing at least a first product and a second product with at least a first machine and a second machine at minimum cost in an environment in which a cost of energy used by the first machine and the second machine varies as a function of time may include generating multiple chromosomes, determining fitness scores of each of the chromosomes, randomly generating, with probabilities based on the fitness scores, new chromosomes, determining fitness scores of the new chromosomes, selecting one of the new chromosomes with an optimal fitness score, and manufacturing at least the first product and the second product with at least the first machine and the second machine according to a schedule based on the selected new chromosome.

First claim

What is claimed is:

1. A method of manufacturing at least a first product and a second product with at least a first machine and a second machine at minimum cost in an environment in which a cost of energy used by the first machine and the second machine varies as a function of time, the method comprising:
generating multiple chromosomes, each chromosome including:
a job sequence matrix describing an order of performing tasks to manufacture the first product and the second product using the first machine and the second machine; and
an idle time matrix describing idle times before performing the tasks in the order described by the job sequence matrix;

determining fitness scores of each of the chromosomes with the job sequence matrices and the idle time matrices, the fitness scores being based on energy costs at the times that the first and second machines perform the tasks;
randomly generating, with probabilities based on the fitness scores, new chromosomes;
determining fitness scores of the new chromosomes;
selecting one of the new chromosomes with an optimal fitness score; and
manufacturing at least the first product and the second product with at least the first machine and the second machine according to a schedule based on the selected new chromosome, the schedule determining when the first and second machines perform which tasks and when the first and second machines are idle.

2. The method of claim 1 , wherein:
the generating multiple chromosomes includes generating multiple chromosomes based on at least a first job associated with the first product and a second job associated with the second product,
the first job includes at least a first task, and a second task to be performed after completing the first task,
the second job includes at least a third task, and a fourth task to be performed after completing the third task, and
each of the first machine and the second machine can perform only one task during a given time unit.

3. The method of claim 2 , wherein the first task requires one time unit, the second task requires one time unit, the third task requires two time units, and the fourth task requires two time units.

4. The method of claim 1 , wherein:
the first product is associated with a first deadline and a first penalty cost per unit time for manufacturing the first product after the first deadline;
the second product is associated with a second deadline and a second penalty cost per unit time for manufacturing the second product after the second deadline; and
the fitness scores for each of the chromosomes are based on a sum of energy costs at the times that the first and second machines perform the tasks and the associated penalty costs for manufacturing the first and second products after the associated deadlines.

5. The method of claim 1 , wherein the method includes determining the fitness scores of each of the chromosomes and randomly generating new chromosomes a predetermined number of times.

6. The method of claim 1 , wherein the method includes determining the fitness scores of each of the chromosomes, randomly generating new chromosomes, and determining fitness scores of the new chromosomes until an improvement of an optimal fitness score of the new chromosomes is below a predetermined threshold.

7. The method of claim 1 , wherein the method includes randomly modifying the idle time matrices of each of the chromosomes before determining the fitness scores of each of the chromosomes.

8. The method of claim 1 , wherein the method includes optimizing the idle time matrices of each of the chromosomes for the job sequence matrices included in the respective chromosome before determining the fitness scores of each of the chromosomes.

9. The method of claim 1 , wherein:
the multiple chromosomes includes a first chromosome with a first job sequence matrix and a second chromosome with a second job sequence matrix, the second job sequence matrix describing a different order of performing a same set of tasks than the first job sequence matrix; and
the method further includes, before determining the fitness scores of each of the chromosomes, exchanging a first sequence of tasks from the first job sequence matrix with a second sequence of tasks from the second job sequence matrix, the first sequence of tasks and the second sequence of tasks including a same subset of the set of tasks that are performed on a same machine, with the tasks in the first job sequence matrix and the second job sequence matrix being performed in a different order.

10. The method of claim 1 , wherein the method further includes, before determining the fitness scores of each of the chromosomes, swapping, within at least one of the job sequence matrices, an order of performing at least a first task for manufacturing the first product on the first machine with a second task for manufacturing the second product on the first machine.

11. The method of claim 1 , wherein:
the multiple chromosomes includes a first chromosome with a first job sequence matrix and a second chromosome with a second job sequence matrix, the second job sequence matrix describing a different order of performing a same set of tasks than the first job sequence matrix;
the method further includes, before determining the fitness scores of each of the chromosomes, exchanging a first sequence of tasks from the first job sequence matrix with a second sequence of tasks from the second job sequence matrix, the first sequence of tasks and the second sequence of tasks including a same set of tasks that are performed on a same machine, with the tasks in the first job sequence matrix and the second job sequence matrix being performed in a different order; and
the method further includes, before determining the fitness scores of each of the chromosomes, swapping, within at least one of the job sequence matrices, an order of performing at least a first task for manufacturing the first product on the first machine with a second task for manufacturing the second product on the first machine.

12. The method of claim 1 , wherein each machine can perform only one task at a time.

13. The method of claim 1 , wherein manufacturing at least the first product and the second product with at least the first machine and the second machine according to the schedule based on the selected new chromosome includes presenting the schedule to a user in a graphical format.

14. A non-transitory computer-readable storage medium comprising instructions stored thereon for optimizing a schedule to manufacture at least a first product and a second product with at least a first machine and a second machine at minimum cost in an environment in which a cost of energy used by the first machine and the second machine varies as a function of time, the instructions, when executed by at least one processor, being configured to cause a computing system to at least:
generate multiple chromosomes, each chromosome including:
a job sequence matrix describing an order of performing tasks to manufacture the first product and the second product using the first machine and the second machine; and
an idle time matrix describing idle times before performing the tasks in the order described by the job sequence matrix;

determine fitness scores of each of the chromosomes with the job sequence matrices and the idle time matrices, the fitness scores being based on energy costs at the times that the first and second machines perform the tasks;
randomly generate, with probabilities based on the fitness scores, new chromosomes based on the chromosomes with the idle time matrices;
determine fitness scores of the new chromoso

Assignees

• Sap Se

Inventors

• Zhou Wenjun
• Li Wen-Syan

Classifications

• G06N7/01

  Probabilistic graphical models, e.g. probabilistic networks · CPC title

• Y02P90/30

  Computing systems specially adapted for manufacturing · CPC title

• G06N3/126

  Evolutionary algorithms, e.g. genetic algorithms or genetic programming · CPC title

• G06Q50/04

  Manufacturing · CPC title

• G05B19/0426 Primary

  Programming the control sequence · CPC title