Method for redirecting a print job, negotiation apparatus, printing system, and article of manufacture

• US 7,804,611 B2
• Filed: 12/27/2005
• Issued: 09/28/2010
• Est. Priority Date: 12/27/2005
• Status: Expired due to Fees

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Castellani, Stefania
• Primary Examiner(s): Tieu; Benny Q
• Assistant Examiner(s): Bryar; Jeremiah A
• Application Number:
  US11/318,745
• Publication Number:
  US 20070146772A1
• Time in Patent Office: 1,736 Days
• Field of Search: 358/1.1, 358/1.2, 358/1.12, 358/1.14, 358/1.15
• US Class Current: 358/1.15
• CPC Class Codes: G06F 3/1208 resulting in improved quality of the output result, e.g. print layout, colours, workflows, print preview
• CPC Class Codes: G06F 3/1255 Settings incompatibility, e.g. constraints, user requirements vs. device capabilities
• CPC Class Codes: G06F 3/1261 by using alternate printing
• CPC Class Codes: G06F 3/1288 in client-server-printer device configuration
• CPC Class Codes: G06K 15/02 using printers
• CPC Class Codes: G06K 15/1859 involving data processing distributed amongst different data processing apparatus

Abstract

A printing system includes printers capable of redirecting print jobs to one another. A negotiator associated with each printer negotiates print job redirections. If a printer is unable to execute a print job, the negotiator seeks to outsource the print job by communicating an outsource request to other negotiators. In formulating an outsource request, the negotiator utilizes one or more constraint services. A negotiator which receives the outsource request includes an insource mechanism which determines whether to make an offer in which the associated printer is to execute at least a portion of the print job to be outsourced. If negotiator determines to make the offer, the insource offer is communicated to the first negotiator. The negotiators may each contemporaneously conduct a plurality of negotiations for a particular print job to be outsourced and/or contemporaneously conduct a plurality of negotiations for different print jobs to be insourced.

Claims

1. A method for redirecting a print job comprising:

providing a network comprising a plurality of printers, each printer being independently capable of executing print jobs by printing on print media, each printer being associated with a negotiator operating on one or more computational machines, the negotiators each being configured for utilizing constraint services which ensure that constraints associated with an outsource request are met, each of the constraint services applying a different set of constraints, the constraint services comprising;

a split service which ensures that if the print job is split into sub-jobs, the print job is an exact composition of the sub-jobs,

an include service which enables an offer to be made by another negotiator for a portion of the print job prior to the job being split, and

an equal service which ensures that a print job is outsourced as a whole;

with a computer processor, conducting at least one negotiation for the redirection of the print job between a first negotiator associated with a first printer of the plurality of printers and at least one another negotiator associated with another of the plurality of printers, including;

utilizing at least one of the constraint services to formulate an outsourcing request for execution of the entire print job for the first negotiator, the outsource request including parameters of the print job expressed in a negotiation protocol;

communicating the outsourcing request from the first negotiator to the at least one other negotiator;

where the entire print job meets insourcing conditions, communicating a print job insource offer for execution of the entire print job to the first negotiator from the other negotiator, expressed in the negotiation protocol, whereby an agreement is formed between the first negotiator and the other negotiator;

where a portion of the print job which is less than the entire print job meets insourcing conditions, communicating a print job insource offer for execution of the print job portion to the first negotiator from the other negotiator, expressed in the negotiation protocol, in response to the outsourcing request;

where the communicated insource offer is for only a portion of the print job, which is less than the entire print job, with the include service, ensuring that the insource offer meets constraints for being a sub-job of the print job;

where no print job insource offer for execution of the entire print job is communicated to the first negotiator from the at least one other negotiator within a predetermined time period, modifying the outsourcing request to offer a split of the print job and communicating the modified outsourcing request from the first negotiator to at least one other negotiator, which takes into account the insource offer for the portion of the print job which was received in response to the outsourcing request, thereby enabling agreements to be made with the at least one other negotiator for sub-jobs of the job; and

redirecting the print job to at least one other printer of the plurality of printers with which an agreement has been made through negotiation between its negotiator and the first negotiator.

2. The method of claim 1, further comprising:

providing a user with a plurality of print job execution solutions, each of the solutions corresponding to at least one of a plurality of agreements.

3. The method of claim 1, wherein the insourcing conditions are derived from one or more of:

the parameters of the job;

capabilities of the associated printer;

a status of the associated printer'"'"'s print job queue;

a status of one or more other ongoing negotiations; and

local usage policies.

4. The method of claim 1, further comprising:

where more than one insource offer which is responsive to an outsourcing request for the entire print job are received in a predetermined time period, selecting one of the responses by at least one of;

optimizing a utility function; and

querying a user.

5. The method of claim 4, wherein the predetermined time period is a function of a deadline parameter of the print job.

6. The method of claim 4, wherein the modified outsourcing request permits a split of the print job between at least two of the plurality of printers and wherein the modified outsourcing request is communicated to other negotiators.

7. The method of claim 4, further comprising:

merging a first insource offer for a first portion of the print job from a first of the other negotiators with a first negotiation alternative containing a second insource offer for a portion of the print job from a second of the other negotiators; and

merging the first insource with a second negotiation alternative containing a third insource offer for a portion of the print job from a third of the other negotiators.

8. The method of claim 1, wherein at least one of the parameters of the print job is selected from the group consisting of:

a location of the printer which executes at least a portion of the print job;

a deadline for completion of the print job;

a total number of pages in the print job;

a maximum cost per page; and

combinations thereof.

9. The method of claim 1 wherein where a print job is split into sub-jobs, each sub-job being executed by a different printer, the modified outsourcing request further includes constraints selected from the group consisting of:

a total job size equals the sum of a size of each sub-job;

a total job costs equals the sum of a cost of each sub-job;

a deadline for completion of a sub-job does not exceed a deadline for completion of the job;

a minimum size of a sub-job;

locations of the printers which executes the sub-job; and

combinations thereof.

10. The method of claim 1, wherein the include service applies constraints selected from the group consisting of:

a size of an insource job offer is less than or equal to a size of the print job;

a deadline of an insource job offer is prior to or equal to a deadline of the print job;

a cost of an insource job offer is less than or equal to a cost of the print job; and

a printer location of an insource job offer source is the printer location of the job source.

11. The method of claim 1, wherein the equal service applies constraints selected from the group consisting of:

a size of an insource job offer is equal to a size of the print job;

a deadline of an insource job offer is equal to a deadline of the print job;

a cost of an insource job offer is equal to a cost of the print job; and

a printer location of an insource job offer source is the printer location of the job source.

12. The method of claim 1, further comprising storing information on the at least one negotiation in memory accessible to the first negotiator.

13. The method of claim 12, further comprising at least one of:

storing information on negotiations with a plurality of other negotiators in memory accessible to the first negotiator and wherein each of the other negotiators has access to at least a portion of the information; and

storing information on a plurality of print job negotiations, for which the other negotiator has communicated insource offers, in memory accessible to at least the other negotiator.

14. The method of claim 1, further comprising:

utilizing an allocate service for identifying printers which are priority candidates for insourcing.

15. The method of claim 1, further comprising:

allocating a time slot to at least a portion of a print job for which the other negotiator makes an offer; and

permitting multiple print jobs for which offers have been made by the other negotiator to be assigned to the same time slot.

16. The method of claim 1, further comprising:

where more than one agreement has been made for at least a portion of the print job, the first negotiator applying constraints to select one of the agreements.

17. The method of claim 1, further comprising:

where more than one agreement has been made for at least a portion of the print job, providing a user with alternative solutions for execution of the print job.

18. The method of claim 1, further comprising, executing the print job on the at least one printer to which the print job is redirected.

19. The method of claim 1, wherein the predetermined time period is a function of a deadline parameter of the print job.

20. A negotiation apparatus comprising:

a negotiator associated with a printer, the negotiator being capable of communicating with other negotiators, each associated with a respective printer in a network linking the printers, the negotiator being capable of negotiating a redirection of a print job from its associated printer to another of the printers, wherein the negotiator is configured for utilizing constraint services which ensure that constraints associated with an outsource request are met, each of the constraint services applying a different set of constraints, the constraint services comprising;

a split service which ensures that if the print job is split into sub-jobs, the print job is an exact composition of the sub-jobs,

an include service which enables an offer to be made by another negotiator for a portion of the print job prior to the job being split, and

an equal service which ensures that a print job is outsourced as a whole;

the negotiator comprising;

a memory storage device for storing information on a plurality of ongoing negotiations;

a processor, in communication with the memory storage device, which executes processing instructions for carrying out a negotiation in which a first negotiator seeks to outsource a print job, the instructions including instructions for;

when serving as the first negotiator, utilizing at least one of the constraint services to formulate an outsourcing request for execution of the entire print job, the outsource request including parameters of the print job expressed in a negotiation protocol and communicating the outsourcing request to at least one other negotiator;

when serving as one of the other negotiators, where the entire print job meets insourcing conditions, communicating a print job insource offer for execution of the entire print job to the first negotiator, expressed in the negotiation protocol, whereby an agreement is formed between the first negotiator and the other negotiator;

when serving as the one of the other negotiators, where a portion of the print job which is less than the entire print job meets insourcing conditions, communicating a print job insource offer for execution of the print job portion to the first negotiator, expressed in the negotiation protocol, in response to the outsourcing request;

when serving as the first negotiator, where the communicated insource offer is for only a portion of the print job, which is less than the entire print job, with the include service, ensuring that the insource offer meets constraints for being a sub-job of the print job; and

when serving as the first negotiator, where no print job insource offer for execution of the entire print job is communicated from the at least one other negotiator within a predetermined time period, modifying the outsourcing request to offer a split of the print job and communicating the modified outsourcing request from the first negotiator to at least one other negotiator, which takes into account the insource offer for the portion of the print job which was received in response to the outsourcing request, thereby enabling agreements to be made with the at least one other negotiator for sub-jobs of the job and redirection of the print job to at least one other printer of the plurality of printers with which an agreement has been made through negotiation with its negotiator.

21. A printing system comprising:

a plurality of printers which execute print jobs by printing on print media, the printers being capable of redirecting print jobs to other printers of the plurality of printers;

a respective negotiator associated with each of the printers capable of negotiating a redirection of a print job from its associated printer to another of the printers, wherein the negotiators are configured for utilizing constraint services which ensure that constraints associated with an outsource request are met, each of the constraint services applying a different set of constraints, the constraint services comprising;

a split service which ensures that if the print job is split into sub-jobs, the print job is an exact composition of the sub-jobs,

an include service which enables an offer to be made by another negotiator for a portion of the print job prior to the job being split, and

an equal service which ensures that a print job is outsourced as a whole;

the negotiators including memory storing instructions and a processor for executing the instructions, the instructions including instructions for;

when serving as a first negotiator, utilizing at least one of the constraint services to formulate an outsourcing request for execution of the entire print job, the outsource request including parameters of the print job expressed in a negotiation protocol, and communicating the outsourcing request to at least one other negotiator;

when serving as one of the at least one other negotiators, where the entire print job meets insourcing conditions, communicating a print job insource offer for execution of the entire print job to the first negotiator, expressed in the negotiation protocol, whereby an agreement is formed between the first negotiator and the other negotiator;

when serving as the one of the at least one other negotiators, where a portion of the print job which is less than the entire print job meets insourcing conditions, communicating a print job insource offer for execution of the print job portion to the first negotiator, expressed in the negotiation protocol, in response to the outsourcing request;

when serving as the first negotiator, where the communicated insource offer is for only a portion of the print job, which is less than the entire print job, with the include service, ensuring that the insource offer meets constraints for being a sub-job of the print job;

when serving as the first negotiator, where no print job insource offer for execution of the entire print job is communicated from the at least one other negotiator within a predetermined time period, modifying the outsourcing request to offer a split of the print job and communicating the modified outsourcing request from the first negotiator to at least one other negotiator, which takes into account the insource offer for the portion of the print job which was received in response to the outsourcing request, thereby enabling agreements to be made with the at least one other negotiator for sub-jobs of the job and redirection of the print job to at least one other printer of the plurality of printers with which an agreement has been made through negotiation with its negotiator.

22. A non-transitory article of manufacture, the article comprising a computer readable medium which stores instructions for conducting at least one negotiation for the redirection of a print job between a first negotiator associated with a first printer of a plurality of printers and at least one other negotiator associated with another of the plurality of printers, the negotiators each being configured for utilizing constraint services which ensure that constraints associated with an outsource request are met, each of the constraint services applying a different set of constraints, the constraint services comprising:

a split service which ensures that if the print job is split into sub-jobs, the print job is an exact composition of the sub-jobs,

an include service which enables an offer to be made by another negotiator for a portion of the print job prior to the job being split, and

an equal service which ensures that a print job is outsourced as a whole;

the instructions including instructions for;

utilizing at least one of the constraint services to formulate an outsourcing request for execution of the entire print job for the first negotiator, the outsource request including parameters of the print job expressed in a negotiation protocol;

communicating the outsourcing request from the first negotiator to the at least one other negotiator;

where the entire print job meets insourcing conditions, communicating a print job insource offer for execution of the entire print job to the first negotiator from the other negotiator, expressed in the negotiation protocol, whereby an agreement is formed between the first negotiator and the other negotiator;

where a portion of the print job which is less than the entire print job meets insourcing conditions, communicating a print job insource offer for execution of the print job portion to the first negotiator from the other negotiator, expressed in the negotiation protocol, in response to the outsourcing request;

where the communicated insource offer is for only a portion of the print job, which is less than the entire print job, with the include service, ensuring that the insource offer meets constraints for being a sub-job of the print job;

where no print job insource offer for execution of the entire print job is communicated to the first negotiator from the at least one other negotiator within a predetermined time period, modifying the outsourcing request to offer a split of the print job and communicating the modified outsourcing request from the first negotiator to at least one other negotiator, which takes into account the insource offer for the portion of the print job which was received in response to the outsourcing request, thereby enabling agreements to be made with the at least one other negotiator for sub-jobs of the job and redirection of the print job to at least one other printer of the plurality of printers with which an agreement has been made through negotiation between its negotiator and the first negotiator.