Say you have an office with 3 printers, all execute print jobs at exactly the same speed. Say you have a fixed order size of:

  • 20 single page reports which take 10 seconds each
  • 15 paper packets which take 100 seconds each
  • 2 full-page images which take 40 seconds each

How would you distribute jobs among printers such that total printing time is minimized?

Now if you boost 1 of the printers to cut the processing time of each job of that printer in half. How would you distribute the print jobs now?

I feel like this is something I've came across before but I just can't think of it. How would you even begin?

  • The first part, where each job has a predefined size (time) and moving a job across printers doesn't affect its time, is a variation of bin packing problem. – rwong Jun 13 '15 at 23:06
  • okay, and if one of the printers has its efficiency increased by 100%... for that particular case you could treat it as 2 bins and theoretically combine both piles into one effectively answering that question. Thanks! – user3716714 Jun 13 '15 at 23:33
  • Here is the bad news from @rwong's link: "it is a combinatorial NP-hard problem." The long and short of it is this problem will likely be expressed as an exhaustive search in exponential time. – user22815 Jun 14 '15 at 9:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.