[Help-glpk] Help solving a job shop scheduling problem

[William Heath]

Hi All,

I am new to glpk.  I want to solve a job shop scheduling problem.  A formal description of my problem is as follows:

Schedule id:  The id of the schedule (Actually an autoincremented id from a db)
Schedule Start Time:  The date the schedule will begin on
Schedule Finish Time:  The date the schedule will finish on
(Usally 1 year from
the                                                              
schedule start time )
Jobs: job id, duration in seconds, workcenter the job can be done on,(optional dep jobid)
workcenters: The workcenters that are available to be used for the jobs ex: wc1

Jobs can have an earliest start time (es), or have already started (st)
Jobs can be scheduled as a result of forcasted demand or as part of an
actual sales order
Jobs can have a needed by time (nb)
Jobs can have a normal or high priority
Jobs can have a different initial startup times on the machines
Jobs can have a different post initial startup times on the machines
Workcenters can have downtime (sdt, duration of downtime in seconds)
Workcenters can have different schedules from each other ex: 6:00 - 17:00,
9:00 - 17:00

Alternative workcenters can be used (wc4, alt: wc1, wc2, wc3)
workcenter 4 jobs can be done on wc1, or wc2, or wc3
Workcenters can have different efficienty rates ex: 80% 120% etc...

Hard constraints for the manufacturing resource planning/scheduling:
  1.  No more then 1 task can be done on any 1 machine at 1 time
  2.  Dependent jobs must be done before parent jobs
  3.  No job can be done on a machine when the machine is not available (wc schedule)
  4.  A job that has started cannot be rescheduled and must finish (can't move job if started)
  5.  All jobs with a high priority must/should be scheduled
before jobs with normal priority (This obviously can be violated if a
job has already started and has normal priority, you could end up with
a situation where the normal priority job was started before a high
priority job)
  6.  Jobs related to a sales order should be scheduled before those associated with forcasted demand
  7.  Jobs that have a shorter needed by delta between now
and the needed by date should be done before those with no needed by
date or a longer delta between now and the needed by date

Soft constraints:
  1.  If a job cannot be completed by the needed by date, the less late it is the better
  2.  The schedule with the least amount of non work time gaps is superior to others when compared (fitness function)

  Goal:
  To create an intelligent mrp scheduler that can schedule 6000 jobs in 30 seconds
  choosing a suboptimal but close to optimal schedule out of many possible schedules

  The results are all the jobs with their durations and start
times in seconds as an offset from the schedule start date/time. 
The xmlrpc function scheduleTasks also returns all the close times
derived/needed in the scheduling.

I have attempted to solve this problem with a straight forward approach
using perl.  If your interested in looking at this go to:

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

It is unfortunately quite slow and needs work to even begin to solve
the problem well.  It does not even attempt to take into
consideration multiple scheduling possibilities.  I would like to
formulate an AMPL description of my problem, but I have never done
AMPL.  Can anyone help me in any way?  I am very interested
in using free opensource software to solve this problem.  Any
suggestions/comments are very welcome.