SYSTEM AND METHODS FOR ADAPTIVE LOT SIZING IN CELLULAR MANUFACTURING

• US 20120099139A1
• Filed: 10/26/2010
• Published: 04/26/2012
• Est. Priority Date: 10/26/2010
• Status: Active Grant

• Current Assignee: Palo Alto Research Center, Inc. (Xerox Holdings Corp.), Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Palo Alto Research Center, Inc. (Xerox Holdings Corp.), Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Zhou, Rong, Rai, Sudhendu, Do, Minh Binh
• Granted Patent: US 8,769,542 B2
• Time in Patent Office: Days
• US Class Current: 358/1.15
• CPC Class Codes: G06F 2206/1508 Load balancing
• CPC Class Codes: G06F 2206/1514 Sub-job
• CPC Class Codes: G06F 3/1211 Improving printing performance
• CPC Class Codes: G06F 3/1241 Dividing a job according to job requirements, e.g. black/white and colour pages, covers and body of books, tabs
• CPC Class Codes: G06F 3/126 Job scheduling, e.g. queuing, determine appropriate device
• CPC Class Codes: G06F 3/1285 Remote printer device, e.g. being remote from client or server

Abstract

The present application presents a new and improved system and method of enhanced Lean Document Production (LDP), which employs cellular manufacturing concepts. The LDP process incorporates an auto-splitting algorithm and/or an earliest completion route algorithm to generate an operation schedule.

Claims

1. A method of balancing workload across multiple cells in a cellular manufacturing environment, the method comprising:

compiling a listing of a plurality of jobs and cells using a computer operable processor, wherein the plurality of jobs are to be produced by at least some of the plurality of cells, and each of the cells include at least one production device; and

auto-splitting the jobs into smaller sized lots using a split-then-merge operation to adapt the lots to cell workloads while returning lot sizes that are no more fine grained than necessary.

2. The method according to claim 1, wherein the auto-splitting performs without a fixed formula to determine an optimal lot size.

3. The method according to claim 1, wherein the auto-splitting includes:

dividing the job into smaller sized lots;

scheduling the smaller sized lots one at a time;

determining, once all the smaller sized lots are scheduled, which of the smaller sized lots can be combined with others to form larger lots; and

merging together the smaller sized lots determined to be combinable.

4. The method according to claim 3, wherein a setup time for a newly scheduled lot is subtracted from a set-up time when a previous lot and the newly scheduled lot are consecutive.

5. The method according to claim 4, wherein two lots are consecutive if and only if they are scheduled back to back and belong to the same job.

6. The method according to claim 5, wherein when two consecutive lots are merged:

a size of the merged lot is the sum of the sizes of the two lots being merged,

a start time of the merged lot is the start time of the lot that is scheduled to begin earlier, and

an end time of the merged lot is the end time of the lot that is scheduled to end later.

7. The method according to claim 3, wherein a schedule is maximally merged, if and only if no consecutive lots can be found that are scheduled on machine i for all i∈

{1,2, . . . , m}.

8. The method according to claim 1, wherein the auto-splitting algorithm automatically adapts the lot size to the changing workload of cells.

9. A method of balancing workload across multiple cells in a manufacturing environment, the method comprising:

compiling a listing of a plurality of jobs and cells using a computer operable processor, wherein the plurality of jobs are to be produced by at least some of the plurality of cells, and each of the cells include at least one production device;

enumerating feasible routes in the manufacturing environment with a preference to routes having fewer inter-cell hops;

assigning the jobs to the cells using an earliest-completion-route algorithm, wherein a specific job is assigned to a specific cell that provides an earliest completion time for the specific job; and

generating a job schedule for job production based on the results of the earliest-completion-route algorithm.

10. The method according to claim 9, further including a penalty or a reward for routes that connect distant and/or neighboring cells in the same workflow.

11. The method according to claim 10, wherein improved scheduling performance for the cellular manufacturing is achieved with or without lot sizing.

12. The method according to claim 11, further obtaining a job schedule by performing auto-splitting operations, and earliest completion-route operations in parallel.

13. The method according to claim 12, wherein the auto-splitting method uses a split-then-merge operation to adapt the lots to cell workloads while returning lot sizes that are no more fine-grained than necessary.

14. A method of balancing workload across multiple cells in a cellular manufacturing environment, the method comprising:

compiling a listing of a plurality of jobs and cells using a computer operable processor, wherein the plurality of jobs are to be produced by at least some of the plurality of cells, and each of the cells include at least one production device;

assigning the jobs to the cells using an earliest-completion-route scheduling strategy; and

generating a job schedule for job production based on the results of the earliest-completion-rout scheduling strategy.

15. The method according to claim 14, wherein the earliest-completion-route scheduling strategy includes:

enumerating all routes that have a minimum number of inter-cell hops;

for each route in this set, finding the best schedule by only using those cells identified by the route; and

selecting the route and the corresponding schedule that finishes the job earliest.

16. The method according to claim 14, wherein improved scheduling performance for cellular manufacturing is achieved with or without lot sizing.

17. The method according to 16, further including obtaining a job schedule by performing auto-splitting operations and earliest completion-route operations in parallel.

18. The method according to claim 17, wherein the auto-splitting method uses a split-then-merge operation to adapt the lots to cell workloads while returning lot sizes that are no more fine-grained than necessary.