\myheading{Job Shop Scheduling/Problem}
\label{JobShop}

\leveldown{}

\renewcommand{\CURPATH}{other/job_shop}

You have number of machines and number of jobs.
Each jobs consists of tasks, each task is to be processed on a machine, in specific order.

Probably, this can be a restaurant, each dish is a job.
However, a dish is to be cooked in a multi-stage process, and each stage/task require specific kitchen appliance and/or chef.
Each appliance/chef at each moment can be busy with only one single task.

The problem is to schedule all jobs/tasks so that they will finish as soon as possible.

See also:
\url{https://en.wikipedia.org/wiki/Job_shop_scheduling},
\url{https://developers.google.com/optimization/scheduling/job_shop}.

\myheading{My first version}

\lstinputlisting[style=custompy]{\CURPATH/job.py}

( Syntax-highlighted version: \url{\RepoURL/\CURPATH/job.py} )

The solution for the 3*3 (3 jobs and 3 machines) problem:

\lstinputlisting{\CURPATH/r1.txt}

It takes ~20s on my venerable Intel Xeon E3-1220 3.10GHz to solve 10*10 (10 jobs and 10 machines) problem from 
\href{http://support.sas.com/documentation/cdl/en/orcpug/63973/HTML/default/viewer.htm#orcpug_clp_sect048.htm}{sas.com}:
\url{\RepoURL/\CURPATH/r2.txt}.

Further work: makespan can be decreased gradually, or maybe binary search can be used...

\myheading{MaxSMT version by Chad Brewbaker}

\lstinputlisting[caption=Diff]{\CURPATH/job_fix.patch}

( Full source-code: \url{\RepoURL/\CURPATH/job_fix.py} )

Works faster, but using MaxSMT.

% FIXME: чё тут было-то? забыл.
% See also: \url{https://github.com/DennisYurichev/yurichev.com/pull/2}.

\levelup{}