dwave.optimization.generators.job_shop_scheduling#

job_shop_scheduling(times: _SupportsArray[dtype[Any]] | _NestedSequence[_SupportsArray[dtype[Any]]] | bool | int | float | complex | str | bytes | _NestedSequence[bool | int | float | complex | str | bytes], machines: _SupportsArray[dtype[Any]] | _NestedSequence[_SupportsArray[dtype[Any]]] | bool | int | float | complex | str | bytes | _NestedSequence[bool | int | float | complex | str | bytes], *, upper_bound: int | None = None) Model[source]#

Generate a model encoding a job-shop scheduling problem.

Job-shop scheduling has many variant. Here, what we have implemented is a variant of job-shop scheduling with the additional assumption that every job makes use of every machine.

E. Taillard provides benchmark instances compatible with this generator.

The model generated is based on the one proposed in L. Blaise, “Modélisation et résolution de problèmes d’ordonnancement au sein du solveur d’optimisation mathématique LocalSolver”, Université de Toulouse, https://hal-lirmm.ccsd.cnrs.fr/LAAS-ROC/tel-03923149v2

Note

There are many ways to model job-shop scheduling. The model returned by this function may or may not give the best performance for your problem.

Parameters:
  • times – An n jobs by m machines array-like where times[n, m] is the processing time of job n on machine m.

  • machines – An n jobs by m machines array-like where machines[n, :] is the order of machines that job n will be processed on.

  • upper_bound – An upper bound on the makespan. If not given, defaults to times.sum(). Note that if the upper_bound is too small the model may be infeasible.

Returns:

A model encoding the job-shop scheduling problem.