PATENT CLAIM ANALYSIS

Application Number: 15958932
Application Type: Utility
Filing Date: 2018-04
Publication Date: 2018-12
Patent Classification: ["700", "101000"]

Abstract:
A method and a system for scheduling parallel machines based on hybrid shuffled frog leaping algorithm and variable neighborhood search algorithm are provided to solve collaborative production and processing of jobs on a plurality of unrelated batch processing machines. The jobs are distributed to machines based on the normal processing time and deterioration situation of the jobs on different machines and are arranged. An effective multi-machine heuristic rule is designed according to the structural properties of an optimal solution for the single-machine problem, and the improved rule is applied to the improved shuffled frog leaping algorithm to solve this problem. The improvement strategy for the traditional shuffled frog leaping algorithm is to improve the local search procedure of the traditional frog leaping algorithm by introducing the variable neighborhood search algorithm. The convergence rate and optimization capacity of the original algorithm are thus improved.

Claim (Index 2):
The method according to  claim 1 , wherein, in the step  3 , calculating a fitness value of each individual in a population P (L)  specifically comprises:\n step  31 : designating an arrangement order of the jobs according to the position of the individual P i (L) ={P i1 (L) , . . . , P ij (L) , . . . , P in (L) }, denoting the arrangement order of the jobs by \u03c6 = { J P i \ue89e \ue89e 1 ( L ) , \u2026 , J P ij ( L ) , \u2026 , J P in ( L ) } , and setting b=1;\n step  32 : grouping first C jobs in \u03d5 into a batch which is denoted by B b (L)  and deleting the first C jobs from \u03d5, and setting k=1; \n step  33 : trying to put the batch B b (L)  on a machine M k , and processing all current batches on the machine M k  according to a non-descending order of a basic processing time for a batch, wherein the basic processing time for a batch is a maximum processing time for all the jobs in the batch without deterioration; and calculating a completion time for the last batch on the M k  according to p jk A =p jk (\u03b1+\u03b2t) \u03bb , which is denoted by MC bk (L)  the normal processing time for the the job on the machine M k  is denoted by p jk , and the normal processing time is the basic processing time for the job when deterioration does not occur; where p jk A  is the actual processing time for the job J j  on the machine M k , \u03b1, \u03b2 and \u03bb are constants, t is the processing start time for the job J j  on the machine M k ; where j=1, 2 . . . , n, and k=1, 2 . . . , m; \n step  34 : determining whether k is not greater than m, if so, assigning k+1 to k, and going to the step  3 ; if not, arranging B b (L)  onto the machine M k* , where k*=arg min {MC bk (L) |k=1, 2, . . . , m}; \n step  35 : determining whether b is equal to B, if so, outputting a current maximum completion time for a batch on all the machines as the fitness value of the individual P (L) ; if not, going to a step  36 , and B represents the number of batches; and \n step  36 : determining whether the number of the remaining jobs in \u03d5, is not greater than C, if so, assigning b+1 to b, grouping the remaining jobs into the batch B b (L) , and going to the step  33 ; if not, assigning b+1 to b and going to the step  32 .

Metadata:
- Claim Count in Document: 11.0
- Percentile: 91.0
- Lexical Diversity: 2.01351
- Patent Class: 700.0
- Transitional Phrase Type: none
- Component Type: 0
- Foreign Priority: True
- Related Applications: ['15577127', '10603666', '10257913', '14434755', '12851498']

Analysis Scores:
- 35 USC 101 Eligibility (BERT): 0.362775328112378
- 35 USC 102 Novelty (BERT): 0.5028435965247032
- Combined Prediction Score: 0.3767821549536105
- Mean Citation Score: 143.822686
- Max Citation Score: 150.9968
- Similarity Product: 82.7788234884262

Labels:
- Claim Label 101: 1
- Claim Label 102: 1
- Claim Label 103: 1
- Claim Label 112: 0
- Combined Label: 1
- Label 101 Adjusted: 0

Dataset: test