Transducers With Constraints Model for Print Scheduling

The following pending applications are related: U.S. Ser. Nos. 472,151; 485,848; 475,003; and 485,846 filed Jun. 7, 1995.

1. Field of the Invention

The present invention relates to a system for developing Document Output Terminals from autonomous machine modules with standard control, data communication and physical interfaces.

2. Background of the Invention

Prior art includes U.S. Pat. No. 5,363,175, assigned to the same assignee as the present invention covering distributed job scheduling of modular components. Also pending U.S. Ser. No. 280,978 covers a controller interrogating processors for operational timing data for configuring the controller to operate in accordance with the operational timing of the processors.

Traditional product development usually begins with a core machine, typically the marking engine, and then develops modules tailored to work with the core machine. This approach produces tightly integrated machines composed of modules that are functionally interdependent. The products may be physically modular (easily separable for transportation) but they are not easily reconfigured nor can they typically be used on other products without extensive revision of the control software. With this type of development, it is difficult to use modules with any product other than the product for which they were developed. In addition to the physical considerations, for example, paper path heights, locations etc.) the modules generally have dependencies on other parts of the product, for example, user interfaces, schedulers, and paper path control. Thus, there is a need to create modules that are capable of stand alone operation and are insensitive to the neighboring modules. It is an object, therefore, of the present invention to provide a system that treats all modules uniformly, regardless of specific functions (such as feeding, finishing, and marking) and to provide open configurations, that is the number and sequence of modules is not fixed or limited.

It is another object to provide each module with a generic, uniformly described identification that is conveyed to the controller and the controller in turn composes the descriptions into a single machine description, in order that no matter the geometric configuration of the connected modules, the machine operates to complete a given job. The configuration of the modules, feeder, marker, or finisher is not pertinent. There might not even be a marker present for a machine to operate and complete a job. In other words there need not necessarily be only one marker or there need not be any marker and there may be any number of feeders or finishers.

It would also be desirable to provide a system that treats various machine modules uniformly but with the appropriate constraints. It is, therefore, an object of the present invention to treat various machine modules as transducers that have constraints specifying behavior and scheduling is accomplished by finding a sequence of transfers between the various transducer inputs and outputs that is consistent with the constraints. This allows a mix and match of markers, feeders, and finishers.

In the prior art, a machine module for a function such as to staple a set of copy sheets was very specific to the machine hardware and software architecture. This meant that the set of copy sheets delivered to the stapler must be in a very well defined orientation and format. In this configuration, only one manner of stapling was accommodated. However, with various stapling machines available from various vendors, more information is needed from the various staplers to determine if in fact a particular operation can be completed, that is, one machine might receive the set face up, staple it, and deliver the set face down. Another machine might do the same but with the output face up, another machine might not take sets in but only separate sheets. Trying to describe all possible permutations using DPA styled key words quickly becomes unmanageable.

It thus becomes desirable to provide a system wherein various permutations of various modules from various vendors can be easily expressed and understood by a control. It is an object of the present invention, therefore, to break descriptions into inputs, outputs, and the relationship between the inputs and the outputs enables the description of the machine into segments that are easily manageable. It is an object of the present invention to express capabilities of transducers which represents a machine, machine modules, or components within a machine module. The capabilities define what the transducer does, that, is identifies the kind of work unit that is entering or exiting on a given port of the transducer. It defines any constraints on timing of the work units and on attributes of the work units. It also defines the relationship between the inputs and the outputs in terms of work unit properties.

Traditionally, representing and controlling a machine was usually based upon certain assumptions about the interconnection of the machine. In particular, the assumption was that a marker module was at the center, with feeders upstream and finishers downstream from the marker with the arrangement being essentially linear. Any deviations from this linear interconnection in the prior were not possible, generally, without an almost total redesign of hardware and software. It would be desirable therefore to be able to represent and interconnect modules in a variety of modes deviating from the traditional linear interconnection and yet have the control recognize the particular interconnection and provide the appropriate response. It is an object of the invention, therefore to be able to interconnect modules in a variety of manners and to represent the interconnection in graphical form including mergers, forks, and parallel operations. It is another object, for any interconnection, including a connection of modules excluding a marker module, to be able to recognize the interconnection and suitably control the machine so formed to complete requested jobs. It is an object of the present invention for each module to communicate interconnection status to the master control which has initiated a request for interconnection status, and to be able to set up a control operation to direct the interconnected modules to complete assigned tasks.

In prior art machines scheduling of capabilities such as marking the front side of a page and also marking on the back side of the page were handled as individual task assignments and not viewed as a control task as a whole. It would be desirable, therefore, to treat interdependent tasks making up a general operation as a commitment group. A commitment group can be assigned to a task or series of tasks only if each capability or element within the commitment group is or can be committed. It is an object therefore for any machine configuration or arbitrary interconnection of modules to operate under the concept of a commitment group in the operation and control of the machine wherein a task requiring the commitment of one or several elements requires the commitment of each of the elements.

According to the present invention, an electronic image processing apparatus is provided with a controller and a plurality of resources in an arbitrary configuration. Each of the resources includes an associated processor storing data related to operational constraints of the associated resource and a bus interconnects the processors to the controller for directing the operation of the resources. The controller is adapted to operate independent of a particular configuration of the plurality of resources by receiving from each of the processors the data related to the operational constraints of each associated resource and interrogating each of the processors to determine the geometrical relationship of the interconnection of the resources. The controller then responds to the data related to the operational constraints of each of the processors and to the geometrical relationship of the interconnection of the resources to dynamically configure the image processing apparatus to operate in accordance with the the operational constraints of each of the processors and to the geometrical relationship of the interconnection of the resources.

FIG. 1 is a simplified elevational view showing the relevant parts of a printing apparatus, on which the present invention may operate;

FIG. 2 is a systems diagram showing a typical prior art machine configuration;

FIGS. 3, 4, and 5 illustrate arbitrary machine configurations capable of transparent control in accordance with the present invention;

FIG. 6 illustrates a universal controller in accordance with the present invention;

FIG. 7 illustrates a control architecture for the universal controller of FIG. 6 in accordance with the present invention;

FIG. 8 illustrates controller packaging of the universal controller of FIG. 6 in accordance with the present invention;

FIGS. 9 and 10 illustrate machine representations as transducers with constraints in accordance with the present invention; and

FIG. 11 illustrates machine module communication protocol in accordance with the present invention.

FIG. 1 is a simplified elevational view of the paper path of an on-demand printing apparatus, capable of simplex or duplex output, in which a stream of digital video signals representative of images desired to be printed causes the desired images to be formed on a selected side of a print sheet. The particular architecture shown in FIG. 1 is for an electrostatographic printer, but it will be understood that the principle of the invention could apply equally to other types of image-creation technologies, such as ink-jet printing. The printing apparatus, generally indicated as 10, contains one or more stacks of available sheets on which to print images, these stacks being indicated as 12a and 12b. The sheets of paper in the stacks 12a and 12b may differ in, for example, size, color, or the presence of a pre-printed letterhead. When it is desired to create an image on a sheet, a sheet of a desired type is drawn from a stack such as 12a or 12b, such as by respective feeders 14a, 14b, and the individual sheet is fed onto duplex loop 16.

Duplex loop 16 is typically in the form of an endless belt which is capable, by means of friction, static electricity, vacuum, or other means, of retaining a plurality of sheets thereon, thereby retaining a particular sheet until it is time for the sheet to receive an image on the side of the sheet facing outwardly from the belt of the duplex loop 16. In the architecture shown in FIG. 1, it is intended that sheets "ride" on the outer surface of the belt of duplex loop 16. Along one portion of duplex loop 16, the belt of duplex loop 16 comes into close contact with a photoreceptor belt indicated as 18. At the point of close proximity of duplex loop 16 and photoreceptor belt 18, there may be provided a transfer corotron 20, the function of which will be familiar to one of skill in the art of xerography.

In the xerographic-based embodiment of a printing apparatus shown in FIG. 1, a device which shall be here generally referred to as an "imager" creates an electrostatic latent image on the surface of photoreceptor 18. Imager 22 has the function of receiving a sequence of digital signals representative of the desired image to be printed, and outputs a physical manifestation, such as a modulated laser scanning beam, to imagewise discharge selected areas on the photoreceptor 18 to create an electrostatic latent image representative of the image desired to be printed. As is known in the art of electrophotography, other stations along the path of photoreceptor 18, such as a charging bar and development unit (not shown) are also required to create the desired developed image on the photoreceptor belt 18. This developed image, which is typically in the form of a reverse image in toner particles on the photoreceptor 18, is then made available to a sheet which rides on the outer surface of duplex loop 16.

After an image is created on the photoreceptor belt 18 by imager 22, and developed (by means not shown), the motion of photoreceptor belt 18 causes the developed toner image to be in close proximity or in contact with a sheet, originally from stack 12a or 12b, which is riding on the outer surface of duplex loop 16. At transfer corotron 20, the toner particles arranged in imagewise fashion on photoreceptor 18 are electrostatically transferred to the surface of the sheet by transfer corotron 20. Soon thereafter along the path of duplex loop 16, the toner image on the sheet is passed through a fuser 24, which causes the toner image to be fixed permanently on the outer surface of the sheet, in a manner known in the art. Thus, immediately downstream of fuser 24, there will be created a sheet having a desired image on the side thereof which faces outward along the duplex loop 16. If at this point the sheet having the image thereon is desired to be output from the system, a device such as router 26, a simple design of which is shown in FIG. 1, but which may be of any number of designs known in the art, will cause the sheet to be disengaged from the duplex loop 16 and output from the printer such as through the path indicated by arrow 28. This output sheet can either be directly output into a tray for pickup by the user, or may be sent to a sorting or stapling device according to the larger architecture of the printing apparatus.

It will be noted that the specifically electrostatographic aspects of the apparatus shown in FIG. 1, such as the photoreceptor 18, imager 22, and transfer corotron 20, could be replaced by equivalent apparatus for other techniques for creating images on one side of a sheet, such as an ink-jet printhead. Also, imager 22 as here described assumes that the user has unlimited control over the order of page images (the "digital video") being output through imager 22. If, however, the original source of images to be created is itself a set of automatically fed hard-copy images, i.e. if the printing system as a whole is operating as a copier, the feeding of originals will also create certain constraints on the optimal order of images created with the printer. It is probably preferable to digitize (convert to digital signals) the original hard-copy images, electronically store the resulting data, and apply the data as required to a digitally-based imager 22.

Referring to FIG. 2, there is shown a standard prior art interface provided by a printer to attach feeding and/or finishing devices. In particular, marking engine or printer 40 including a user interface with a screen is interconnected to document feeding device 42 and document finishing devices 46 and 48. As is well known, the feeding devices are sources of printable media like paper for providing printer 40 with stock for completion of the printing process. The finishing devices can be any suitable devices such as sorters, compilers, staplers, folders, or trimmers. Feeding devices are paper trays, and the need for feeding devices is to supply an increased level of printable stock selection to the printer.

The feeding/finishing devices are physically attached to the print engine such that sheets can be feed into the print engine or sheet or sets can be transferred from the print engine to the devices. The devices are attached to each other such that sheets or sets of paper can be transferred from one device to another.

Prior art devices are generally in a linear relationship having one print engine with sheet feeder or internal trays up stream and a finisher station downstream as shown in FIG. 2. A need exists to create modules that are capable of stand alone operation and are not control dependent to their neighboring modules. The solution is developing autonomous machine modules with standard control, data communication, and physical interfaces, such that each module is indifferent to it's neighbor and all modules can be modeled using common techniques. Document Output Terminals would be created by integrating collections of physical machine modules. A machine module is standalone, and makes no assumptions about any other machine module, to enable a liberal mix-and-match of modules. An important aspect of this approach is that all machine modules of a Document Output Terminal (DOT), whether finishers, markers, or finishers are treated identically, allowing nontraditional configurations such as feeders post-marking, tandem markers in series or parallel, feeders and finishers only with no marker, etc. as illustrated in FIGS. 3, 4, and 5.

For example, FIG. 3 shows the two markers 50, 52 in series with one feeder 54 and two finishers 56, 58. FIG. 4 illustrates markers 60, 62 in parallel with finisher 64 and no feeder module. FIG. 5 illustrates a configuration of 3 feeders 66, 68, and 70 connected to finisher 72 and no marker module in the configurations. The only constraints on configurations is that the inputs and outputs of the machine modules must match (i.e. can't connect a module that outputs sets to a module that only input sheets).

Since machine modules can be configured into arbitrary configurations, a small number of modules can yield a large number of configurations, each able to meet different needs of customers. For example, a suite of ten modules might be used to create fifty different configurations to meet fifty different types of customer needs. Using autonomous machine modules, this is reasonable; without autonomous machine modules it would be much more difficult to address to many different kinds of needs. Once a suite of machine modules has been developed, creating a new machine for a particular customer need can be orders of magnitude faster. In the ideal case, one simply selects which machine modules and how many of each are required, and ships them to the customers to be configured on site. In other cases, perhaps some modules already exist but some module would need to be developed or adapted to operate as an autonomous machine module. However, this is most likely still faster than developing an entirely new machine.

In accordance with the present invention, a Mark Facility Controller is a part of a Machine Control Software Architecture. The Mark Facility Controller manages, coordinates, and represents the entire connected configuration of feeder modules, marker modules, finisher modules and output modules. These are referred to collectively as Machine Modules. There is one Mark Facility Controller for a configuration of machine modules. This collection of machine modules along with a Mark Facility Controller is referred to as a Document Output Terminal or alternatively, a Mark Facility.

The basic concept of the Mark Facility is that jobs coming from various sources such as decomposers, scanners, file systems, etc. can be sent to a common Mark Facility interface independent of where the job is coming from, and independent of what physical machine modules make up the DOT. The Mark Facility Controller is responsible for taking the mark job (described primarily via an Assembly Tree) which is machine independent, mapping it on to the particular machine configuration present, and coordinating the machine modules to render the job.

Note that the Mark Facility Controller is not responsible for the Image Path. However, the Mark Facility Controller interacts closely with the Image Loader. The Image Loader is the demarcation point in the image path after which any further processing can be done in a deterministic amount of time. From the point of view of the Mark Facility Controller, the Image Loader acts as an "image flow control valve", and the Mark Facility Controller coordinates the "feeding of images" through the Image Loader along with and in the same manner as the feeding sheets.

FIG. 6, illustrates how the Mark Facility Controller would interact with the various modules of the Mark Facility as well as the client(s) of the Mark Facility Interface. In particular, there is shown a mark Facility controller 74 interconnected to arbitrary machine modules 76, 78, and 80 and image loader 82 by means of a page level control path shown at 84. Also shown connected to controller 74 are print server 86 and decompose facility 87 interconnected by means of either a service level control path 83 or job level control path 88. Also, the image loader 82 can be connected between decompose facility 87 and a marker module, such as 78 by means of a page level image path 90. Other operations such as a copy service, scan facility, and file system can also be part of the system. The diagram is an example configuration, not the required configuration. The service level control path 83 provides control of the entire Mark Facility (e.g. suspend the facility, resume the facility, submit mark job, cancel mark job, etc). The job level control path 88 would be used for streaming a job description (i.e. assembly tree); page level control 84 is essentially the scheduling of a page.

The Mark Facility Controller meets various requirements. In particular, the Mark Facility Controller ensures that the document output terminal produces what the operator asked for within the constraints of the DOT. If a jam or other anomaly (e.g. crash) occurs during production then recovery must guarantee that no part of the output is lost or duplicated (e.g. can't lose or duplicate printed checks). The Mark Facility Controller ensures that the document output terminal is driven at rated speed whenever resources (paper, images) are available. This requirement implies that the Mark Facility Controller will control whatever buffering functions are necessary to ensure a steady supply of images to the marking module regardless of peculiarities of page order requirements of specific modules. It further implies that the Mark Facility Controller must be capable of streaming mark job (the job description coming into the Mark Facility Controller) to ensure uninterrupted delivery of prints.

In addition, the Mark Facility Controller must support a common Mark Facility Interface (software interface) for all DOTs; all DOTs are controlled through the same software interface, the Mark Facility interface. The Mark Facility Controller must provide a uniform Machine Module Interface for marking, feeding and finishing for all devices supported by the architecture The Mark Facility Controller must provide information to enable Job Shop Scheduling (a.k.a. work flow management). This includes estimations of "time to complete job". This estimation includes factors like skipped pitches which can be predicted and perhaps those that can be statistically predicted; it does not account for unpredictable skipped pitches (e.g. unexpected jams). The Mark Facility Controller also provides information to its clients to enable load balancing of print jobs across multiple DOTs.

Also, the Mark Facility Controller makes available information about the DOT to Mark Facility clients, including information about the capabilities of the DOT and its current state. The Mark Facility Controller will not have any embedded knowledge about the client(s) of the Mark Facility Interface. That is, there must not be any source dependencies incorporated into a Mark Facility Controller implementation. The Mark Facility Controller architecture has no a prior machine module specific knowledge. In particular, even if the Mark Facility Controller is physically packaged with a Marker Module, the Mark Facility Controller implementation software has no a prior knowledge of the marker module; it is completely independent of the marker module. Further, the underlying technology of the Mark Facility Controller should be machine module independent as well. Note that a particular implementation may be "tuned" or even "preset" for a certain set of configurations in order to decrease resource requirements.

The Mark Facility Controller has no knowledge of the image object content, processing requirements and representation. The Image Loader 82 is responsible for performing image processing and the hard real time buffering, synchronization and transmission of data between the Mark Facility Controller and the Marking Module. Information about the production of a mark job (e.g. skipped pitches, number of impressions, etc.) must be available to clients of the Mark Facility. The Mark Facility Controller insulates clients of the Mark Facility from the timing dependencies of the machine modules. Also, the Mark Facility Controller is capable of job streaming--processing a new mark job while the current mark job(s) is being processed. The intent is to remain productive (i.e. do not "cycle down", minimize skip pitches) during the transition from the current job to the next. The Mark Facility Controller is capable of stream printing, that is, of driving marking, feeding, and finishing modules before the entire assembly tree or all source images have been received.

FIG. 7 is a high level architectural view of the Mark Facility Controller. The control path is shown in solid arrows 112; the image path is shown in dotted arrows 102. The Mark Facility Controller 74 accepts mark job descriptions from a Mark Facility client such as a Print Service or Copy Service. The main component of this job is the assembly tree, which specifies the physical assembly of the document(s) to be produced. The assembly tree definition is independent of the DOT that will produce the job. The assembly tree references images which are stored outside of the Mark Facility Controller. Jobs are queued in the mark job queue 94, and then go to the scheduler 96 to begin execution.

The scheduler understands and models the machine modules in terms of capabilities and constraints which are uploaded into the Mark Facility Controller at power up time and stored in the constraint store 110. The scheduler 96 coordinates the various machine modules (104, 106, 108, (e.g. feeder modules, image path modules, marker modules, finisher modules, and output modules) to produce the job. The scheduler also coordinates the image loader 98 which is viewed by the scheduler as just another machine module (one that happens to feed images rather than paper). The image loader acts as a "flow control" valve, pulling the images out of the image store and transferring them to a marking module at the scheduled time. Note that there are two fairly independent paths--the control path and the image path. These two paths intersect at the image loader.

The Mark Facility Controller accepts mark jobs and other communication from Mark Facility clients and controls the overall operation of the Machine Modules. There is one and only one Mark Facility Controller per configuration of machine modules; a machine module is controlled by exactly one Mark Facility Controller. A configuration of machine modules can have any combination of modules including multiple mark engines (e.g. a color mark engine and a black/white mark engine both feeding into an envelope stuffer), or no mark engine (just feeders feeding directly into finishers).

A key function of the Mark Facility Controller is to translate the configuration-independent and time-independent mark job specification into configuration-dependent and time-dependent actions for the various machine modules and to coordinate their activities. The Mark Facility Controller sees the machine modules as transducers which input and output work units (sheets, images, and compilations) and have constraints on these inputs and outputs. Thus, mark scheduling involves planning and coordinating a timed sequence of matched inputs and outputs (i.e. transfers) between the various machine modules in the configuration. The Machine Modules are responsible for translating timed sequences of inputs and outputs for their module (e.g. accept a sheet at time 3700 and an image at 4200, and output a print at time 8200) into the electrical and mechanical events necessary to accomplish the transductions to which they commit. Note that while machine modules talk to the Mark Facility Controller in terms of absolute time, this does not imply that machine control inside a module must use absolute time. On the contrary, it is anticipated that some machine modules will translate absolute time to machine clocks and base all their timing off machine clocks as has been done traditionally. There exists a mechanism in the Machine Module Interface to keep absolute clocks in sync across machine modules.

The Mark Job Queue 94 holds jobs until they can be produced. Mark Facility clients can promote and demote jobs in the queue for additional flexibility. The Scheduler 96 takes in jobs represented as assembly trees from the job queue, maps them onto the machine modules present, and finds the optimal sequence of operations to produce the job. Note that for scheduling purposes, the Image Loader 98 is coordinated using the same Machine Module Interface as the machine modules. The scheduler then coordinates the machine modules, monitors their progress, and reacts to problems such as jams and determines the optimal recovery strategy.

The machine modules describe themselves in terms of capabilities and constraints on those capabilities (e.g. I can take in sheets and images and put out prints with a maximum throughput of 180 prints per minute). These are uploaded from each machine module into the scheduler where they are combined to form a model of the entire machine. Architecturally, the scheduler requires no prior machine knowledge, and allows for machine modules to upload their capabilities and constraints at power up. However, for a particular product program implementation various optimizations may be made in order to lessen CPU and RAM requirements.

Some mark jobs are not completely provided at the beginning of a job, but rather are streamed in while the job is running. This is called stream printing. The scheduler is responsible for recognizing extensions to the tree as subtree extensions are streamed into it, and pruning the tree as the machine modules indicate that various nodes of the assembly tree have been successfully delivered. There may need to be some kind of bidding functionality. For example, a print shop scheduler (a different scheduler, at a much higher level) might query the Mark Facility Controller as to its ability to render a particular mark job. To validate the job without actually printing it, the bidding function would examine the machine graph (the description of the print machine configuration), validate that it could (or could not) do the job, and if so, submit a estimate of how long it would take, how soon it could start, etc. This would allow the print shop scheduler to perform load balancing or job pre-validation to improve shop productivity. Note that when estimating the time to produce a mark job, the Mark Facility Controller cannot take into account unforeseen circumstances like unexpected paper jams, etc.

While the Image Path is not part of the Mark Facility Controller, the Mark Facility Controller makes assumptions about its operation which are documented here. The Mark Facility Controller treats images as work units to be scheduled (the same as sheets and compilations). The Mark Facility Controller expects modules sourcing images as work units to behave as proper Machine Modules and thus export the Machine Module Interface. Functions such as image buffer control, image processing, and consumption/generation of image formats are outside the scope of the Mark Facility Controller Strategy.

The Mark Facility Controller also needs to support offline finishing. There are two classifications of offline finishing: 1) completely independent stand alone finishers and 2) configurations of feeders and/or finishers. A Mark Facility Controller is not needed in (1). A Mark Facility Controller may be needed in (2). Therefore the Mark Facility Controller must be able to run on a platform suitable to this situation. For example, it may be desirable to have the Mark Facility Controller run on a laptop which can be connected to a configuration of feeders and finishers and coordinate them.

Following the principle that scalability demands that software architecture not imply a particular physical packaging of the software with the hardware, the architecture allows for several alternative packaging. A particular packaging can be chosen to fit the particular needs of a given program as shown in FIG. 8. For example, the Mark Facility Controller 74 may be physically packaged with the document services platform 114 shown as 116 in FIG. 8, or it may be physically packaged with the marker module 118 shown as 120 (either sharing the marker module's CPU or on it's own board) or the entire system may be packaged on a single CPU.

In accordance with the present invention, a system of machine modules is modeled as a collection of transducers which have constraints as shown in FIGS. 9 and 10 that specify their behavior. Scheduling is accomplished by finding a sequence of transfers between the various transducer inputs and outputs that is consistent with the constraints. This is the essence that enables mix-and-match of Markers, Feeders, and Finishers. In particular, machine modules such as feeders, mark engines, and finishers are viewed as black boxes with portals which allow transfer units such as sheets, sets, plates, etc to enter or exit. Modules also have conceptual control signals which is used to specify desired capabilities such as simplex verses duplex, or staple verses bind. Modules export portals and control signals to the scheduler along with constraints. The constraints identify the subspace of signals that can be exhibited by the black-box on its portals. Every solution of the constraints corresponds to a feasible behavior of the black-box and every feasible behavior of the black-box corresponds to a solution of the constraints.

The scheduler creates a graph representing all of the modules. For example, feeders 122, 124, and image loader 126 with specific constraints are connected to either or both of black and white mark engine 128 and color mark engine 130 as illustrated in FIG. 9. Each of the mark engines includes specific constraints relative to a connection to complier/stapler 132 in turn connected to shrink wrapper 134 with associated constraints. Depending upon the interconnection and constraints, certain operations are acceptable and certain operations would fail. This interrelation can be illustrated by interconnected transducers illustrated in FIG. 10. For example, transducer 136 is connected to transducer 148, transducer 136 responding to constraints 138, inputs 140 and control 142 to provide outputs 144 and 146. Output 146 is an input to transducer 148 in turn providing output 154 in response to control 152 and constraint 150.

When a print job is submitted, the scheduler creates a plan by solving the constraints and specifying the identity and times of transfer along the edges of a graph representation of module (the boundaries of the transducers). The machine module descriptions that the scheduler accepts are compositional, i.e. feeder, mark engine, and finisher descriptions can be merged at power-up time to form a single print machine description which can then be scheduled.

Capabilities are a means of describing what a DOT machine module can do such as feed paper, simple mark, staple, etc. Capabilities are described in terms of work units input, work units output, and the relationship between the inputs and the outputs using universally defined keywords. Traditional means of defining what a machine module can do have limited their description to the end outcome (stapled, bound, etc) which is insufficiently detailed to allow mix-and-match of markers, feeders, and finishers.

A capability is expressed on a transducer such as a machine, a machine module, or a component within a machine module. The capabilities defined what the transducer does. The capability identifies which kind of work unit is entering or exiting on which port of the transducer. It defines any constraints on timing of the work units (e.g. minimum 500 milliseconds between entering sheets), on attributes of the work units (e.g. paper size must be less than 17"), etc. It also defines the relationship between the inputs and outputs in terms of work unit properties/finishing changed, added, deleted, etc. for example, the sheet exiting has all the same properties as the sheet entering, except the orientation is changed from face up to face down).

The advantages over traditional methods of describing such data include the following. Traditionally, one simply said that a machine module had a stapler and it stapled, and referred to the DPA keyword STAPLE. However, actual machines differ widely in the physical details of accomplishing this operation. Therefore, by simply saying STAPLE does not provide enough information to determine whether a collection of machine modules can actually produce the job. For example, one machine might receive the set face up, staple and release the set face down. Another machine might do the same but release face up, another might not take sets in but take sheets in, etc. Trying to describe all the different permutations using DPA-styled keywords quickly leads to an explosion of the number of keywords which quickly becomes unmanageable. Breaking the description into inputs, outputs, and the relationship between the inputs and outputs breaks the problem of describing what the machine does into smaller pieces which turn out to be easily manageable.

A Machine Graph, a directed graph data structure, as shown in FIG. 9, is a means of representing a configuration of DOT feeders, markers, and finisher modules. Traditionally, DOT machines were represented only as the sum of their functionality (so many feeders options, so much marking throughput, and so many finishing options) and have never attempted to represent topology. The nodes of the graph represent the machine module; the directed edge represented the paper/set/etc flow between machine modules. Nodes may have multiple ins and outs. By representing the machine as a graph, arbitrary configurations of machine modules can be expressed including modules with merges, forks, parallel paths, etc. Also, the marker-centric paradigm is no longer required configurations can be expressed which have multiple markers or no markers.

In scheduling Document Output Terminals, committing to some capabilities such as marking the front side of a page are interdependent on committing to other capabilities such as marking the back side of the page as well. In the past such interdependencies were handled on an ad hoc basis. However, ad hoc methods generally don't support mix-and-match of arbitrary modules. A generalized concept called the commitment group, any collection of interdependent capability commitment is required. A commitment group is committed if and only if each capability commitment within the group is committed.

To produce a mark job, capabilities are committed through a commit protocol (Propose, Accept/Reject, Confirm/Cancel). If various capabilities are interdependent (e.g. either you mark the front side of a sheet and exactly seven seconds later mark the back side, or you do neither), these capabilities are proposed together as part of the same commitment group. If all capabilities are accepted, the group as a whole is confirmed, otherwise it is cancelled. The commitment group become one of the keys around which much of the coordination of the DOT operation revolves. For example, commitment groups are committed to in a particular order--if one of the groups has to be broken (paper jam, etc), all subsequent groups must be broken and the process of gaining the groups' commitment must begin again from the first broken commitment group.

With any machine configuration is created, the Mark Facility Controller uploads the capabilities and constraints of each of the machine modules and examines the constraints to uncover interdependencies. When a job is submitted and the Mark Facility Controller is coordinating its execution, the Mark Facility Controller identifies the commitment groups be referring to these interdependencies as it prepares to propose the capabilities to produce the job. Commitment Groups provide a generalized scheme for dealing with interdependencies, thus enabling mix-and-match of modules.

With reference to FIG. 11, there is shown a typical generalized distributed job coordinating system including Mark Facility Controller 212, imager 214, marker 216, feeder 218, and finisher 220 interconnected to the controller 212 by communication lines 215, 217, 219 and 221 respectively. Each of the two way communication lines 215, 217, 219, and 221 represents continual request communications with the Controller 212. For example, assume a job description 222 received by the Mark Facility Controller 212 to provide a copy sheet to the finisher 220 from the feeder 218 of an image developed at marker 216. This requires that each of these components operate as required within a given period of time. If one of the components is unable to commit, the overall operation must be aborted or delayed until another time frame when all of the requested components respond with ready or commit responses to the Mark Facility Controller 212.

FIG. 11, illustrates a very simplified version of the concept of a request and commit or veto protocol between the Mark Facility Controller and the various operating components. If all of the components 214, 216, 218, and 220 commit, then the Mark Facility Controller proceeds to confirm the sheet to all components, which in turn proceed to execute the requested operations. As stated above, if at least one of the components is not able to commit, then the Mark Facility Controller will delay operation until all necessary components provide a commit response.

While this invention has been described in conjunction with a specific apparatus, it is evident that many alternatives, modifications, and variations will be apparent to those skilled in the art. Accordingly, it is intended to embrace all such alternatives, modifications, and variations as fall within the spirit and broad scope of the appended claims.