[Coin-discuss] Job shop scheduling advice/help

[William Heath]

Hi All,

I am very interested in solving a job shop scheduling problem I have.  I
must implement the following:

   22 #   Jobs can have an earliest start time (es), or have already
started (st)   23 #   Jobs can be scheduled as a result of forcasted
demand or as part of an   24 #   actual sales order   25 #   Jobs can
have a needed by time (nb)   26 #   Jobs can have a normal or high
priority   27 #   Jobs can have a different initial startup times on
the machines   28 #   Jobs can have a different post initial startup
times on the machines   29 #   Workcenters can have downtime (sdt,
duration of downtime in seconds)   30 #   Workcenters can have
different schedules from each other ex: 6:00 - 17:00,   31 #
                                                     9:00 - 17:00   32
#   33 #         Alternative workcenters can be used (wc4, alt: wc1,
wc2, wc3)   34 #                                     workcenter 4 jobs
can be done on wc1, or wc2, or wc3   35 #         Workcenters can have
different efficiently rates ex: 80% 120% etc...   36 #   37 #  Hard
constraints for the manufacturing resource planning/scheduling:   38 #
 1.  No more then 1 task can be done on any 1 machine at 1 time   39 #
 2.  Dependent jobs must be done before parent jobs   40 #  3.  No job
can be done on a machine when the machine is not available (wc
schedule)   41 #  4.  A job that has started cannot be rescheduled and
must finish (can't move job if   42 #      started)   43 #  5.  All
jobs with a high priority must/should be scheduled before jobs with
normal   44 #      priority (This obviously can be violated if a job
has already started and has normal   45 #      priority, you could end
up with a situation where the normal priority job was started   46 #
   before a high priority job)   47 #  7.  Jobs related to a sales
order should be scheduled before those associated   48 #      with
forcasted demand   49 #  8.  Jobs that have a shorter needed by delta
between now and the needed by date should   50 #      be done before
those with no needed by date or a longer delta between now and the
51 #      needed by date   52 #   53 #  Soft constraints:   54 #  1.
If a job cannot be completed by the needed by date, the less late it
is the better   55 #  2.  The schedule with the least amount of non
work time gaps is superior to others   56 #      when compared
(fitness function)   57 #   58 #  Goal:   59 #  To create an
intelligent mrp scheduler that can schedule 6000 jobs in 30 seconds
60 #  choosing a suboptimal but close to optimal schedule out of many
possible schedules   61 #   62 #  The results are all the jobs with
their durations and start times in seconds as an offset   63 #  from
the schedule start date/time.  The xmlrpc function scheduleTasks also
returns   64 #  all the close times derived/needed in the scheduling.


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:

http://edusmart.cvs.sourceforge.net/edusmart/perlMRPScheduler/

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.

Thanks,

Tim

P.S.

My solution will be GPL'd and opensource and then integrated in tinyerp.  If
your interested in a free opensource erp program go to www.tinyerp.com.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://list.coin-or.org/pipermail/coin-discuss/attachments/20061006/3e9b7fb5/attachment.html>