I have 5 trucks and coming new job orders, and I need to make a autorunning program that can automatically check the status of truck and assign coming new jobs to it.
the problem is that not only I need to balance the service time of each truck, but also I have to maximize the satisfaction of the job orders. here, each job has different service time, some can be finished in short time, but some can not.
if I serve the job by using First come first serve, then for those jobs queuing after a long service time required job will have to wait for a long time then can be proceeded.
if I just skip this long service time required job, I can impove my satisfaction rate. But I don't know where to add this job in or when to serve it?
any experts here got any eperience on this resoure scheduling problem? or is it possible that I can find some similar source code that I can learn from it?
If I understand correctly, you may have two jobs waiting to be processed. One takes 1 hour, the other 5 hours, and only one truck available. You'd like to process the 1 hour one before the 5 hour one to maximize satisfaction rate, correct?
This sounds very similar to the "bin packing" problem. You have different sized items to back into different sized bins, and you want to maximize the number of items that you can pack into the fewest number of bins. In this case, you can pack multiple items into the same bin if they'll fit (two items, size 1 and 3, into a size 5 bin, leaving 1 "slot" left over).
I'd recommend googling for "bin packing" and other related terms to narrow your search. Your needs are different since there's the time element: multiple jobs arriving over a time period rather than all jobs available up front. But it does sound close.
I think you should look at aging algorithms. In short - what you do is you give each job a grade, made up from the time it needs, and the cycles it was 'skipped' (i.e. - other jobs where scheduled, while it was in the system). using this grade, you order your waiting-jobs-queue, and whenever a truck comes in - you need to give it the first elligible waiting job from that queue.
pie. tiny ad:
Building a Better World in your Backyard by Paul Wheaton and Shawn Klassen-Koop