Patent US5706200A successfully refreshed from Google Patents.
US5706200A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Scheduling system and scheduling method for reentrant line processes
Assignee: ILLINOIS UNIVERSITY OF BOARD OF TRUSTEES OF
•
Filing: 1996-08-15
•
Granted: 1998-01-06
•
Expires: 2016-08-15
Abstract
Abstract A multiple-product reentrant line scheduling method includes the steps of storing a time measurement variable for each one of a plurality of incomplete products disposed in a buffer at a workstation, the time measurement variable representing the entry of the incomplete product into the reentrant line, storing a time measurement variable for the buffer representing the time remaining for incomplete products of the same product type disposed in the buffer to be completed, calculating the difference between the stored time measurement variable for each incomplete product and the stored time measurement variable for the buffer to generate a slack variable for each incomplete product, normalizing the slack variable for each incomplete product by comparing the slack variable of each incomplete product with the slack variables for all incomplete products of same product type that have passed through the workstation to generate a selection variable for each incomplete product, comparing the selection variables to select one of the incomplete products for processing at the workstation, and processing the selected incomplete product. An apparatus for carrying out the scheduling method is also provided.
Inventors
- 👤 Panganamala Ramana Kumar
- 👤 Ray M. Richardson
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-05 18:47
CPC Classifications
G; G06; G06Q; G06Q10/00; G06Q10/06; G05; G05B; G05B19/00; G05B19/02; G05B19/418; G05B19/41865; G06Q50/00; G06Q50/04; Y; Y02; Y02P; Y02P90/00; Y02P90/02
Claims Analysis
Total Claims: 12
Claim 1
Independent Claim
282 words
A method of scheduling the processing of a plurality of incomplete products at a workstation in a reentrant line, each one of the plurality of incomplete products disposed in a buffer at the workstation and processable into one of a plurality of product types, the method comprising the steps of: storing a time measurement variable for each one of the plurality of incomplete products representing an entry of the each one of the plurality of incomplete products into the reentrant line; storing a time measurement variable for the buffer representing the time remaining for the incomplete products of the product type disposed in the buffer to be completed; calculating the difference between the stored time measurement variable for each one of the plurality of incomplete products and the stored time measurement variable for the buffer in which the each one of the plurality of incomplete products is disposed to generate a slack variable for each one of the plurality of incomplete products; normalizing the slack variable for each one of the plurality of incomplete products by comparing the slack variable of the each one of the plurality of incomplete products with the slack variables for all incomplete products of the product type of the each one of the plurality of incomplete products that have passed through the workstation to generate a selection variable for the each one of the plurality of incomplete products; comparing the selection variables for the plurality of incomplete products to select one of the plurality of incomplete products for processing at the workstation; and processing the one of the plurality of incomplete products selected in the step of comparing the selection variables for the plurality of incomplete products.
Claim 2
Independent Claim
282 words
A method of scheduling the processing of a plurality of incomplete products at a workstation in a reentrant line, each one of the plurality of incomplete products disposed in a buffer at the workstation and processable into one of a plurality of product types, the method comprising the steps of: storing a time measurement variable for each one of the plurality of incomplete products representing an entry of the each one of the plurality of incomplete products into the reentrant line; storing a time measurement variable for the buffer representing the time remaining for the incomplete products of the product type disposed in the buffer to be completed; calculating the difference between the stored time measurement variable for each one of the plurality of incomplete products and the stored time measurement variable for the buffer in which the each one of the plurality of incomplete products is disposed to generate a slack variable for each one of the plurality of incomplete products; normalizing the slack variable for each one of the plurality of incomplete products by comparing the slack variable of the each one of the plurality of incomplete products with the slack variables for all incomplete products of the product type of the each one of the plurality of incomplete products that have passed through the workstation to generate a selection variable for the each one of the plurality of incomplete products; comparing the selection variables for the plurality of incomplete products to select one of the plurality of incomplete products for processing at the workstation; and processing the one of the plurality of incomplete products selected in the step of comparing the selection variables for the plurality of incomplete products.
Claim 3
Dependent Claim
184 words
The method according to claim 1, the step of normalizing the slack variables further comprising the steps of: storing an estimate of a mean of the slack variables for the incomplete products of the product type that have passed through the buffer at the workstation; storing an estimate of a standard deviation of the slack variables for the incomplete products of the product type that have passed through the buffer at the workstation; calculating the difference between the slack variable of the each one of the plurality of incomplete products processable into one of the plurality of product types and the stored estimate of the mean of the slack variables for the product type; and dividing the result of the step of calculating the difference between the slack variable of the each one of the plurality of incomplete products and the stored estimate of the mean of the slack variables for the product type by the stored estimate of the standard deviation of the slack variables for the product type to generate the selection variable for each one of the plurality of incomplete products.
Claim 4
Dependent Claim
179 words
The method according to claim 1, the step of normalizing the slack variable further comprising the steps of: storing an estimate of a mean of the slack variables for the incomplete products of the product type that have passed through the workstation; storing an estimate of a standard deviation of the slack variables for the incomplete products of the product type that have passed through the workstation; calculating the difference between the slack variable of the each one of the plurality of incomplete products processable into one of the plurality of the product types and the stored estimate of the mean of the slack variable for the product type; and dividing the result of the step of calculating the difference between the slack variable of the each one of the plurality of incomplete products and the stored estimate of the mean of the slack variables for the product type by the stored estimate of the standard deviation of the slack variables for the product type to generate the selection variable for each one of the plurality of incomplete products.
Claim 5
Dependent Claim
69 words
The method according to claim 3, further comprising the steps of: updating the estimate of the mean of the slack variables for the product type after generating the selection variable for each one of the plurality of incomplete products; and updating the estimate of the standard deviation of the slack variables for the product type after generating the selection variable for each one of the plurality of incomplete products.
Claim 6
Dependent Claim
52 words
The method according to claim 1, further comprising the step of updating the time measurement variable for the buffer representing the time remaining for incomplete products of the product type disposed in the buffer to be completed after each one of the plurality of incomplete products of the product type is completed.
Claim 7
Independent Claim
263 words
An apparatus for scheduling the processing of a plurality of incomplete products at a workstation in a reentrant line, each one of the plurality of incomplete products disposed in a buffer at the workstation and processable into one of a plurality of product types, the apparatus comprising: means for storing a time measurement variable for each one of the plurality of incomplete products representing an entry of each one of the plurality of incomplete products into the reentrant line; means for storing a time measurement variable for the buffer representing the time remaining for incomplete products of the product type disposed in the buffer to be completed; means for calculating the difference between the stored time measurement variable for each one of the plurality of incomplete products and the stored time measurement variable for the buffer in which the each one of the plurality of incomplete products is disposed to generate a slack variable for each one of the plurality of incomplete products; means for normalizing the slack variable for each one of the plurality of incomplete products by comparing the slack variable of the each one of the plurality of incomplete products with the slack variables for all incomplete products of the product type of the each one of the plurality of incomplete products that have passed through the workstation to generate a selection variable for the each one of the plurality of incomplete products; and means for comparing the selection variables for the plurality of incomplete products to select one of the plurality of incomplete products for processing at the workstation.
Claim 8
Independent Claim
263 words
An apparatus for scheduling the processing of a plurality of incomplete products at a workstation in a reentrant line, each one of the plurality of incomplete products disposed in a buffer at the workstation and processable into one of a plurality of product types, the apparatus comprising: means for storing a time measurement variable for each one of the plurality of incomplete products representing an entry of each one of the plurality of incomplete products into the reentrant line; means for storing a time measurement variable for the buffer representing the time remaining for incomplete products of the product type disposed in the buffer to be completed; means for calculating the difference between the stored time measurement variable for each one of the plurality of incomplete products and the stored time measurement variable for the buffer in which the each one of the plurality of incomplete products is disposed to generate a slack variable for each one of the plurality of incomplete products; means for normalizing the slack variable for each one of the plurality of incomplete products by comparing the slack variable of the each one of the plurality of incomplete products with the slack variables for all incomplete products of the product type of the each one of the plurality of incomplete products that have passed through the workstation to generate a selection variable for the each one of the plurality of incomplete products; and means for comparing the selection variables for the plurality of incomplete products to select one of the plurality of incomplete products for processing at the workstation.
Claim 9
Dependent Claim
189 words
The apparatus according to claim 6, the means for normalizing the slack variables further comprising: means for storing an estimate of a mean of the slack variables for the incomplete products of the product type that have passed through the buffer at the workstation; means for storing an estimate of a standard deviation of the slack variables for the incomplete products of the product type that have passed through the buffer at the workstation; means for calculating the difference between the slack variable of the each one of the plurality of incomplete products processable into one of the plurality of product types and the stored estimate of the mean of the slack variables for the product type; and means for dividing the result of the step of calculating the difference between the slack variable of the each one of the plurality of incomplete products and the stored estimate of the mean of the slack variables for the product type by the stored estimate of the standard deviation of the slack variables for the product type to generate the selection variable for each one of the plurality of incomplete products.
Claim 10
Dependent Claim
184 words
The apparatus according to claim 6, the means for normalizing the slack variable further comprising: means for storing an estimate of a mean of the slack variables for the incomplete products of the product type that have passed through the workstation; means for storing an estimate of a standard deviation of the slack variables for the incomplete products of the product type that have passed through the workstation; means for calculating the difference between the slack variable of the each one of the plurality of incomplete products processable into one of the plurality of the product types and the stored estimate of the mean of the slack variable for the product type; and means for dividing the result of the step of calculating the difference between the slack variable of the each one of the plurality of incomplete products and the stored estimate of the mean of the slack variables for the product type by the stored estimate of the standard deviation of the slack variables for the product type to generate the selection variable for each one of the plurality of incomplete products.
Claim 11
Dependent Claim
70 words
The apparatus according to claim 8, further comprising: means for updating the estimate of the mean of the slack variables for the product type after generating the selection variable for each one of the plurality of incomplete products; and means for updating the estimate of the standard deviation of the slack variables for the product type after generating the selection variable for each one of the plurality of incomplete products.
Claim 12
Dependent Claim
51 words
The apparatus according to claim 8, further comprising means for updating the time measurement variable for the buffer representing the time remaining for incomplete products of the product type disposed in the buffer to be completed after each one of the plurality of incomplete products of the product type is completed.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2001-01-05 | 2001-07-07 | 2002-01-06 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2005-01-05 | 2005-07-07 | 2006-01-06 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2009-01-05 | 2009-07-07 | 2010-01-06 | $7700.00 | Window Closed / Lapsed |