Use case: flowshop scheduling¶
This example is based on the paper from Tao et al. (2015), where authors present an introduction example. In a flow shop problem, a set of \(n\) jobs has to be processed on \(m\) different machines in the same order. Job \(j\), \(j=1,2,...,n\) is processed on machines \(i\), \(i=1,2,..,m\), with a nonnegative processing time \(p(i,j)\) and a release date \(r_j\), which is the earliest time when the job is permitted to process. Each machine can process at most one job and each job can be handled by at most one machine at any given time. The machine processes the jobs in a first come, first served manner. The goal is to determine a job sequence that minimizes the makespan.
The problem statement is:
The following solution is reported by the authors (order J1, J3, J4, J2, scheduled horizon: 29):
In this notebook, we try to Reference
Tao Ren, Meiting Guo, Lin Lin, Yunhui Miao, “A Local Search Algorithm for the Flow Shop Scheduling Problem with Release Dates”, Discrete Dynamics in Nature and Society, vol. 2015, Article ID 320140, 8 pages, 2015. https://doi.org/10.1155/2015/320140
import processscheduler as ps %config InlineBackend.figure_formats = ['svg']
Create the scheduling problem¶
The total horizon is unknwown, leave it empty and only set the problem name.
flow_shop_problem = ps.SchedulingProblem('FlowShop')
Create the 3 machines M1, M2 and M3¶
M3 = ps.Worker('M3') M2 = ps.Worker('M2') M1 = ps.Worker('M1')
One machine per task.
J11.add_required_resource(M1) J12.add_required_resource(M2) J13.add_required_resource(M3) J21.add_required_resource(M1) J22.add_required_resource(M2) J23.add_required_resource(M3) J31.add_required_resource(M1) J32.add_required_resource(M2) J33.add_required_resource(M3) J41.add_required_resource(M1) J42.add_required_resource(M2) J43.add_required_resource(M3)
Constraint: release dates¶
r1 = 0 r2 = 9 r3 = 2 r4 = 7 ps.TaskStartAfterLax(J11, r1) ps.TaskStartAfterLax(J12, r1) ps.TaskStartAfterLax(J13, r1) ps.TaskStartAfterLax(J21, r2) ps.TaskStartAfterLax(J22, r2) ps.TaskStartAfterLax(J23, r2) ps.TaskStartAfterLax(J31, r3) ps.TaskStartAfterLax(J32, r3) ps.TaskStartAfterLax(J33, r3) ps.TaskStartAfterLax(J41, r4) ps.TaskStartAfterLax(J42, r4) ps.TaskStartAfterLax(J43, r4)
TaskStartAfterLax_326322d3(<class 'processscheduler.task_constraint.TaskStartAfterLax'>) 1 assertion(s): J43_start >= 7
All jobs should be scheduled in the same ordre on each machine. The constraint is expressed as following: all J2 tasks must be scheduled before Or after J2 tasks, AND all J3 tasks must be scheduled before OR oafter J1 tasks etc.
J1 = [J11, J12, J13] J2 = [J21, J22, J23] J3 = [J31, J32, J33] J4 = [J41, J42, J43] # we need to combinations function of the itertools module, # to compute all pairs from the list of jobs. from itertools import combinations for Ja, Jb in combinations([J1, J2, J3, J4], 2): befores =  afters =  for i in range(3): Ja_before_Jb = ps.TaskPrecedence(Ja[i], Jb[i]) Ja_after_Jb = ps.TaskPrecedence(Jb[i], Ja[i]) befores.append(Ja_before_Jb) afters.append(Ja_after_Jb) xor_operation = ps.xor_([ps.and_(befores), ps.and_(afters)]) flow_shop_problem.add_constraint(xor_operation)
Add makespan objective¶
makespan_obj = flow_shop_problem.add_objective_makespan()
Solution, plot the schedule¶
solver = ps.SchedulingSolver(flow_shop_problem) solution = solver.solve() solution.render_gantt_matplotlib(fig_size=(10,5), render_mode='Resource')
Solver type: =========== -> Standard SAT/SMT solver Incremental optimizer: ====================== Found value: 28 elapsed time:0.007s Checking better value <28 Found value: 22 elapsed time:0.007s Checking better value <22 Found value: 21 elapsed time:0.008s Checking better value <21 No solution can be found for problem FlowShop. Reason: Unsatisfiable problem: no solution exists Found optimum 21. Stopping iteration. total number of iterations: 4 value: 21 FlowShop satisfiability checked in 0.01s
Matplotlib is building the font cache; this may take a moment.
We confirm the job sort from Tao et al. (2015) (J1 then J3, J4 and finally J2). The horizon is here only 21.