Dears
I look for algorithms that resolve a sequencing problem (we need to minimize Cmax) with the following conditions:
1. m similar machines, when each one has a different capacity Ci
2. n job, when each one has a different process time Tj and a different priority Pj
Any contribution or suggestion is more than welcome.
Cmax mean the time when the laste job leave the the last machine.
for m it could be from 4 to 9. for n it could be from 10 to 100
Yes, it's the most important thing, because the n jobs don't have the same priority
Please find attached a graphical explanation of a possible algorithm and the 2 works “Analysis and Synthesis of engineering systems” and "The Integrations of Variables method". 14th example of the 1st work must be of great help for you, the 2nd one must provide you the theorical basis. I am waiting for your answer.
Hi Charif,
The attached two papers may be of interest to you. Although not exactly the same as the problem you are trying to solve, they do include sequencing, multi-objective optimization, m robots (you can think of them as machines) with different capacity and processing/coverage time, etc.
Hope they help.
Conference Paper An approach to base placement for effective collaboration of...
Conference Paper Task oriented area partitioning and allocation for optimal o...
Tricky one, this, as there are thousands of papers out there on machine scheduling problems. It might be best to start with a good book, such as:
http://faculty.tuck.dartmouth.edu/principles-sequencing-scheduling/
https://www.amazon.co.uk/Theory-Sequencing-Scheduling-L-Lawler/dp/0471905496
http://dl.acm.org/citation.cfm?id=1882743
There are a lot of works devoted to machine scheduling problems, but the algorithm I proposed for Charif problem must to be very effective, by the reason it was very useful solving a mathematically similar, but easier, previously resolved problem, that even requires of a complex geometric treatment in each iteration
Best wishes to all and every follower,
Jose
Excuse for my English, I tried to say: ... it was very useful solving a mathematically similar, but much more complex, previously solved problem ...
Hi Charif
Suppose a machine with Ci>1. Is it possible loading a job to this machine while that is processing the other job? If yes, so you can suppose that you have M=sum (Ci) different machines with same speed. Cannot you?
Now, you order the jobs in their priority in one list. Then suppose M sub lists and allocate the jobs to them. Try to have same size sub lists (by size, I mean sum (Pj)). Now allocate Ck sub lists to machine with Ck capacity.
Even this algorithm in not the same you want, but this approach can be useful.
- Badges
- Science topic
- Similar topics
- Computer Science and Engineering
- Algorithms