Scheduling high priority print jobs with minimal print waste

Systems and methods are provided for scheduling high priority print jobs with minimal paper waste. One embodiment is a printing system that includes a print controller having a print data path with intermediate queues and a last queue to store print ready bitmap data. The print controller monitors the last queue to determine an estimate time for printing the print ready bitmap data stored in the last queue, determines whether the estimate time exceeds a time threshold, and determines whether a high priority print job is detected in the job storage system. In response to determining that the estimate time exceeds the time threshold and detecting the high priority print job, the print controller halts processing of at least one of the plurality of print jobs that is not the high priority print job, and advances processing of the high priority print job on the print data path.

FIELD

This disclosure relates to the field of production printing systems and, in particular, to scheduling high priority print jobs with minimal print waste.

BACKGROUND

High-speed production printers typically include a print controller that includes a print data path from a job storage system that spools print jobs to one or more print engines (also referred to as an “imaging engine” or as a “marking engine”). The print data path includes several components that process the print jobs to prepare pages for printing. Examples of components include a segmenter to segment a print job into pages, a layout master to create sheetsides, a rasterizer to rasterize the sheetsides into bitmaps, and a mechanism module to dispatch the sheet bitmaps (i.e., front and/or back sheetsides) to a print engine that physically marks paper using the sheetside bitmaps.

The components along the print data path may have queues to temporarily store data in memory for performing its job processing functions. As processing operations are completed, the data is forwarded down the print data path to the next component and queue, and the queues are continually depleted and refreshed in this manner as print jobs are processed in the print controller. To maintain printing at a high-speed, the print controller keeps the print data path sufficiently full with data such that the last queue feeding the print engine is able to continually feed the print engine with sheets at a fast rate. If the queue feeding the print engine runs empty, a condition known as a “back hitch” may occur in which the print engines stop printing and/or unintended blank pages fill the paper path and exit the printer.

In current print systems, when a user designates a print job as having a high priority (e.g., to print it soon at the expense of other previously submitted print jobs in various stages of processing in the print controller), it is necessary to clear the queues of the print data path to make room for processing the high priority print job. As such, when a high priority print job is detected, the print data path is immediately cleared to make way for the high priority print job. However, immediately cancelling a print job and clearing its data from the print data path means that the queues are emptied. Therefore, scheduling a high priority print job in current high-speed print systems often means creating a back hitch condition and wasting a significant amount of paper.

SUMMARY

Embodiments described herein provide for scheduling high priority print jobs with minimal paper waste. The print controller checks for a high priority print job after confirming that the last queue feeding the print engine has a sufficient amount of data such that it does not become empty by the time print data of the high priority print job begins reaching the last queue. If this condition is met and there is a high priority print job waiting to begin processing, the print controller partially clears the print data path by erasing data from the intermediate queues up to the last queue (i.e., excluding the last queue from erasure). Therefore, the high priority print job can begin processing soon while avoiding the back hitch condition. Furthermore, the last job placed in the last queue is allowed to complete, and thus the print controller waits to clear the print data path until there is no more data in it that contributes to the last job in the last queue.

One embodiment is a printing system that includes a job storage system configured to receive a plurality of print jobs from at least one host system, and to store the plurality of print jobs. The printing system also includes a print controller having a print data path from the job storage system to at least one print engine of the printing system, the print data path including one or more intermediate queues to temporarily store data of one or more print jobs for processing by the print controller, the print data path further including a last queue to temporarily store print ready bitmap data from at least one print job prior to dispatching the print ready bitmap data to the at least one print engine for imaging. The print controller configured to monitor the last queue to determine an estimate time for printing the print ready bitmap data stored in the last queue, to determine whether the estimate time exceeds a time threshold, and to determine whether a high priority print job is detected in the job storage system. The print controller further configured, in response to determining that the estimate time exceeds the time threshold and detecting the high priority print job, to halt processing of at least one of the plurality of print jobs that is not the high priority print job, and to advance processing of the high priority print job on the print data path.

Other illustrative embodiments (e.g., methods and computer-readable media relating to the foregoing embodiments) may be described below. The features, functions, and advantages that have been discussed can be achieved independently in various embodiments or may be combined in yet other embodiments further details of which can be seen with reference to the following description and drawings.

DESCRIPTION

The figures and the following description illustrate specific illustrative embodiments of the disclosure. It will thus be appreciated that those skilled in the art will be able to devise various arrangements that, although not explicitly described or shown herein, embody the principles of the disclosure and are included within the scope of the disclosure. Furthermore, any examples described herein are intended to aid in understanding the principles of the disclosure, and are to be construed as being without limitation to such specifically recited examples and conditions. As a result, the disclosure is not limited to the specific embodiments or examples described below, but by the claims and their equivalents.

FIG. 1illustrates a printing system100in an illustrative embodiment. The printing system100includes one or more host system(s)110, a print controller120, and a printer150. The printer150may comprise a high-speed printer used for volume printing, such as 100 pages per minute or more. The printer150includes one or more print engines152-154to physically mark a print medium160(e.g., paper). In this example, the printer150is a continuous forms printer having an input paper roll162, a first print engine152(e.g., that prints on a front side of the print medium160), a second print engine154(e.g., that prints on a back side of the print medium160), and an output paper roll164. It will be appreciated, however, that the concepts described herein may also apply to cut sheet printers and alternative production printers having various architectures, finishing devices, etc.

The print controller120generally interfaces with the host systems110to receive print jobs, and prepares the print jobs for printing on the print engines152-154. To perform functions, the print controller120may be implemented by a processor122communicatively coupled to a memory124. The processor122includes any electronic circuits and/or optical circuits that are able to perform functions. For example, the processor122may include one or more Central Processing Units (CPUs), Graphics Processing Units (GPUs), microprocessors, Digital Signal Processors (DSPs), Application-specific Integrated Circuits (ASICs), Programmable Logic Devices (PLDs), control circuitry, etc. Some examples of processors include INTEL® CORE™ processors, Advanced Reduced Instruction Set Computing (RISC) Machines (ARM®) processors, etc. The memory124includes any electronic circuits, optical circuits, and/or magnetic circuits that are able to store data. For instance, the memory124may include one or more volatile or non-volatile Dynamic Random Access Memory (DRAM) devices, FLASH devices, volatile or non-volatile Static RAM (SRAM) devices, magnetic disk drives, Solid State Disks (SSDs), etc. Some examples of non-volatile DRAM and SRAM include battery-backed DRAM and battery-backed SRAM.

FIG. 2is a block diagram of a printing system100in an illustrative embodiment. As shown inFIG. 2, the print controller120may include a job storage system210, a raw data preprocessing system220, an rasterization system230, and a mechanism module240. The job storage system210comprises any system, device, or component operable to receive print jobs202from one or more of the host systems110, and store the print jobs202in a raw job spool212. The print jobs202may optionally include job tickets and so for ease of reference, the print jobs202may refer to print jobs with or without corresponding job tickets. The job storage system210also includes a despooler214to retrieve a print job from the raw job spool212and forward the raw data216for the print job to the raw data preprocessing system220along a print data path250.

The raw data preprocessing system220comprises any system, device, or component operable to receive the raw data216for the print jobs202, and perform preprocessing on the raw data216before the print jobs202are interpreted. In this embodiment, the raw data preprocessing system220includes a segmenter222to segment the print jobs202into segmented pages224, and a layout master226to create raw sheetsides228based on the segmented pages224. The layout master226may thus include layout functionalities to assemble the segmented pages224into raw sheetsides228. The segmenter222forwards data to the layout master226via an intermediate queue262on the print data path250. Similarly, the layout master226forwards data to the rasterization system230via an intermediate queue264on the print data path250.

The rasterization system230comprises any system, device, or component operable to interpret, render, rasterize, or otherwise convert the raw sheetsides228for print jobs into print ready bitmap data234for the print jobs. As such, the rasterization system230may include one or more Page Object Handlers (POHs)232operable to render the raw sheetsides228to generate the print ready bitmap data234. The POHs232may render multiple raw sheetsides228concurrently so that the rate of rendering substantially matches the rate of imaging of production print engines. The rasterization system230may forward the print ready bitmap data234along a last queue266of the print data path250to the mechanism module240.

The mechanism module240comprises any system, device, or component operable to control the transfer of the print ready bitmap data234to the print engines152-154for subsequent printing. Generally, the print ready bitmap data234that is transferred from the last queue266causes one of print engines152-154to which it has been sent to print based on the print ready bitmap data234it has received. As such, the last queue266is generally the last queue on the print data path250that stores print data before the print data is used for physically marking the print media. The mechanism module240may attempt to pull a sheet out of the last queue266, and if there are none (i.e., the last queue266is empty), the mechanism module240may issue a stop command, potentially causing a back hitch. Moreover, if the print engines152-154are full, the mechanism module240may temporarily pause transfer of the print ready bitmap data234to wait for a sheet to finish sending to the print engines152-154, and then pull the next sheet from the last queue266. Although a particular architecture of the print controller120is shown and described with respect toFIG. 2for purposes of discussion, it will be appreciated that alternative architectures are possible, including alternative component and queue configurations. For example, the print controller120may include other intermediate queues in addition to or instead of the intermediate queues262-264of the segmenter222and the layout master226, and the last queue266may be part of alternative components or devices (e.g., the print engines152-154) that are controllable by the print controller120. The print controller120and the print engines152-154may both be implemented in the same printing system100or may be implemented separately and coupled together.

To coordinate overall operation, the print controller120includes a control system270that is enhanced with a job scheduler272and a queue manager274. The job scheduler272is configured to detect a high priority print job in the job storage system210, and to schedule the high priority job such that it prints at the print engines152-154soon with minimal paper waste and printing downtime. The queue manager274is configured to manage and prepare queues of the print data path250(e.g., the intermediate queues262-264and the last queue266) for the suitable conditions that enable scheduling and processing a high priority print job without causing paper waste and printing delay. Alternatively or additionally, the queue manager274may halt processes performed in the print data path250(e.g. those processes performed by the segmenter222, the layout master226and/or the POH232). Generally, the job scheduler272and the queue manager274coordinate to avoid depleting the print data path250in processing a high priority print job. That is, instead of immediately clearing all queues of the print data path250or interrupting print jobs mid-job, the control system270may wait before initializing the high priority print job to ensure that the print data path250, exclusive of last queue266, does not contain any portions of a print job currently in the last queue266. The print controller120may implement or interface with a graphical user interface (GUI)280of the printing system100that enables user input (e.g., via keyboard, mouse, display screen, etc.) indicating a maximum period of time of waiting so that high priority print jobs may be scheduled according a user's preferences for printing soon performance. Illustrative details of the operation of the print controller120will be discussed with regard toFIG. 3.

FIG. 3is a flowchart illustrating a method300for scheduling a high priority print job in an illustrative embodiment. The steps of the flowcharts are described with reference to the print controller120ofFIGS. 1 and 2, but those skilled in the art will appreciate the methods may be performed in other systems. The steps described herein are not all inclusive, may include other steps not shown, and may be performed in alternative orders.

In step302, the job storage system stores print jobs. In step304, the job scheduler272schedules print jobs to begin processing on a print data path250of the print controller120. As described above with respect toFIG. 2, the print data path250includes one or more intermediate queues262-264to temporarily store data of one or more print jobs for processing by the print controller120. Additionally, the print data path250includes the last queue266to temporarily store the print ready bitmap data234of at least one print job prior to dispatching to at least one of the print engines152-154for imaging.

In step306, the queue manager274monitors the last queue266to determine an estimate time for printing the print ready bitmap data234stored in the last queue266. The queue manager274may estimate the time to finish printing based on a number of remaining sheets of a print job which are stored in the last queue266, a number of copies to be printed, and/or a speed of the printer (e.g., a rated speed of the print engines152-154).

In step308, the queue manager274determines whether the estimate time exceeds a time threshold. The time threshold may be received via user input to the GUI280. If the estimate time does not exceed the time threshold, the method300may return to step304and repeat steps304-308. In doing so, the job scheduler272may instruct the despooler214to retrieve print data according to a normal order of print job processing. Otherwise, if the estimate time does exceed the time threshold, the method300may proceed to step310.

In step310, the job scheduler272determines whether a high priority print job is detected in the print data path250. The priority level of a print job may be indicated by a user via the GUI280. Alternatively, the priority level of a print job may be indicated in a print job ticket or set via a user of the host systems110. If a high priority print job is not detected in the job storage system210, the method300may return to step304and repeat steps304-310, thereby allowing already scheduled jobs to keep being processed, since the print data path250may have multiple jobs in processing at a time. Otherwise, if a high priority print job is detected in the job storage system210, the method300proceeds to step312.

In step312, the queue manager274halts the processing of at least one print job of the plurality of print jobs in the print path250without clearing the last queue266. Further, the halting is done without halting the processing of the high priority print job. Further still, halting the processing may include any combination of erasing (e.g. purging or clearing) at least some data currently associated with the at least one print job and interrupting at least some processes currently associated with the at least one print job. Data associated with the at least one print job may include data stored in the intermediate queues262-264, processes, other hardware devices, and other software applications in print data path250. Processes associated with the at least one print job may include processes in the print data path250. Examples of processes in data path250include the segmenter222, the layout master226, and POH232. Then, in step314, the job scheduler272initiates the next processing step of the high priority print job on the print data path250. In performing the method300, the control system270is able to confirm that the last queue266has sufficient data before halting the processing of the at least one print job to allow for the high priority print job to advance along the print data path250. The method300provides a benefit over prior techniques for scheduling high priority print jobs because the high priority print job can begin or continue processing on the print data path250without allowing the last queue266to empty.

FIG. 4is a flowchart illustrating a method400for scheduling a high priority print job in another illustrative embodiment. The steps of the flowcharts are described with reference to the print controller120ofFIGS. 1 and 2, but those skilled in the art will appreciate the methods may be performed in other systems. The steps described herein are not all inclusive, may include other steps not shown, and may be performed in alternative orders.

In step402, the control system270receives a time threshold value for the last queue266. Alternatively, control system270receives user input (e.g., via GUI280) indicating a time threshold value for the last queue266.FIG. 5illustrates a graphical user interface500for receiving user input for a high priority print job in an illustrative embodiment. As shown inFIG. 5, a user may select a print job in the job storage system210having a job identifier502, and designate a priority level504and/or a timing threshold506for the selected print job. More particularly, the user may select to “print now” to immediately begin processing the selected print job, to “print next” to schedule the selected print job at a job boundary (i.e., to begin immediately after the current job finishes, along with all copies), or to “print soon” to schedule the selected print job without disrupting the printing that is already in progress. Assume, for this example, that the user has selected the priority level504of print soon and selected the timing threshold506value as 45 seconds via GUI280.

Returning toFIG. 4, in step404, the print controller120gets the next sheet to examine. That is, the print controller120in operation continues to rasterize sheets of print jobs202and forward those sheets along the print data path250. In step406, the control system270determines whether the potential sheet is part of the same print job in last queue266or a first print job. If so, the method400proceeds to step408and the control system270determines whether the size of the last queue266is a maximum size. If the size of the last queue266is not maximum, the method400proceeds to step410to resize the last queue266to its maximum size. Otherwise, if the last queue266size is already its maximum (in step408) or it has been resized (in step410), the method400proceeds to step412and the control system270adds the time to print the sheet (including time to print copies of the sheet) to the estimate of time to print last queue266. Then, in step414, the control system270forwards the sheet on to the last queue266. That is, the control system270may attempt to put the sheet on the last queue266, and if the last queue266is full, the attempt completes after a sheet is removed from the last queue266by the mechanism module240. In this way, the control system270may update and track the estimate time for printing contents of the last queue266as sheets are added to the last queue266. The method400may then return to step404for the next sheet.

If, in step406, the control system270determines that the sheet is not part of the same print job in last queue266and not part of the first print job, the method400proceeds to step416. In other words, a negative output of step406may indicate a job boundary has been determined. In step416, the control systems270determines whether the estimate time for printing the last queue266is greater than a time threshold. For instance, in continuing with the example above, the control system270may determine whether the last queue266contains greater than 45 seconds of printing time. If not, the method400proceeds to step408such that the size of the last queue266may be reset to normal maximum and the print controller120can proceed unimpeded until the next job boundary. Otherwise, if in step416the control system270determines that the estimate time for printing the last queue266is greater than the time threshold, the method proceeds to step418.

In step418, the control system270resizes the last queue266based on the time threshold. For example, the queue manager274may restrict the number of entries of the last queue266according to the estimate time to finish printing contents of the last queue266. In other words, the queue manager274may resize the last queue266to the number of sheets last put on the last queue266whose times exceed the time threshold. This temporarily prevents a subsequent job from being placed on the last queue266. Then, in step420, the control system270determines whether a high priority print job is pending in the job storage system210. If not, the method400returns to step412-414, where the estimate time for printing sheet is added to the estimate time and the control system270may attempt to put the sheet into the last queue266, and the method400repeats beginning at step404. If a high priority print job is pending in step420, the method400proceeds to step422.

In step422, the control system270determines whether the print job is pending for the last queue266is the requested high priority print job. If so, the method400returns to step408so that the control system270may reset the last queue266to its normal maximum size and the print controller120can proceed unimpeded until the next job boundary. Otherwise, the method400proceeds to step424and the control system270performs a redrive without affecting the mechanism module240or the last queue266. In doing so, the queue manager275halts the processing of at least one print job of the plurality of print jobs in the print path250without clearing the last queue266and without halting the processing of the high priority print job. Further by doing so, the queue manager274may set aside the in-process job data by clearing out the intermediate queues262-264to make room for the high priority print job to be processed. In some embodiments, the queue manager274may perform a modified redrive operation in which queues of the print data path250are erased (e.g. cleared) excluding erasure of the last queue266on the print data path250. As such, the high priority print job may be processed and printed without waste or delay. In other embodiments, the queue manager274may find an alternate print data path and process the high priority print job in parallel, pausing (e.g., halting) the normal next print job until after the high priority print job completes. Alternatively or additionally, the queue manager274may interrupt at least some processes currently associated with the at least one print job.

In step426, the control system270sets the high priority print job as the current job. Accordingly, as the method400returns to step404, the print controller120may continue to process the high priority print job unimpeded (e.g., via steps406-414) until the next job boundary. Unimpeded, in this context, means that the last queue266is maintained at its normal, maximum capacity during processing of a print job. In using the method400, the control system270resizes the last queue266on-the-fly to ensure that the next print job is not put on the last queue266before the high priority print job is allowed to be started and begins to reach the last queue266. By resizing the last queue266to a smaller number of entries than are already in the last queue266, the control system270temporarily prevents a subsequent job from reaching the last queue266while it determines if there are any high priority print jobs to schedule. If there is sufficient room on the last queue266to ensure a back hitch condition is not created, either the next print job may be continued (if there is no high priority print job pending) or the high priority print job may be started. After a print job starts, the control system270may allow that print job to complete even if a high priority print job becomes pending, and the control system270may schedule the high priority print job to print as soon as possible yet after the last job in the last queue266completes placement on the last queue266. However, if the last queue266is insufficient, jobs may continue to be passed down the print data path250in front of the high priority print job. The control system270may interrupt the print data path250with the high priority print job after the last queue266is determined to have enough data to keep the print engines152-154running.

Moreover, if a high priority print job is present before a new entry is allowed on the last queue266, the data on the print data path250up to the last queue266may be discarded and the high priority print job may begin processing in the print controller120on the print data path250. Accordingly, in the method400, print jobs are held back from entering the print data path250for a time threshold maximum period of time to allow for insertion of a high priority print job without causing a back hitch condition. If the time threshold allows more time, the last queue266may become larger and allow more jobs (e.g., several minutes of printing time). That is, the time for printing contents of the last queue266is increased thereby reducing the probability of a back hitch. However, since jobs are not terminated after reaching the last queue266, this may increase the chance that a high priority print job is further delayed. Therefore, the user may set the time threshold according to a desired balance of reducing the time to begin processing a high priority print job versus reducing the chance that a back hitch is created.

Embodiments disclosed herein can take the form of software, hardware, firmware, or various combinations thereof. In one particular embodiment, software is used to direct a processing system of the print controller120to perform the various operations disclosed herein.FIG. 6illustrates a processing system600operable to execute a computer readable medium embodying programmed instructions to perform desired functions in an illustrative embodiment. Processing system600is operable to perform the above operations by executing programmed instructions tangibly embodied on computer readable storage medium612. In this regard, embodiments of the invention can take the form of a computer program accessible via computer-readable medium612providing program code for use by a computer or any other instruction execution system. For the purposes of this description, computer readable storage medium612can be anything that can contain or store the program for use by the computer.

Computer readable storage medium612can be an electronic, magnetic, optical, electromagnetic, infrared, or semiconductor device. Examples of computer readable storage medium612include a solid state memory, a magnetic tape, a removable computer diskette, a random access memory (RAM), a read-only memory (ROM), a rigid magnetic disk, and an optical disk. Current examples of optical disks include compact disk-read only memory (CD-ROM), compact disk-read/write (CD-R/W), and DVD.

Processing system600, being suitable for storing and/or executing the program code, includes at least one processor602coupled to program and data memory604through a system bus650. Program and data memory604can include local memory employed during actual execution of the program code, bulk storage, and cache memories that provide temporary storage of at least some program code and/or data in order to reduce the number of times the code and/or data are retrieved from bulk storage during execution.

Input/output or I/O devices606(including but not limited to keyboards, displays, pointing devices, etc.) can be coupled either directly or through intervening I/O controllers. Network adapter interfaces608may also be integrated with the system to enable processing system600to become coupled to other data processing systems or storage devices through intervening private or public networks. Modems, cable modems, IBM Channel attachments, SCSI, Fibre Channel, and Ethernet cards are just a few of the currently available types of network or host interface adapters. Display device interface610may be integrated with the system to interface to one or more display devices, such as printing systems and screens for presentation of data generated by processor602.