System for adaptive lot sizing in cellular manufacturing for balancing workloads across multiple cells using split-then-merge operations and earliest completion route algorithm

• US 8,769,542 B2
• Filed: 10/26/2010
• Issued: 07/01/2014
• Est. Priority Date: 10/26/2010
• Status: Expired due to Fees

• 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
• Primary Examiner(s): An, Meng
• Assistant Examiner(s): GHAFFARI, ABU Z
• Application Number:
  US12/911,766
• Publication Number:
  US 20120099139A1
• Time in Patent Office: 1,344 Days
• Field of Search: 718/104, 718/105, 358/1.13, 358/1.15, 358/1.16
• US Class Current: 718/104
• 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 a plurality of cells, 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,

wherein the auto-splitting includes;

dividing the jobs into smaller sized lots;

scheduling the smaller sized lots to various ones of the cells one lot at a time, wherein the scheduling includes assigning the smaller sized lots of the jobs to the cells using an earliest-completion-route algorithm, which includes enumerating a set of feasible routes for each specific job of the plurality of jobs that has a minimum number of inter-cell hops, finding the best schedule by only using those cells identified by the corresponding route and selecting the route and corresponding schedule that finishes the specific job taking into account at least one of production throughput and wait times;

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

merging together the smaller sized lots determined to be combinable as consecutive lots of the same job,

wherein this method is performed by use of at least an electronic processor.

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

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

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

5. The method according to claim 4, wherein when the 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.

6. The method according to claim 1, wherein a schedule is maximally merged when the schedule contains as few lots as possible to complete the job.

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

8. 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, 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;

performing auto-splitting operations to divide the jobs into smaller sized lots, wherein the auto-splitting operations use split-then-merge operations to adapt the lots to cell workloads while returning lot sizes that are optimized for the cell to which the lots are to be assigned;

enumerating a set of feasible routes for a specific job of the plurality of jobs in the manufacturing environment using an iterative broadening strategy to gradually relax route enumeration criterion, starting with trying out routes for the specific job having fewer inter-cell hops first;

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

generating a job schedule for job production of the specific job based on the results of the auto-splitting operations and the earliest-completion-route algorithm which are performed in parallel,

wherein the method is performed by use of at least an electronic processor.

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

10. 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 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;

performing auto-splitting operations to divide the jobs into smaller sized lots, wherein the auto-splitting operations use split-then-merge operation to adapt the lots to cell workloads while returning lot sizes that are optimized for the cell to which the lots are to be assigned;

assigning the jobs to the cells using an earliest-completion-route scheduling strategy, wherein the earliest-completion-route scheduling strategy includes;

enumerating a set of feasible routes for a specific job of the plurality of jobs that all 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 corresponding route; and

selecting the route and the corresponding schedule that finishes the specific job earliest; and

generating a job schedule for job production based on the results of the auto-splitting operations and the earliest-completion-route scheduling strategy which are performed in parallel, wherein the method is performed by use of at least an electronic processor.