Using max-plus to solve the job shop problem with time lags

We consider a job shop problem with minimum and maximum time lags (JSPTL). The scheduling method is based on potential inequalities and disjunctive constraints, that are formulated in the max-plus algebra, in terms of inequalities. The computation of the eigenvalue of the corresponding matrices provides bounds, and a feasibility test that is used in a branch-and- bound procedure that permits to solve the problem. Effective computations make use of the max-plus Scicoslab toolbox, and its implementation of the Howard algorithm. One can evaluate whether or not a solution exists to the problem, compute one solution, or compute the set of solutions minimizing the completion time. The method is applied to two case studies from the literature, which permit to point out its advantages and drawbacks.