# US 2008/0313635 A1 · Job allocation method for document production

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2008/0313635 A1
- Document ID: US20080313635A1
- Status: Published application
- Kind: A1
- Application number: 11/763,079
- Filed: 2007-06-14
- Published: 2008-12-18
- Earliest claimed: 2007-06-14
- Assignees: Xerox Corporation
- Inventors: Sudhendu Rai
- Web page: https://patentgrep.com/patent/US20080313635A1

## CPC

- G06F 3/1285: {Remote printer device, e.g. being remote from client or server}
- G06F 3/1204: {resulting in reduced user or operator actions, e.g. presetting, automatic actions, using hardware token storing data}
- G06F 3/1214: {at the submitting node}
- G06F 3/1226: {Discovery of devices having required properties}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

Methods and systems of processing print jobs are disclosed. A feasible route for processing each of a plurality of jobs is determined- For each feasible route, the time to process the job via the feasible route is determined. Each job is assigned to a first feasible route. A first objective function value is determined using a time to process each job assigned to each autonomous cell. A job is selected. A second feasible route is selected for the selected job. A second objective function value is determined by substituting the second feasible route for the first feasible route for the selected job. If the first value plus a threshold exceeds the second value, the second value replaces the first value, and the second feasible route replaces the first feasible route. Selection and substitution are repeated for each job. The jobs are then processed.

## Claims

### Claim 1

A computer-implemented method of processing a plurality of print jobs in a document production environment, the method comprising:
for each of a plurality of print jobs:
determining, by a print job workflow management system, a number of feasible routes for processing the print job, wherein each feasible route comprises at least one resource in at least one of a plurality of autonomous cells, wherein each autonomous cell comprises one or more resources,
for each feasible route, determining a job processing time comprising an amount of time required to process the print job via the feasible route, and
assigning by the print job workflow management system, the print job to a first feasible route;
determining, by the print job workflow management system, a first value for an objective function based on a total processing time for each autonomous cell to process each print job assigned to the autonomous cell;
selecting a print job based on the number of feasible routes for each print job;
selecting a second feasible route for the selected print job based on the job processing time for each feasible route for the selected print job,
determining, by the print job workflow management system, a second value for the objective function based on the total processing time for each autonomous cell to process each print job assigned to the autonomous cell including the second feasible route:
if the second value is less than a third value:
reassigning, by the print job workflow management system the selected print job to the second feasible route, and
replacing the first value with the second value;
repeating at least said selecting a print job, said selecting a second feasible route, and said determining a second value a plurality of times for each of the plurality of print jobs; and
processing the plurality of print jobs based on the assigned feasible routes.

### Claim 2 (depends on 1)

The method of claim 1 wherein determining a first value for the objective function comprises:
for each autonomous cell, determining a total processing time for the autonomous cell to process each print job assigned to the autonomous cell; and
determining a maximum total processing time based on the total processing time for each autonomous cell.

### Claim 3 (depends on 1)

The method of claim 1 wherein selecting a print job comprises:
for each print job, determining a number of feasible routes for the print job;
summing the number of feasible routes for each print job to produce a total number of feasible routes;
for each print job, assigning a selection probability equal to the number of feasible routes for the print job divided by the total number of feasible routes; and
selecting a print job using the selection probabilities for the print jobs.

### Claim 4 (depends on 1)

The method of claim 1 wherein selecting a second feasible route comprises:
for each feasible route for the selected print job determining an inverted processing time for the feasible route equal to one divided by the processing time for the feasible route;
summing the inverted processing times for each feasible route to produce a total inverted processing time;
for each feasible route, assigning a selection probability equal to the inverted processing time for the feasible route divided by the total inverted processing time; and
selecting a second feasible route using the selection probabilities for the feasible routes.

### Claim 5 (depends on 1)

The method of claim 1 wherein determining a second value for the objective function comprises:
for each autonomous cell, determining a total processing time for the autonomous cell to process each print job assigned to the autonomous cell; and
determining a maximum total processing time based on the total processing time for each autonomous cell.

### Claim 6 (depends on 1)

The method of claim 1, further comprising setting the third value to a sum of the first value and a threshold.

### Claim 7 (depends on 6)

The method of claim 6, further comprising reducing the threshold.

### Claim 8

A system for processing a plurality of print jobs in a document production environment, the system comprising;
a plurality of autonomous cells, wherein each autonomous cell is configured to process print jobs, wherein each autonomous cell comprises one or more resources; and
a print job workflow management system configured to:
for each of a plurality of print jobs:
determine a number of feasible routes for processing the print job, wherein each feasible route comprises at least one resource in at least one of the plurality of autonomous cells,
for each feasible route, determine a job processing time comprising an amount of time required to process the print job via the feasible route, and
assign the print job to a first feasible route,
determine a first value for an objective function based on a total processing time for each autonomous cell to process each print job assigned to the autonomous cell,
select a print job based on the number of feasible routes for each print job.
select a second feasible route for the selected print job based on the job processing time for each feasible route for the selected print job,
determine a second value for the objective unction based on the total processing time for each autonomous cell to process each print job assigned to the autonomous cell including the second feasible route, and
if the second value is less than a third value:
reassign the selected print job to the second feasible route, and
replace the first value with the second value,
wherein the print job workflow management system is configured to perform at least said selecting a print job, said selecting a second feasible route, and said determining a second value a plurality of times for each of the plurality of print jobs.

### Claim 9 (depends on 8)

The system of claim 8 wherein the print job workflow management system is configured to determine a first value for the objective function by:
for each autonomous cell, determining a total processing time for the autonomous cell to process each print job assigned to the autonomous cell; and
determining a maximum total processing time based on the total processing time for each autonomous cell.

### Claim 10 (depends on 8)

The system of claim 8 wherein the print job workflow management system is configured to select a print job by:
for each print job, determining a number of feasible routes for the print job;
summing the number of feasible routes for each print job to produce a total number of feasible routes;
for each print job, assigning a selection probability equal to the number of feasible routes for the print job divided by the total number of feasible routes, and
selecting a print job using the selection probabilities for the print jobs.

### Claim 11 (depends on 8)

The system of claim 8 wherein the print job workflow management system is configured to select a second feasible route by:
for each feasible route for the selected print job, determining an inverted processing time for the feasible route equal to one divided by the processing time for the feasible route;
summing the inverted processing times for each feasible route to produce a total inverted processing time;
for each feasible route, assigning a selection probability equal to the inverted processing time for the feasible route divided by the total inverted processing time; and
selecting a second feasible route using the selection probabilities for the feasible routes.

### Claim 12

The system of claim X wherein the print job workflow management system is configured to determine a second value for the objective function by:
for each autonomous cell, determining a total processing time for the autonomous cell to process each print job assigned to the autonomous cell; and
determining a maximum total processing time based on the total processing time for each autonomous cell.

### Claim 13 (depends on 8)

The system of claim 8 wherein the print job workflow management system is further configured to set the third value to a sum of the first value and a threshold.

### Claim 14 (depends on 1)

The system of claim 1I wherein the print job workflow management system is further configured to reduce the threshold.

### Claim 15

A computer-implemented method of processing a plurality of print jobs, the method comprising:
for each of the plurality of print jobs, assigning a first feasible route selected from a plurality of feasible routes, wherein each of the plurality of feasible routes comprises at least one resource in at least one of a plurality of autonomous cells, wherein each of the plurality of autonomous cells comprises one or more resources,
determining a first value for an objective function based on a total processing time for each of the plurality of autonomous cells to process each print job assigned to the autonomous cell;
selecting one of the plurality of print jobs based on the number of feasible routes for each of the plurality of print jobs;
selecting a second feasible route for the selected print job based on the job processing time for each feasible route for the selected print job;
determining a second value for the objective function based on the total processing time for each autonomous cell to process each print job assigned to the autonomous cell including the second feasible route,
if the second value is less than a third value:
reassigning the selected print job to the second feasible route, and
replacing the first value with the second value; and
processing the plurality of print jobs based on the assigned feasible routes.

### Claim 16 (depends on 15)

The method of claim 15 wherein selecting one of the plurality of print jobs comprises:
for each print job, determining a number of feasible routes for the print job.
summing the number of feasible routes for each print job to determine a total number of feasible routes;
for each print job, assigning a selection probability equal to the number of feasible routes for the print job divided by the total number of feasible routes; and
selecting a print job using the selection probabilities for the print jobs.

### Claim 17 (depends on 15)

The method of claim 15 wherein selecting a second feasible route comprises:
for each feasible route for the selected print job, determining an inverted processing time for the feasible route equal to one divided by the processing time for the feasible route,
summing the inverted processing times for each feasible route to produce a total inverted processing time:
for each feasible route, assigning a selection probability equal to the inverted processing time for the feasible route divided by the total inverted processing time; and
selecting a second feasible route using the selection probabilities for the feasible routes

### Claim 18 (depends on 15)

The method of claim 15, further comprising setting the third value to a sum of the first value and a threshold.

### Claim 19 (depends on 18)

The method of claim 18, further comprising reducing the threshold.
