{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Use case: flowshop scheduling\n", "\n", "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.\n", "\n", "The problem statement is:\n", "\"problem\n", "\n", "The following solution is reported by the authors (order J1, J3, J4, J2, scheduled horizon: 29):\n", "\"gantt\n", "\n", "In this notebook, we try to reproduce the results reported by the authors.\n", "\n", "**Reference**\n", "\n", "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" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Imports" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "import processscheduler as ps\n", "\n", "%config InlineBackend.figure_formats = ['svg']" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Create the scheduling problem\n", "The total horizon is unknwown, leave it empty and only set the problem name." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "flow_shop_problem = ps.SchedulingProblem(\"FlowShop\")" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Create the 3 machines M1, M2 and M3" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "M3 = ps.Worker(\"M3\")\n", "M2 = ps.Worker(\"M2\")\n", "M1 = ps.Worker(\"M1\")" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Create jobs J1, J2, J3 and J4 - related tasks" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "# J1\n", "J11 = ps.FixedDurationTask(\"J11\", duration=2)\n", "J12 = ps.FixedDurationTask(\"J12\", duration=5)\n", "J13 = ps.FixedDurationTask(\"J13\", duration=6)\n", "\n", "# J2\n", "J21 = ps.FixedDurationTask(\"J21\", duration=1)\n", "J22 = ps.FixedDurationTask(\"J22\", duration=5)\n", "J23 = ps.FixedDurationTask(\"J23\", duration=7)\n", "\n", "# J3\n", "J31 = ps.FixedDurationTask(\"J31\", duration=1)\n", "J32 = ps.FixedDurationTask(\"J32\", duration=4)\n", "J33 = ps.FixedDurationTask(\"J33\", duration=1)\n", "\n", "# J4\n", "J41 = ps.FixedDurationTask(\"J41\", duration=3)\n", "J42 = ps.FixedDurationTask(\"J42\", duration=4)\n", "J43 = ps.FixedDurationTask(\"J43\", duration=7)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Assign resources\n", "One machine per task." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "J11.add_required_resource(M1)\n", "J12.add_required_resource(M2)\n", "J13.add_required_resource(M3)\n", "\n", "J21.add_required_resource(M1)\n", "J22.add_required_resource(M2)\n", "J23.add_required_resource(M3)\n", "\n", "J31.add_required_resource(M1)\n", "J32.add_required_resource(M2)\n", "J33.add_required_resource(M3)\n", "\n", "J41.add_required_resource(M1)\n", "J42.add_required_resource(M2)\n", "J43.add_required_resource(M3)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Constraint: release dates" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "r1 = 0\n", "r2 = 9\n", "r3 = 2\n", "r4 = 7\n", "\n", "ps.TaskStartAfter(J11, r1)\n", "ps.TaskStartAfter(J12, r1)\n", "ps.TaskStartAfter(J13, r1)\n", "\n", "ps.TaskStartAfter(J21, r2)\n", "ps.TaskStartAfter(J22, r2)\n", "ps.TaskStartAfter(J23, r2)\n", "\n", "ps.TaskStartAfter(J31, r3)\n", "ps.TaskStartAfter(J32, r3)\n", "ps.TaskStartAfter(J33, r3)\n", "\n", "ps.TaskStartAfter(J41, r4)\n", "ps.TaskStartAfter(J42, r4)\n", "ps.TaskStartAfter(J43, r4)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Constraints: precedences\n", "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." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "J1 = [J11, J12, J13]\n", "J2 = [J21, J22, J23]\n", "J3 = [J31, J32, J33]\n", "J4 = [J41, J42, J43]\n", "\n", "# we need to combinations function of the itertools module,\n", "# to compute all pairs from the list of jobs.\n", "from itertools import combinations\n", "\n", "for Ja, Jb in combinations([J1, J2, J3, J4], 2):\n", " befores = []\n", " afters = []\n", " for i in range(3):\n", " Ja_before_Jb = ps.TaskPrecedence(Ja[i], Jb[i])\n", " Ja_after_Jb = ps.TaskPrecedence(Jb[i], Ja[i])\n", " befores.append(Ja_before_Jb)\n", " afters.append(Ja_after_Jb)\n", " xor_operation = ps.xor_([ps.and_(befores), ps.and_(afters)])\n", " flow_shop_problem.add_constraint(xor_operation)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Add a makespan objective" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "makespan_obj = flow_shop_problem.add_objective_makespan()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Solution, plot the schedule" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "solver = ps.SchedulingSolver(flow_shop_problem)\n", "solution = solver.solve()\n", "solution.render_gantt_matplotlib(fig_size=(10, 5), render_mode=\"Resource\")" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "We confirm the job sort from Tao et al. (2015) (J1 then J3, J4 and finally J2). The horizon is here only 21." ] } ], "metadata": { "kernelspec": { "display_name": "Python 3 (ipykernel)", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.9.0" } }, "nbformat": 4, "nbformat_minor": 4 }