Hi All,<br>
<br>
I am very interested in solving a job shop scheduling problem I have. I must implement the following:<br>
<br>
<pre><span class="slc"></span>
<span class="line"> 22 </span><span class="slc"># Jobs can have an earliest start time (es), or have already started (st)</span>
<span class="line"> 23 </span><span class="slc"># Jobs can be scheduled as a result of forcasted demand or as part of an</span>
<span class="line"> 24 </span><span class="slc"># actual sales order</span>
<span class="line"> 25 </span><span class="slc"># Jobs can have a needed by time (nb)</span>
<span class="line"> 26 </span><span class="slc"># Jobs can have a normal or high priority</span>
<span class="line"> 27 </span><span class="slc"># Jobs can have a different initial startup times on the machines</span>
<span class="line"> 28 </span><span class="slc"># Jobs can have a different post initial startup times on the machines</span>
<span class="line"> 29 </span><span class="slc"># Workcenters can have downtime (sdt, duration of downtime in seconds)</span>
<span class="line"> 30 </span><span class="slc"># Workcenters can have different schedules from each other ex: 6:00 - 17:00,</span>
<span class="line"> 31 </span><span class="slc"># 9:00 - 17:00</span>
<span class="line"> 32 </span><span class="slc">#</span>
<span class="line"> 33 </span><span class="slc"># Alternative workcenters can be used (wc4, alt: wc1, wc2, wc3)</span>
<span class="line"> 34 </span><span class="slc"># workcenter 4 jobs can be done on wc1, or wc2, or wc3</span>
<span class="line"> 35 </span><span class="slc"># Workcenters can have different efficiently rates ex: 80% 120% etc...</span>
<span class="line"> 36 </span><span class="slc">#</span>
<span class="line"> 37 </span><span class="slc"># Hard constraints for the manufacturing resource planning/scheduling:</span>
<span class="line"> 38 </span><span class="slc"># 1. No more then 1 task can be done on any 1 machine at 1 time</span>
<span class="line"> 39 </span><span class="slc"># 2. Dependent jobs must be done before parent jobs</span>
<span class="line"> 40 </span><span class="slc"># 3. No job can be done on a machine when the machine is not available (wc schedule)</span>
<span class="line"> 41 </span><span class="slc"># 4. A job that has started cannot be rescheduled and must finish (can't move job if</span>
<span class="line"> 42 </span><span class="slc"># started)</span>
<span class="line"> 43 </span><span class="slc"># 5. All jobs with a high priority must/should be scheduled before jobs with normal</span>
<span class="line"> 44 </span><span class="slc"># priority (This obviously can be violated if a job has already started and has normal</span>
<span class="line"> 45 </span><span class="slc"># priority, you could end up with a situation where the normal priority job was started</span>
<span class="line"> 46 </span><span class="slc"># before a high priority job)</span>
<span class="line"> 47 </span><span class="slc"># 7. Jobs related to a sales order should be scheduled before those associated</span>
<span class="line"> 48 </span><span class="slc"># with forcasted demand</span>
<span class="line"> 49 </span><span class="slc"># 8. Jobs that have a shorter needed by delta between now and the needed by date should</span>
<span class="line"> 50 </span><span class="slc"># be done before those with no needed by date or a longer delta between now and the</span>
<span class="line"> 51 </span><span class="slc"># needed by date</span>
<span class="line"> 52 </span><span class="slc">#</span>
<span class="line"> 53 </span><span class="slc"># Soft constraints:</span>
<span class="line"> 54 </span><span class="slc"># 1. If a job cannot be completed by the needed by date, the less late it is the better</span>
<span class="line"> 55 </span><span class="slc"># 2. The schedule with the least amount of non work time gaps is superior to others</span>
<span class="line"> 56 </span><span class="slc"># when compared (fitness function)</span>
<span class="line"> 57 </span><span class="slc">#</span>
<span class="line"> 58 </span><span class="slc"># Goal:</span>
<span class="line"> 59 </span><span class="slc"># To create an intelligent mrp scheduler that can schedule 6000 jobs in 30 seconds</span>
<span class="line"> 60 </span><span class="slc"># choosing a suboptimal but close to optimal schedule out of many possible schedules</span>
<span class="line"> 61 </span><span class="slc">#</span>
<span class="line"> 62 </span><span class="slc"># The results are all the jobs with their durations and start times in seconds as an offset</span>
<span class="line"> 63 </span><span class="slc"># from the schedule start date/time. The xmlrpc function scheduleTasks also returns</span>
<span class="line"> 64 </span><span class="slc"># all the close times derived/needed in the scheduling.</span></pre>
<br>
I have attempted a brute force solution to this with perl and it needs
lots of work. If anyone is interested in looking at it please go
to:<br>
<br>
<a href="http://edusmart.cvs.sourceforge.net/edusmart/perlMRPScheduler/">http://edusmart.cvs.sourceforge.net/edusmart/perlMRPScheduler/</a><br>
<br>
The 6000 jobs take well over 30 seconds currently. It is quite
frustrating to say the least. I have been told that a better
approach might be to use a genetic algorithm. What would be ideal
for me is to use a library that at least partially or completely solves
the problem. I really want to avoid re-creating the wheel.
Any help/advice would be greatly appreciated.<br>
<br>
Thanks,<br>
<br>
Tim<br>
<br>
P.S.<br>
<br>
My solution will be GPL'd and opensource and then integrated in
tinyerp. If your interested in a free opensource erp program go
to <a href="http://www.tinyerp.com">www.tinyerp.com</a>.<br>
<br>