Autonomous decision-making in print job redirection

• US 20070146772A1
• Filed: 12/27/2005
• Published: 06/28/2007
• Est. Priority Date: 12/27/2005
• Status: Active Grant

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Castellani, Stefania
• Granted Patent: US 7,804,611 B2
• Time in Patent Office: Days
• US Class Current: 358/1.150
• 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 associated with a negotiator, 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, and

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

conducting at least one negotiation for the redirection of at least a portion of the print job between a first negotiator associated with a first printer of the plurality of printers and at least 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 at least a portion of the print job for the first negotiator, the outsource request including parameters of the print job expressed in a negotiation protocol;

communicating the outsource request from the first negotiator to the other negotiator;

where the print job meets insourcing conditions, communicating a print job insource offer for execution of at least a portion of the 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;

optionally, where the communicated insource offer is for only a portion of the print job, formulating a modified outsourcing request which takes into account the insource offer for the portion of the print job;

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, wherein the forming an agreement includes forming a plurality of agreements for execution of the print job.

3. The method of claim 2, further comprising;

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

4. 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.

5. The method of claim 1, further comprising at least one of:

a) where no insource offers which are responsive to a first outsource request for a print job are received in a predetermined time period, modifying the outsource request to allow the print job to be split and communicating the modified outsource request from the first negotiator to at least the other negotiator; and

b) where more than one insource offer which is responsive to an outsource request for the whole 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.

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

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

8. The method of claim 5, 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.

9. 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.

10. 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 outsource 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.

11. 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.

12. 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.

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

14. The method of claim 13, 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.

15. The method of claim 1, further comprising:

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

16. 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.

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, the first negotiator applying constraints to select one of the agreements.

18. 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.

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

27. A printing system comprising the negotiation apparatus of claim 19, and further comprising a plurality of printers, each of the printers being associated with a negotiation processor.

20. A negotiation apparatus comprising:

a negotiator associated with a printer, which communicates with other negotiators, each associated with a respective printer, each of the printers being capable of executing print jobs, the negotiator comprising;

memory for storing information on a plurality of ongoing negotiations, each of the ongoing negotiations comprising an outsource request and at least one insource offer from another of the negotiators, which is at least partially responsive to the outsource request;

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

(a) generating an outsource request for a print job to be outsourced, expressed in the negotiation protocol, the outsource request including parameters of the print job;

(b) communicating the outsource request to at least one other of the negotiators;

(c) receiving an insource offer from another negotiator, expressed in the negotiation protocol, the insource offer being at least partially responsive to an outsource request; and

(d) identifying at least one of an insource offer and a combination of insource offers which satisfies the outsource request.

21. The apparatus of claim 20, wherein the processor executes processing instructions for merging insource offers from a plurality of the other negotiators where the insource offers are only partially responsive to an outsource request.

22. The apparatus of claim 20, further comprising constraint services utilized by the processor which ensure that constraints associated with an outsource request are met, each of the constraint services applying a different set of constraints, comprising:

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

an include service which ensures that inclusion dependencies between a sub-job and the print job are respected, and

an equal service which ensures that equivalence dependencies between jobs are respected.

23. The negotiation apparatus of claim 20, wherein the processor executes processing instructions for carrying out a negotiation in which the negotiator seeks to insource a print job, the processor in executing the processing instructions:

generating an insource offer for a print job, expressed in the negotiation protocol, the insource offer being at least partially responsive to an outsource request from another negotiator.

24. The negotiation apparatus of claim 20, further comprising a plurality of negotiators.

25. The negotiation apparatus of claim 24, further comprising a coordinator which coordinates negotiations between the negotiators.

26. The negotiation apparatus of claim 24, wherein each of the negotiators further comprises memory for storing a plurality of ongoing negotiations, each of the ongoing negotiations comprising an outsource request from another negotiator and an insource offer generated by the second processor, which is at least partially responsive to the outsource request.

28. A printing system comprising:

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

a 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, when a first of the printers receives a print job with parameters which the first printer cannot execute, its negotiator seeks to outsource the print job, by communicating an outsource request which includes parameters of the print job to at least a second of the negotiators of the other printers, the parameters of the print job being expressed in a negotiation protocol, the at least a second negotiator which receives the outsource request including 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 and where the second negotiator determines to make the offer, the second negotiator communicating an insource offer for the at least a portion of the print job to the first negotiator, expressed in the negotiation protocol, the negotiators each being configured for entering a plurality of negotiations for a particular print job to be outsourced and for entering a plurality of negotiations for different print jobs to be insourced.

29. An article of manufacture to be communicatively linked with a printer, the article comprising:

a negotiation processor comprising processing instructions for performing a negotiation with negotiation processors associated with other printers, the processing instructions comprising;

instructions for outsourcing print jobs including;

instructions for generating an outsource request for a print job to be outsourced, the outsource request including parameters of the print job,

instructions for communicating the outsource request to other negotiation processors,

instructions for forming an agreement with a second processor which communicates an insourcing request which is at least partially responsive to the outsource request,

instructions for generating a modified outsource request when the second negotiation processor which communicates an insource offer communicates an insource offer which is only partially responsive to an outsource request, and

instructions for redirecting the print job to at least one other printer, for which an agreement has been formed with the associated negotiation processor;

instructions for insourcing print jobs including;

instructions for generating an insource offer for a print job to be insourced, the insource offer being at least partially responsive to an outsource request from another processor, and

instructions for communicating the insource offer to the processor communicating the outsource request.