{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "7fb27b941602401d91542211134fc71a",
   "metadata": {},
   "source": [
    "# 劳动力调度问题\n",
    "\n",
    "**类别：** 排程\n",
    "\n",
    "使用 OptAgent 的 Python 接口描述变量、约束与目标。\n",
    "\n",
    "问题与原始示例来源：[Hexaly Code Templates](https://www.hexaly.com/templates/workforce-scheduling-problem)。\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "acae54e37e7d407bbb7b55eff062a284",
   "metadata": {},
   "source": [
    "## 问题描述\n",
    "\n",
    "在劳动力调度问题中,一家公司必须在一周内完成一组任务。每个任务在随时间变化的过程中需要数量不等的员工来满足需求。员工有各自的可用性约束——特定的日子和小时——并且可能不具备执行所有任务的资格。此外,每个任务需要一定的处理时间,而每位员工在同一时间只能执行一项任务。\n",
    "\n",
    "目标是制定一个调度方案,将员工分配到任务中,使任意时刻所需员工数与已分配员工数之间的差距最小化。该目标通过三个具体子目标来刻画,详见建模部分。\n",
    "\n",
    "### 学到的建模技巧\n",
    "\n",
    "- 定义字典序多目标模型并确定每个目标的优先级\n",
    "- 尽可能预计算指示变量,以降低模型的复杂度\n",
    "- 区分决策变量与中间表达式\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9a63283cbaf04dbcab1f6479b197f3a8",
   "metadata": {},
   "source": [
    "## 数据\n",
    "\n",
    "劳动力调度问题的数据文件格式如下:\n",
    "\n",
    "- 第一行:员工数量\n",
    "- 第二行:任务数量\n",
    "- 第三行:天数\n",
    "\n",
    "后续行由若干节段组成,分别包含以下信息:\n",
    "\n",
    "- 每个任务的持续时长\n",
    "- 每项任务每天每小时所需的员工数\n",
    "- 每位员工可工作的天数\n",
    "- 工作日内员工可工作的小时数\n",
    "- 每位员工能执行的任务集\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8dd0d8092fe74a7c96281538738b07e2",
   "metadata": {},
   "source": [
    "## 建模思路\n",
    "\n",
    "用于劳动力调度问题的 OptAgent 模型使用布尔决策变量来建模每位员工的排班。对于每位员工、每个任务和每个时间,决策变量表示该员工是否在该时刻开始该任务。\n",
    "\n",
    "为了降低模型的复杂度,我们进行一些预计算。在读取数据时,我们将每位员工的可用性信息与技能信息合并,生成一个指示变量,用于评估该员工是否能在给定时刻开始任务、执行任务,并在当天结束前完成。我们利用该指示变量来书写模型中的主要约束。为确保没有员工在同一时间被分配多项任务,我们考察所有可能导致冲突的决策变量对,并施加约束以防止它们同时为 true。\n",
    "\n",
    "接下来,我们估算每位员工每天的工作时间。我们对其施加上下界,以更贴近现实的工作场景。这样可以避免出现一位员工一天工作 12 小时而另一位一周仅工作 1 小时的情形。\n",
    "\n",
    "对于每个时间步,我们计算所需员工数与分配到各项任务的员工数之间的差值,从而得到每个任务的人手不足与人手过剩的指示变量。\n",
    "\n",
    "我们定义以下三个目标来求解劳动力调度问题:\n",
    "\n",
    "- 最小化任务的人手不足\n",
    "- 最小化任务的人手过剩\n",
    "- 最小化员工工作日的长度\n",
    "\n",
    "三个目标按字典序进行优化:声明的顺序即其重要性顺序。将人手不足和人手过剩分成两个独立目标,可以优先满足需求,即便这意味着某些时刻人员偏多。相比于某些时刻严重短缺而另一些时刻过剩,这更可取。该方法同时还能避免人手不足与过剩之间的相互抵消效应。\n",
    "\n",
    "第三个目标旨在使员工的工作日紧凑,尤其是在仅被分配少量任务时。通常,我们希望避免出现员工在早上 7:00 执行一项一小时任务,又在傍晚 6:00 执行另一项任务,中间长时间空闲的情形。\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "72eea5119410473aa328ad9291626812",
   "metadata": {},
   "source": [
    "## Python 实现\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "8edb47106e1a46a883d545849b8ab81b",
   "metadata": {},
   "outputs": [],
   "source": [
    "from pathlib import Path\n",
    "\n",
    "from optagent import OptModel, solve\n",
    "\n",
    "\n",
    "# Function used to extract the information from the data file\n",
    "def read_data(filename):\n",
    "    lines = iter(Path(filename).read_text(encoding=\"utf-8\").splitlines())\n",
    "\n",
    "    # Dimensions of the problem\n",
    "    nb_agents = int(next(lines))\n",
    "    nb_tasks = int(next(lines))\n",
    "    nb_days = int(next(lines))\n",
    "    horizon = nb_days * 24\n",
    "    min_working_time = 4\n",
    "    max_working_time = 8\n",
    "\n",
    "    # Tasks duration\n",
    "    next(lines)\n",
    "    task_duration = [0 for i in range(nb_tasks)]\n",
    "    for i in range(nb_tasks):\n",
    "        task_duration[i] = int(next(lines))\n",
    "\n",
    "    # Number of agents needed for the task i at time t\n",
    "    # agents_needed[i][t] contains the number of agents needed\n",
    "    # for the task i at time t\n",
    "    next(lines)\n",
    "    next(lines)\n",
    "    agents_needed = [[0 for t in range(horizon)] for i in range(nb_tasks)]\n",
    "    for d in range(nb_days):\n",
    "        for i in range(nb_tasks):\n",
    "            elements = next(lines).split(\" \")\n",
    "            for h in range(24):\n",
    "                t = d * 24 + h\n",
    "                agents_needed[i][t] = int(elements[h])\n",
    "        next(lines)\n",
    "\n",
    "    # Agent disponibility\n",
    "    # day_dispo[a][d] = 1 if agent a is available on day d\n",
    "    day_dispo = [[0 for d in range(nb_days)] for a in range(nb_agents)]\n",
    "    for a in range(nb_agents):\n",
    "        elements = next(lines).split(\" \")\n",
    "        for d in range(nb_days):\n",
    "            day_dispo[a][d] = int(elements[d])\n",
    "\n",
    "    # hour_dispo[a][h] = 1 if agent a is available on hour h\n",
    "    next(lines)\n",
    "    hour_dispo = [[0 for h in range(24)] for a in range(nb_agents)]\n",
    "    start_day = [0 for a in range(nb_agents)]\n",
    "    end_day = [0 for a in range(nb_agents)]\n",
    "    for a in range(nb_agents):\n",
    "        elements = next(lines).split(\" \")\n",
    "\n",
    "        start_day[a] = int(elements[0])\n",
    "        end_day[a] = int(elements[1])\n",
    "\n",
    "        hour_dispo[a][0 : start_day[a]] = [0] * start_day[a]\n",
    "        hour_dispo[a][start_day[a] : end_day[a]] = [1] * (end_day[a] - start_day[a])\n",
    "        hour_dispo[a][end_day[a] : 24] = [0] * (24 - end_day[a])\n",
    "\n",
    "    # We can concatenate these two informations\n",
    "    # into a global indicator of agent disponibility\n",
    "    # agent_dispo[a][t] = 1 if agent a is available\n",
    "    # on time t\n",
    "    agent_dispo = [[0 for t in range(horizon)] for a in range(nb_agents)]\n",
    "    for a in range(nb_agents):\n",
    "        for d in range(nb_days):\n",
    "            for h in range(24):\n",
    "                t = d * 24 + h\n",
    "                agent_dispo[a][t] = day_dispo[a][d] * hour_dispo[a][h]\n",
    "\n",
    "    # Agent skills\n",
    "    # agent_skills[a][i] = 1 if agent a is able to perform the task i\n",
    "    next(lines)\n",
    "    agent_skills = [[0 for i in range(nb_tasks)] for a in range(nb_agents)]\n",
    "    for a in range(nb_agents):\n",
    "        elements = next(lines).split(\" \")\n",
    "\n",
    "        for i in range(nb_tasks):\n",
    "            agent_skills[a][i] = int(elements[i])\n",
    "\n",
    "    # We can use all these informations and task length to get an indicator\n",
    "    # telling us if the agent a can begin the task i at time t,\n",
    "    # and complete it before the end of day\n",
    "    agent_can_start = [[[0 for t in range(horizon)] for i in range(nb_tasks)] for a in range(nb_agents)]\n",
    "    for a in range(nb_agents):\n",
    "        for i in range(nb_tasks):\n",
    "            for d in range(nb_days):\n",
    "                for h in range(0, start_day[a]):\n",
    "                    t = d * 24 + h\n",
    "                    agent_can_start[a][i][t] = 0\n",
    "                for h in range(start_day[a], end_day[a] - task_duration[i] + 1):\n",
    "                    t = d * 24 + h\n",
    "                    agent_can_start[a][i][t] = agent_dispo[a][t] * agent_skills[a][i]\n",
    "                for h in range(end_day[a] - task_duration[i] + 1, 24):\n",
    "                    t = d * 24 + h\n",
    "                    agent_can_start[a][i][t] = 0\n",
    "\n",
    "    return (\n",
    "        nb_agents,\n",
    "        nb_tasks,\n",
    "        nb_days,\n",
    "        horizon,\n",
    "        task_duration,\n",
    "        agents_needed,\n",
    "        day_dispo,\n",
    "        agent_can_start,\n",
    "        min_working_time,\n",
    "        max_working_time,\n",
    "    )\n",
    "\n",
    "\n",
    "# Returns the time steps corresponding to day d\n",
    "def times_of_day(d):\n",
    "    return range(d * 24, (d + 1) * 24)\n",
    "\n",
    "\n",
    "# Returns the time steps s such that\n",
    "# [s, s + duration) intersects time t\n",
    "def intersecting_starts(t, duration):\n",
    "    return range(max(t - duration + 1, 0), t + 1)\n",
    "\n",
    "\n",
    "def main(instance_file, output_file=None, time_limit=30):\n",
    "    (\n",
    "        nb_agents,\n",
    "        nb_tasks,\n",
    "        nb_days,\n",
    "        horizon,\n",
    "        task_duration,\n",
    "        agents_needed,\n",
    "        day_dispo,\n",
    "        agent_can_start,\n",
    "        min_working_time,\n",
    "        max_working_time,\n",
    "    ) = read_data(instance_file)\n",
    "\n",
    "    def build_and_solve():\n",
    "        #\n",
    "        # Declare the optimization model\n",
    "        #\n",
    "        model = OptModel()\n",
    "\n",
    "        # Definition of the decision variable :\n",
    "        # agent_start[a][i][t] = 1 if agent a starts the task i at time t\n",
    "        agent_start = [[[model.bool() for t in range(horizon)] for i in range(nb_tasks)] for a in range(nb_agents)]\n",
    "\n",
    "        # An agent can only work if he is able to complete his task\n",
    "        # before the end of the day\n",
    "        for a in range(nb_agents):\n",
    "            for i in range(nb_tasks):\n",
    "                for t in range(horizon):\n",
    "                    model.constraint(agent_start[a][i][t] <= agent_can_start[a][i][t])\n",
    "\n",
    "        # Each agent can only work on one task at a time\n",
    "        for a in range(nb_agents):\n",
    "            for i1 in range(nb_tasks):\n",
    "                for i2 in range(nb_tasks):\n",
    "                    for t1 in range(horizon):\n",
    "                        for t2 in intersecting_starts(t1, task_duration[i2]):\n",
    "                            if (i1 != i2) or (t1 != t2):\n",
    "                                model.constraint(agent_start[a][i1][t1] + agent_start[a][i2][t2] <= 1)\n",
    "\n",
    "        # Working time per agent per day\n",
    "        agent_working_time = [\n",
    "            [\n",
    "                sum(agent_start[a][i][t] * task_duration[i] for i in range(nb_tasks) for t in times_of_day(d))\n",
    "                for d in range(nb_days)\n",
    "            ]\n",
    "            for a in range(nb_agents)\n",
    "        ]\n",
    "\n",
    "        # Minimum and maximum amount of time worked\n",
    "        for a in range(nb_agents):\n",
    "            for d in range(nb_days):\n",
    "                if day_dispo[a][d] == 1:\n",
    "                    model.constraint(agent_working_time[a][d] >= min_working_time)\n",
    "                    model.constraint(agent_working_time[a][d] <= max_working_time)\n",
    "\n",
    "        # Difference between needed and attributed number of agents\n",
    "        # for each task\n",
    "        agent_attributed = [\n",
    "            [\n",
    "                sum(agent_start[a][i][t] for a in range(nb_agents) for t in intersecting_starts(t0, task_duration[i]))\n",
    "                for t0 in range(horizon)\n",
    "            ]\n",
    "            for i in range(nb_tasks)\n",
    "        ]\n",
    "\n",
    "        agent_diff = [[agents_needed[i][t] - agent_attributed[i][t] for t in range(horizon)] for i in range(nb_tasks)]\n",
    "\n",
    "        # Indicators for lack and excess of agents\n",
    "        agent_lack = sum(model.pow(model.max(agent_diff[i][t], 0), 2) for t in range(horizon) for i in range(nb_tasks))\n",
    "\n",
    "        agent_excess = sum(\n",
    "            model.pow(model.max(-agent_diff[i][t], 0), 2) for t in range(horizon) for i in range(nb_tasks)\n",
    "        )\n",
    "\n",
    "        agent_day_start = [\n",
    "            [\n",
    "                model.min(t + (1 - agent_start[a][i][t]) * horizon for i in range(nb_tasks) for t in times_of_day(d))\n",
    "                for d in range(nb_days)\n",
    "            ]\n",
    "            for a in range(nb_agents)\n",
    "        ]\n",
    "\n",
    "        agent_day_end = [\n",
    "            [\n",
    "                model.max(\n",
    "                    (t + task_duration[i]) * agent_start[a][i][t] for i in range(nb_tasks) for t in times_of_day(d)\n",
    "                )\n",
    "                for d in range(nb_days)\n",
    "            ]\n",
    "            for a in range(nb_agents)\n",
    "        ]\n",
    "\n",
    "        # Difference between first and last hour of agents each day\n",
    "        agent_day_length = sum(\n",
    "            model.max(agent_day_end[a][d] - agent_day_start[a][d], 0) for a in range(nb_agents) for d in range(nb_days)\n",
    "        )\n",
    "\n",
    "        # Objectives\n",
    "        model.minimize(agent_lack)\n",
    "        model.minimize(agent_excess)\n",
    "        model.minimize(agent_day_length)\n",
    "\n",
    "        solution = solve(model, time_limit_s=float(time_limit))\n",
    "        if not solution.feasible:\n",
    "            print(f\"No feasible schedule found; Status = {solution.status}\")\n",
    "            return solution\n",
    "\n",
    "        print(\n",
    "            f\"Agent lack = {agent_lack.value}; Agent excess = {agent_excess.value}; \"\n",
    "            f\"Day length = {agent_day_length.value}; Status = {solution.status}\"\n",
    "        )\n",
    "        # Outputs if output file specified\n",
    "        if output_file is not None:\n",
    "            lines = [str(agent_lack.value), str(agent_excess.value), str(agent_day_length.value)]\n",
    "            for a in range(nb_agents):\n",
    "                for i in range(nb_tasks):\n",
    "                    lines.append(\" \".join(str(agent_start[a][i][t].value) for t in range(horizon)) + \" \")\n",
    "                lines.append(\"\")\n",
    "            Path(output_file).write_text(\"\\n\".join(lines) + \"\\n\", encoding=\"utf-8\")\n",
    "            print(\"Solution written in file\", output_file)\n",
    "        return solution\n",
    "\n",
    "    return build_and_solve()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "10185d26023b46108eb7d9f57d49d2b3",
   "metadata": {},
   "outputs": [],
   "source": [
    "INSTANCE_DIR = Path.cwd() / \"instances\"\n",
    "print(\"Instances:\", INSTANCE_DIR)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "8763a12b2bbd4a93a75aff182afb95dc",
   "metadata": {},
   "outputs": [],
   "source": [
    "solution_2tasks = main(INSTANCE_DIR / \"2tasks.txt\", time_limit=1)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "name": "python",
   "version": "3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}