Say we have an open shop scheduling problem with following constraints :

  • No wait-time between operations of a job
  • Multiple job types (meaning each job type has different set of operations eventhough their intersection might not be empty)
  • No wait-time between each operation on the same machine (machine must not be idle from the moment it has taken an operation until it has finished all its tasks)
  • Some machines have multiple instances say $k_i$ instances (so the constraint that no machine can process multiple job at the same time is transformed to cannot process more than $k_i$ jobs at the same time)
  • The operations are partially ordered (making it close to a flow shop problem but the order is only partial meaning that some operations must happen before or after others but some can happen in any order)

The classical objective is to maximise makespan but here what I would like to know is the maximum number of each type of jobs (with respect to a known distribution of the types) I could pack inside a given time frame.

What would be the algorithms/paradigms you suggest ? I'm going for constraint programming (OR-tools more precisely) but I'm not finding any alternative, is there any (proprietary software as a black box algorithm not excluded) ?

Additionnal informations : the number of machines is small but not 2 (~10) and the number of jobs is depending on the time frame but can be reasonably estimated to 10-100.

  • $\begingroup$ A small example would be nice to clearly understand all the problem features. $\endgroup$ – Vince Apr 5 at 12:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.