Abstract:
A printshop contains resources that are utilized to complete print jobs. The resources are partitioned into autonomous cells. Each autonomous cell is capable of completing at least one class of print job. Print jobs are assigned to the autonomous cells for completion. An autonomous cell may subdivide a print job into smaller sized lots and process the smaller size lots in parallel. This approach enhances the efficiency of the shop, decreases the work in progress, labor and inventory costs associated with running the print jobs and increases the utilization of the printing equipment in the printshop.

Description:
TECHNICAL FIELD OF THE INVENTION 
     The present invention relates generally to printing and more particularly to optimization of printshop resources via the use of autonomous cells. 
     BACKGROUND OF THE INVENTION 
     Conventional printshops are organized in a fashion that is functionally independent of print job complexity, print job mix, and total volume of print jobs. Typically, related equipment is grouped together. Thus, all printing equipment is grouped and located in a single locale. Similarly, all finishing equipment is grouped and located in a single locale. In other words, conventional printshops organize resources into separate departments, where each department corresponds to a type of process or operation that is performed to complete a print job. 
     When a print job arrives from a customer, the print job sequentially passes through each department. Once the print job is completely processed by a first department, the print job gets queued for the next department. This approach continues until the print job is completed. Unfortunately, this conventional approach leads to significant time delays and increased work-in-progress and inventory costs. 
     SUMMARY OF THE INVENTION 
     The present invention addresses the above-described limitations. In accordance with one embodiment of the present invention, a printshop is partitioned into autonomous cells. In addition, print jobs are partitioned into classes such that each autonomous cell contains sufficient resources to complete a print job of at least one class. Thus, for example, an autonomous cell may include equipment, such as multiple printers, a shrink wrapper and a computerized control system. A second autonomous cell may include different varieties of printers, cutters and copiers. The present invention intelligently divides the resources into autonomous cells and then assigns print jobs to the autonomous cells. 
     The assignment of print jobs to autonomous cells is done intelligently to provide desired load balancing and throughput. Moreover, print jobs are assigned to cells based on whether the cells have sufficient types of resource to complete the print job. The assignment of print jobs to the autonomous cells may be determined dynamically based upon the current queue of print jobs, current available capacity and current operating loads of the respective autonomous cells. The structure and composition of the cells themselves may be determined dynamically based upon the profile of jobs to be performed by the printshop at any given time. 
     In accordance with one aspect of the present invention, a method is practiced in a printshop having resources for performing various tasks. The resources are divided into autonomous cells, where each autonomous cell has sufficient resources to produce one or more classes of print job. Each print job is assigned to one of the cells for printing. 
     In accordance with another aspect of the present invention, a printshop is partitioned into autonomous cells, and a print job is received for printing at the printshop. The print job is sent to a selected one of the autonomous cells that has equipment for completing the print job. Alternatively, the print job may be divided into lots and the lots are concurrently processed either on separate items of equipment in the selected autonomous cell or in separate cells. 
     In accordance with another aspect of the present invention, a method is practiced for partitioning a printshop into autonomous cells. Products that are to be produced by the printshop are identified, and the operations required for each of the identified products are specified. A determination is made to specify the printshop resources that are received or required for the identified operations. A determination is also made to specify the printshop resources that are required for operations to produce the product based on customer demand for the products. The printshop resources are partitioned into autonomous cells based on the determined number of printshop resources required for operations to produce products based on customer demand for products. Each autonomous cell is independently capable of producing at least one of the identified products. This partition is re-examined and re-optimized repeatedly as the customer demand for products changes. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
       An illustrative embodiment of the present invention will be described below relative to the following drawings. 
         FIG. 1  is a flow chart that provides an overview of steps that are performed in the illustrative embodiment of the present invention. 
         FIG. 2  is a flow chart that illustrates the steps that are performed to generate a graphical representation of job flow. 
         FIG. 3  is an example of a graphical representation of printshop resources in accordance with the illustrative embodiment. 
         FIG. 4  is a flow chart that illustrates the steps that are performed to partition printshop resources into autonomous cells from the job flow representation. 
         FIG. 5  is a diagram depicting how a printshop is partitioned into four autonomous cells. 
         FIG. 6  is a flow chart illustrating the steps that are performed to determine whether to reconfigure the autonomous cells of a printshop. 
         FIG. 7  is a flow chart illustrating steps that are performed in determining whether to assign a print job to a particular autonomous cell in the illustrative embodiment. 
     
    
    
     DETAILED DESCRIPTION OF THE INVENTION 
     The illustrative embodiment of the present invention provides an approach to partitioning resources in a printshop efficiently so as to optimize performance of the printshop. Printshop resources, such as printers, copiers, cutters, shrinkwrappers and other varieties of equipment, are partitioned into autonomous cells. When a print job arrives, it is assigned to a particular autonomous cell for completion. Each autonomous cell may act independently from the other autonomous cells in processing a print job. Print jobs may be partitioned into smaller-sized lots that are concurrently processed by autonomous cells in order to optimize the efficiency and throughput of each autonomous cell. Moreover, multiple print jobs may be processed concurrently by an autonomous cell, and multiple print jobs may be executed concurrently by multiple autonomous cells in parallel. 
     Printshop resources are intelligently divided into autonomous cells. An analysis is made of print jobs that are typically performed by a printshop. Each type of print job is classified into a print job class according to the resources required to execute it. A print job class may be depicted graphically as a set of operations that are connected by edges representing the sequence of flow of operations in the print job. The capacity of each of the pieces of equipment in the printshop to perform operation is determined. The capacity for each print job class needed to meet the customer requirements is determined. The printshop resources may then be organized into autonomous cells and used during operation in an optimal fashion 
       FIG. 1  shows a flow chart that provides an overview of steps performed in the illustrative embodiment of the present invention. Initially, the expected job flow in a printshop is collected and analyzed to determine the types (“classes”) of jobs to be performed and the number of each per unit time (step  102  in  FIG. 1 ). The printshop is analyzed to design and propose autonomous cells into which the printshop resources may be divided so as to optimize the flow of jobs through the shop (step  104  in  FIG. 1 ). Each autonomous cell represents a grouping of one or more resources in the printshop that is capable of executing at least one class of print job. The autonomous cell may be able to complete the execution of multiple classes of print jobs or even all of the classes of print jobs. The partitioning of the resources into autonomous cells will be described in more detail below. A “printshop,” as used herein, refers to a grouping of resources used in completing a print job. A printshop may be part of a corporation, a free-standing shop, or other variety of organization. 
     Once the printshop resources have been divided into proposed autonomous cells, the proposed “virtual” cell configuration is tested and evaluated (step  106  in  FIG. 1 ). This testing and evaluation helps to ensure that the virtual cell configuration works well and produces acceptable results. If the proposed virtual cell configuration does not produce acceptable results (see step  108  in  FIG. 1 ), the above-described process repeats again beginning with step  104  so as to design and propose new autonomous cells. 
     If the results are acceptable (see step  108  in  FIG. 1 ), then a detailed cell layout is constructed (step  110  in  FIG. 1 ). The workflow within the print job is restructured to correspond with the cell layout. Scheduling algorithms are then constructed as well (step  112  in  FIG. 1 ). Once this is completed, the use of the autonomous cells becomes formally implemented (step  114  in  FIG. 1 ). The physical layout of the printshop may be restructured to account for the autonomous cells (step  116  in  FIG. 1 ). 
     In order to facilitate proper operation of the printshop to account for the use of autonomous cells, printshop personnel must be properly trained (step  118  in  FIG. 1 ). The printshop personnel must perform necessary tasks and must understand how the cells operate. The initial execution within the printshop is monitored to ensure that performance is acceptable (step  120  in  FIG. 1 ). The scheduling algorithms may be tuned up to produce more optimal results in the response to the monitoring (step  122  in  FIG. 1 ). 
       FIG. 2  is a flow chart illustrating steps that are performed to produce a graphical representation of the job flow in the printshop. This job flow depicts operations performed by resources in the printshop. Printshop resources include equipment, such as printers, copiers, rollers, shrinkwrappers, sealers and other varieties of equipment that are typically used to complete a print job. Those skilled in the art will appreciate that a wide variety of different types of equipment may be categorized as printshop resources, being included within autonomous cells in the illustrative embodiment. For example, manual resources may be partitioned as part of an autonomous cell. 
     In the illustrative embodiment of the present invention, the partitioning of the printshop into autonomous cells relies upon empirical data. The empirical data is gathered over a period of time, such as a few months or years, to identify the varieties of print jobs that are performed on the behalf of customers at a printshop (step  202  in  FIG. 2 ). The print jobs may be classified into print job classes. For example, the print job classes may be print-insert, print and self-mail, and print and shrink wrap. Each print job class represents a sequence of operations that need to be performed by printshop resources to complete a print job of the specified class. Thus, print jobs that require the exact same sequence of operations are classified into the same printshop class. Accordingly, a first step is to classify the empirically-derived data regarding print jobs so that each of the print jobs is classified into one of the given print job classes (Step  204  in  FIG. 2 ). Operations are determined for each print job class (step  206  in  FIG. 2 ). In other words, the operations that are performed for print jobs of the print job class are identified. Then, the aggregate demand for each operation is determined from the empirical data (step  208  in  FIG. 2 ). 
     A graphical representation of each print job class is developed by analyzing the flow between operations (step  210  in  FIG. 2 ). In particular, each print job operation is represented as a node and each edge constitutes a transition from one operation to a next that is required for a variety of print job class.  FIG. 3  shows an example of such a graphical representation of three varieties of print job classes. A first print job class is represented by nodes  302 ,  304 ,  306  and  312 . These nodes  302 ,  304 ,  306  and  312  and the associated edges specify a sequence of operations to be performed to complete a print job of the specified print job class. A second print job class is represented by nodes  302 ,  304 ,  308  and  312  and the associated edges interconnecting these nodes. A third and final print job class is represented by nodes  302 ,  304 ,  310  and  312  and the associated edges. 
       FIG. 4  shows in more detail the steps that are performed to design and propose autonomous cells (see step  104  in  FIG. 1 ). The job flow graph is partitioned into autonomous cells (step  400  in  FIG. 4 ). A suitable form of graph partitioning algorithm for performing this partitioning is specified in, “A concurrent approach to cell formation and assignment of identical machines in group technology,” N. Wu, International Journal of Production Research, 1998, Vol. 36, No. 8; 2099–2114. Those skilled in the art will appreciate that the cells may also be partitioned using other techniques. The autonomous cells that result from the partitioning of the job flow graph are then mapped onto the physical layout of the printshop (step  402  in  FIG. 4 ). 
       FIG. 5  shows an example of the partitioning of a printshop into autonomous cells. The printshop  560  shown in  FIG. 4  is partitioned into four cells numbered  1  through  4 . Cell  1  includes printers  562 ,  564  and  566  and copiers  576 ,  578  and  580 . Each of the copiers has an attached inserter  570 ,  572  and  574 . A cutter  568  is also included in cell  1 , as are computing resources  582 ,  584  and  586 . The computing resources may include server computers that execute software for automatically assigning print jobs to given cells and for processing print jobs once they have arrived in given cells. Moreover, the computing resources  582 ,  584  and  586  may provide the ability of operators to control operation of the equipment within the cell. 
     Cell  2  includes a computer system  592  and a highlight printer  590 . Cell  3  includes a printer  594  as well as a sealer  598  and computer system  596 . Lastly, cell  4  includes a shrink wrapper  503 , a computer system  505 , a printer  507  and a roll system  509 . 
     The resulting partitioning and mapping of autonomous cells is evaluated by computer simulation (step  404  in  FIG. 4 ). The computer simulation attempts to simulate real-time printshop operation conditions. Certain constraints may be placed upon the autonomous cells. In step  406  of  FIG. 4 , a determination made whether the constraints have been satisfied and whether the flow of operations between autonomous cells is minimal. In general, a cell should be self-contained such that there is no need for a cell to communicate with another cell in order to complete a print job. If the inter-cell flows are small and the constraints are satisfied (see step  406  in  FIG. 4 ), the resulting cell layout and job class mapping algorithm are utilized. On the other hand, if the inter-cell flows are not small and the constraints are not satisfied, the inter-cell flow metric is revised to capture constraints in a different way (step  408  in  FIG. 4 ). 
       FIG. 6  is a flow chart illustrating the steps that are performed when a print job is received in a printshop that has been organized into autonomous cells. Initially, a print job is received at the shop (Step  602  in  FIG. 6 ). The submission of the print job may be performed by a customer walking into the printshop and making a verbal request for a print job. Alternatively, the print job may be received electronically. The specification of the print job identifies the tasks that are to be performed to complete the print job. This specification may also identify the timing required of the print job and particular features that are to be incorporated into the print job, such as type of printing to be used, type of stock to be used, whether binding is to be used and the like. The print job is analyzed to identify the operations that it requires and the quantity of operations that are required by the job (step  604  in  FIG. 6 ). A determination is made whether the print job can fit into an existing cell (step  606  in  FIG. 6 ). If the print job will fit into an existing cell, a cost estimate and a schedule for printing the print job are prepared (step  608  in  FIG. 6 ). If the cost and the schedule are acceptable to both the printshop and the customer (step  610  in  FIG. 6 ), the job is accepted (step  614  in  FIG. 6 ). If they are not acceptable to the printshop and/or the customer, the print job is rejected (step  612  in  FIG. 6 ). If the print job is accepted, it is assigned to an autonomous cell (step  616  in  FIG. 6 ) and subsequently sent to the autonomous cell (step  618  in  FIG. 6 ). 
     If in step  606  of  FIG. 6  it is determined that the print job does not fit into an existing cell, a determination is made whether it is feasible to have a new mapping onto the existing cells (step  620  in  FIG. 6 ). If it is feasible, such a mapping is performed so as to use existing cells (step  622  in  FIG. 6 ). If it is not feasible to map the print job onto the existing cells using a different mapping, an assessment of the print job value is made and an assessment is made of the reconfiguration cost which would be associated with reconfiguring the autonomous cells (step  624  in  FIG. 6 ). A cost estimate and schedule are prepared for performing the job in the reconfigured printshop (step  626  in  FIG. 6 ). If the cost and schedule are not acceptable to both the printshop and the customer (see step  628  in  FIG. 6 ), the print job is rejected (step  630  in  FIG. 6 ). In contrast, if the cost and schedule are acceptable to both the print job and to the customer, the printshop is reconfigured (step  632  in  FIG. 6 ). In particular, a new mapping of autonomous cells is generated. The print job is then assigned to one of the cells (step  634  in  FIG. 6 ) and sent to the associated cells (step  636  in  FIG. 6 ). 
     A number of different criteria may be applied to determine which autonomous cell to assign to a received print job.  FIG. 7  provides a flow chart illustrating an approach as adopted by the illustrative embodiment to the present invention. The cells may be examined in a predefined sequence, such as a round robin sequence or based upon utilization. For example, the process depicted in  FIG. 7  may initially begin with the least busy cell and continue with successively more busy cells until a suitable cell is found for processing the print job. Thus, initially, the cell of interest is examined (step  700  in  FIG. 7 ). First, a determination is made whether the cell has the proper resources for completing the print job (step  702  in  FIG. 7 ). For example, if a print job requires shrinkwrapping in the shop described in  FIG. 5  then cell  4  is used. Only cell  4  has a shrinkwrapper, and, thus, cells  1 ,  2  and  3  do not have the proper resources for completing the print job. A test may then be made whether the cell has sufficient available capacity to complete the print job within specified time requirements (step  704  in  FIG. 7 ). If a cell does not have enough capacity to print the print job in a timely fashion, then the cell may not be utilized to complete the print job. Those skilled in the art will appreciate that other criteria may also be applied (see step  706  in  FIG. 7 ) to determine whether to assign a print job to a given cell or not. In cases where the examined cells can not be used, a next cell is then examined (step  708  in  FIG. 7 ) until either it is validated that no suitable cell is available (step  707  in  FIG. 7 ) or until a suitable cell is found. If a suitable cell is found, the print job is assigned to the examined cell (step  710  in  FIG. 7 ). If no suitable cell can be found, the alternatives are examined as described in  FIG. 6 . 
     While the present invention has been described with reference to an illustrative embodiment thereof, those skilled in the art will appreciate that various changes in form and detail may be made without departing from the intended scope of the present invention as defined in the appended claims.