Print production scheduling

• US 9,367,268 B2
• Filed: 04/30/2012
• Issued: 06/14/2016
• Est. Priority Date: 04/30/2012
• Status: Active Grant

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Dispoto, Gary J, Zeng, Jun, Duan, Qing, Chakrabarty, Krishnendu, Lin, I-Jong
• Primary Examiner(s): Dulaney, Benjamin O
• Application Number:
  US14/364,752
• Publication Number:
  US 20150098110A1
• Time in Patent Office: 1,506 Days
• US Class Current: 1/1
• CPC Class Codes: G06F 3/1211 Improving printing performance
• CPC Class Codes: G06F 3/1217 achieving reduced idle time at the output device or increased asset utilization
• CPC Class Codes: G06F 3/126 Job scheduling, e.g. queuing, determine appropriate device
• CPC Class Codes: G06F 3/1263 based on job priority, e.g. re-arranging the order of jobs, e.g. the printing sequence
• CPC Class Codes: G06F 3/1285 Remote printer device, e.g. being remote from client or server
• CPC Class Codes: G06N 3/126 Evolutionary algorithms, e.g. genetic algorithms or genetic programming
• CPC Class Codes: G06N 5/046 Forward inferencing; Production systems
• CPC Class Codes: G06Q 10/06313 Resource planning in a project environment
• CPC Class Codes: G06Q 10/06316 Sequencing of tasks or work

Abstract

A print production system includes a dispatcher and a task-resource scheduler. The dispatcher sorts print requests for placement among a series of containers to identify relative priorities among all print requests in each container and then merges the containers together to produce a prioritized list of print requests among all containers. Upon release by the dispatcher of a top N print requests from the prioritized list, the scheduler converts the prioritized list into a task-resource schedule for print production.

Claims

1. A print production scheduler comprising:

a server including a non-volatile memory to store, and a processor to execute, machine readable instructions to provide;

a dispatcher module including;

a first sort function to sort a plurality of print requests for placement, among containers, wherein each container is assigned a time interval, and each of the plurality of print requests is placed in one of the containers according to a time-based attribute of the print request and the time interval of the container where the print request is placed, and

within each container, the first sort function is to sort priorities of the print requests within the container; and

a second sort function to sort the print requests across all the containers into a prioritized list of all print requests,

wherein the dispatcher module selects top N print requests from the prioritized list and releases them upon a first periodic trigger signal; and

a task-resource scheduler module to convert the prioritized list into, and to release upon a second periodic trigger signal, a task-resource schedule.

2. The print production scheduler of claim 1, wherein at least one of the first sort function, the second sort function, and the task-resource scheduler perform operations according to an evolutionary-based computation, meta-heuristic optimization scheme.

3. The print production scheduler of claim 2, wherein the dispatcher module classifies the print requests within each container according to a distribution pattern including at least one of a first portion, a second portion, and a third portion with the respective portions arranged with the first portion corresponding to relatively higher priorities, the third portion corresponding to relatively lower priorities, and the second portion corresponding to relative priorities intermediate to the higher and lower relative priorities.

4. The print production scheduler of claim 3, wherein the second sort function produces the prioritized list of print requests for all containers via:

performing, in parallel for all adjacent pairs of containers, a merge function to merge together each adjacent pair of containers, wherein the third portion of one container is merged with the first portion of an adjacent container.

5. The print production scheduler of claim 1, wherein the intervals are defined to cause the containers to generally contain the same number of print requests and wherein the intervals are defined to at least one of a due date attribute, an elapsed slack time attribute, an estimated lead time attribute, a non-time based attribute, and a single criterion based on a combination of multiple attributes.

6. The print production scheduler of claim 1, wherein the dispatcher module includes:

an incoming print request function to receive a new print request to assign the new print request to one of the containers, to insert the new print request into an intermediate sorting solution for the assigned container, and to resume operation of the first sort function to the container to identify the relative priorities among all print requests for the container associated with the new print request.

7. The print production scheduler of claim 1, wherein the task-resource scheduler comprises an operations assessment function to determine the task-resource schedule based, in part, on real-time surveillance information from a production factory, wherein the surveillance information includes at least one of:

a per resource workload parameter;

a process rework parameter; and

a resource interruption parameter.

8. A print service provider system comprising:

a production scheduler module including a server having a non-volatile memory to store, and a processor to execute, machine readable instructions to provide;

a dispatcher module including;

a first sort function to sort a plurality of print requests for placement among containers, wherein each container is assigned a time interval, and each of the plurality of print requests is placed in one of the containers according to a time-based attribute of the print request and the time interval of the container where the print request is placed, and,

within each container, the first sort function is to sort priorities of the print requests within the container; and

a second sort function to merge the containers to produce a prioritized list of print requests for all containers;

a release function to release, upon a first periodic trigger signal, a portion of the prioritized list that includes a top N print requests; and

a task-resource scheduler module to convert the released list into, a task-resource schedule and upon a second periodic trigger signal, releasing the task-resource schedule; and

a print production facility including at least one printer to at least partially perform the task-resource schedule, wherein the print production facility includes a surveillance module to track real-time surveillance information at the print production facility including at least one of a resource workload parameter, a process rework parameter, and a resource interruption parameter,

wherein the task-resource scheduler module converts the released list into the task-resource schedule based at least partially on the real-time surveillance information.

9. The print service provider system of claim 8, wherein first sort function, the second sort function, and the task-resource scheduler perform at least some operations, according to an evolutionary-based, meta-heuristic optimization scheme in which a chromosome represents at least one of:

a prioritized sequence of print requests for the first and second sort function; and

a prioritized task-resource schedule for the conversion of the released list.

10. The print service provider system of claim 9, wherein at least one of the first sort function, the second sort function, and the task-resource scheduler temporarily terminate application of the optimization scheme according to a stop criteria including at least one of:

receipt of a periodic trigger event signal;

an increase of a fitness value between two consecutive generations in the optimization scheme is less than a threshold value; and

a fitness value exceeds another threshold value.

11. The print service provider system of claim 8, wherein the machine readable instructions provide:

a TAKT clock to issue trigger events to meter operation of the production scheduler module relative to the production facility, including synchronizing operation of the respective first and second sort functions of dispatcher module and the task-resource scheduler.

12. A non transitory computer readable medium storing machine readable instructions, executable on a processor, for performing an automated method of managing print production, the method comprising:

partitioning a pool of print requests among containers, wherein each container is assigned a time interval, and the partitioning includes placing each of the plurality of print requests in one of the containers according to a time-based attribute of the print request and the time interval of the container where the print request is placed;

within each container, determining priorities among print requests in the container; and

merging the containers to determine a global prioritized list of print requests for the containers;

releasing, upon a first periodic trigger signal, a portion of the prioritized list that includes a top N print requests; and

converting the released list into a task-resource schedule and releasing, upon a second periodic trigger signal, the task-resource schedule for print production.

13. The computer readable medium of claim 12, comprising:

upon admission of a new print request, performing an incremental optimization according to a most recent optimization solution of at least one of;

the relative priorities within a respective one of the containers;

the merging of containers; and

the task-resource schedule,

wherein the incremental optimization and the most recent optimization solution are performed according to a population-based computation optimization scheme.

14. The computer readable medium of claim 12, comprising:

classifying the print requests within each container, according to a distribution within the container of the relative priorities, into at least one of a first portion, a second portion, and a third portion;

arranging the first portion to include relatively higher priorities within the respective container, the third portion to include relatively lower priorities within the respective container, and the second portion to include relative priorities intermediate to the relative priorities of the first and third portions; and

performing, in parallel for all adjacent pairs of containers, a merge function to merge together each adjacent pair of containers to produce the global prioritized list, wherein the third portion of one container is merged with the first portion of an adjacent container.

15. The computer readable medium of claim 12, wherein the method comprises:

receiving, upon a periodic trigger signal, real-time surveillance information from a production facility, the surveillance information including at least one of a factory workload parameter on a per resource basis, a process rework parameter, and a resource interruption parameter; and

performing at least one of the repeated determinations of the relative priorities, the merging of containers, and the converting of the released list according to the surveillance information.