用整数规划法调度魁北克SAQ公司员工.docxVIP

用整数规划法调度魁北克SAQ公司员工SAQ：是法国魁北克省的一家公共公司，负责在其领土上通过400多家商店和仓库的大型网络经销和销售酒精类产品。·问题: 怎样安排超过3000员工的每周计划·直到 2002年，都是手工处理这个问题·非常昂贵: 薪金 + 投诉 = 130万加元/年·目标: 开发基于 web 的数据库系统以实现此过程的自动化工会要求公司进行顺序分配：·必须为最高级员工分配最佳的调度；·然后，使用剩余的班次为下一个最高级的员工分配最佳的调度；·直到分配了所有班次；保证生成可行的时间表／员工调度表（总有足够的员工来满足要求）；挑战：这个规则允许SAQ在两个员工之间拆分6小时或更多的班次，而且采用一小时无酬午餐／晚餐休息时间，这会产生很多复杂情况。在以下约束条件下，生成每个员工的每周日程安排：·任何员工每天工作不能在10小时以上, 每周工作不能在38 小时以上；·工会规定公司采用向后分配规则: 必须每天生成计划, 从每周结束 (星期六) 开始, 向后一直到开始 (星期日)；·目标是通过考虑要分配的班次和员工的有效性来最大化员工每天工作的工时数；·当然, 我们可以通过计划在整个星期内做得更好 (分配更多的工作时间), 但我们不允许这样做:，我们必须尊重所有的工会协议规则!一些基本定义：·把每天以15分钟为单位分成若干的时间段；·间隔:连续时间段的集合；工作间隔:员工工作的时间间隔；工作间隔的类别：白班（上午8:00-晚上11:00）；夜班（晚上9:00-上午6:00）；混合。·在计划某一天的日程时, 我们还必须考虑前一天的最后三小时；·不连续: 当员工被安排为两个不相交的工作时间间隔时会创建一个不连续（不连续不能超过2个）。一些规则：休息规则: 员工在夜班前后要有至少8小时的休息时间（为了执行向后分配规则, 我们必须知道员工在上一周的星期六停止工作的时间）；替换规则: 保证的班次将分配给员工, 除非有另一个计划产生同一工作间隔类别在同一商店中；移动时间规则: 当员工被分配给两个不同的商店时, 员工必须有足够的时间在它们之间移动。·午餐休息规则: 当工作间隔完全包含在间隔上午10:30-下午3:30 中时, 员工有一个小时的无酬午餐休息时间；·晚餐 (下午3:30 晚上8:30) 和隔夜休息的类似规则；拆分规则: 一个工作间隔可以分为两部分,工件和剩余，分别分配给两个员工；每个工作间隔必须至少包含3个小时，可班次至少有6个时间, 并且工件和剩余部分至少有3个小时。一些问题的情况：·雇主不得支付比所需工时更多的工时: 如果员工被分配了p个工作小时的工时间隔, 则是通过拆分总工时数为 n 的某些班次获得, 则剩余部分不应包含超过 n ? p 工作小时。·调整剩余部分:删除一小时；删除两小时；添加一小时。·禁止机会拆分, 允许避免午休的分割。目标函数：最大化工作时间数：任务首选项：员工偏向于完成哪个任务oit = 1: 如果期间i被分配到任务toWit = 1: 如果期间 i 工作并且被分配到任务 t·最小化不连续：·最小化员工被分配的商店数量·最小化拆分班次数·商店首选项：员工偏向于在哪个商店工作支持最早的期间 (从上午8:00 开始)最大化班次数·最大化工作时间数:一些限制：·分配约束: yi= 1:如果期间i被分配了；zj= 1:如果班次j被分配了；xij = 1:如果可拆分班次j被分配在期间 i；JiU ：一系列不可拆分的班次；JiD ：一系列可拆分的班次。休息约束:rk = 1: 如果雇员休息k，则约束可被写为：·工作时间限制: yiW = 1: 如果期间i工作正常；p=4，表示一个小时的休息包括四个期间。·不连续约束：ui = 1: 如果雇员被分配到期间 i, 但不是期间 i – 1；每个工作间隔必须至少包含三小时；uDi = 1, 如果在期间 i 中存在不连续；不超过两个不连续；uD0 = 1, 如果至少有一个不连续；·拆分班次约束：vij = 1: 如果可拆分班次j在i期间，则xij=1和x(i?1)j=0。wij = 1: 如果可拆分班次j在i?1期间, 即,xij = 0和x(i?1)j=1。每个可拆分班次只能拆分一次；剩余必须至少包含三小时；财务效益：系统开发成本: 130万 $，但是节省约100万美元/年 (75% 薪金, 25% 投诉)非财务效益：简化了商店经理和工会代表的工作；消除了纸面文件, 简化了数据管理, 减少了专用于计划任务的时间；工会的要求现在以统一的方式在全省的所有商店中进行解释: 消除许多投诉；对整个组织 (员工和商店经理、工会和人力资源部) 的工作关系的积极影响。