• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

any algorithm suggestion?

 
Greenhorn
Posts: 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I am having a resource scheduling problem now.

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?

thanks bros
 
Ranch Hand
Posts: 195
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Have you evaluated Semaphores? You can have very efficient resource-allocation control by using a single Sempahore object to control the resources.

Now coming to your "satisfaction for each order"...this depends upon how much of your code goes through synchronization and how big your run() method of the thread will be.
 
Ranch Hand
Posts: 1646
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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.
 
Ranch Hand
Posts: 82
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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.

Nimo.
 
I can't renounce my name. It's on all my stationery! And hinted in this tiny ad:
a bit of art, as a gift, that will fit in a stocking
https://gardener-gift.com
reply
    Bookmark Topic Watch Topic
  • New Topic