应用¶
基本概念¶
均衡生产：heijunka
组合优化基础¶
装箱问题(Bin Packing, BP)
背包问题(Knapsack Problem, KP)
车间调度问题(Job-shop Scheduling Problem, JSP)
整数规划问题(Integer Programming, IP)
旅行商问题(Traveling Salesman Problem, TSP)
车辆路径问题(Vehicle Routing Problem, VRP)
图着色问题(Graph Coloring, GC)
图匹配问题(Graph Matching, GM)
精确算法：分支定界法(Branch and Bound)和动态规划法(Dynamic Programming)
- 近似算法：近似算法(Approximate Algorithms)和启发式算法(Heuristic Algorithms)
贪心算法、局部搜索算法、线性规划、松弛算法、序列算法
模拟退火算法、禁忌搜索、进化算法、蚁群优化算法、粒子群算法、迭代局部搜索、变邻域搜索
数据¶
MRP: Material Requirements Planning
BOM: Bill Of Materials
Route
数据准备 - 主需求数据 - 工艺路线 - 资源日历
功能¶
一个完善的APS系统包含以下模块。 - 需求中心 - 排程中心 - 排程工作台 - 物料中心
建模¶
Activities represent operations with time and resource requirements Resources have calendars defining availability Demand represents customer orders to fulfill
过程¶
实际APS会涉及到各个车间，各个工序的复杂区分，以及BOM中涉及到多工厂的部分。 - 其实和APS关系不大，APS只要把最后一层工序展开，最后一层BOM展开，按实际的资源约束进行计算，最后只是展现形式上的区别
首先解决m个工序、n个机器的车间排产问题，然后把实际问题往车间问题靠。
1、根据一定的规则（产品总工作时长、工序B的最早开工时间等）获得产品的优先级 2、初始化任务的初始状态，除了每个产品的工序A为可开工状态其余皆为不可开工状态； 3、根据优先级对工序A对应的任务进行加工，并更新任务的状态及紧后工序的状态； 4、对机器的空闲时间进行排序，取最早可开工机器k； 5、根据机器k的空闲开始时间以及任务状态检索任务，存储为任务列表R； 6、判断任务列表R是否为空，是则k=k+1，返回步骤五，否则进行下一步； 7、根据任务的最早可加工时间进行排序，选择最早开始的任务进行加工，更新机器状态、任务状态及后续的工序状态； - 确定任务的开工时间及结束时间 - 更新机器的释放时间 - 更新当前任务的状态、开工时间、完工时间 - 更新当前任务后续节点的最早开工时间，若当前任务为产品的最后一个工序则无须更新 8、判断所有任务是否均已完工，是则结束，否则返回步骤四。
解决冲突的过程，即是一个顺排的过程。把所有分布在该资源上的任务根据顺序进行顺排
车间过程1-倒排+顺排¶
先分发冻结期，按锁定期 - 关键问题：成组后的工序部分处于冻结期；job的工序不是完整的工序 - 只assign资源和日历，由于不完整进行顺排。 - 检查物料齐套约束，如果物料不齐套，按齐套排程并给出报警消息
再排锁定任务
只倒排，如果倒排不可行则返回错误。按优先级 - 非关键工序: 按lead_time（倒排lead_time，顺排lag_time）、节拍往前排，不考虑齐套时间。 - 关键工序: 如有锁定资源，则按资源情况进行编排。不考虑齐套时间，因为锁定任务是为了确保优先级，物料通过缺料去人工追料 - 共享工序: 共享工序本身取多个job中靠前的时间断。 - 原本已经排过的其他job，前序工序需要以此为新的往前推 - 同时拥有共享工序的job排序适时进行调整，尽量避免以上修改 - 在冻结期且物料约束不满足: 按最早齐套时间进行排产，同时已排工序进行
再根据优先级排产其他任务
先倒排 - 第一道关键工序前的非关键工序，先按lead time进行排，后面需要二次更新。 - 关键工序倒排，(task分割会有的)非关键工序则按lead time前推 - 倒排中时间约束都是最晚时间，但物料约束是最早开始时间。如果时间不足以排产，则该工序及之后的工序都转为顺排重排 - 另一个思路是，先直接道排到第一个工序，后续一起按照可开始时间进行顺排。甚至等到推紧时一起顺排是否可行呢 - 遇到共享task，如果之前的共享task被安排的时间更晚，那么剩余工序也转为顺排重排 - 第一步剩余的非关键工序后拉 - 如果任务一步中，资源日历不足则进入下一步
倒排有问题则顺排 - 按各个资源最早可用日期开始排 (此时应该选可以最早的资源)，非关键工序按lead time排，并需要进行二次更新 - 关键工序顺排. 如果遇到共享task不满足时间约束 - 第一步剩余的非关键工序前拉 - 如果任何一步中，资源日历不足则返回错误 关键工序完全没有设置的job，按无限产能倒排
任务推紧规整 - 所有任务都采用顺排，类似按资源排产的方法。 - 按关键工序设置，“是否可以挪动”。每一个资源的第一道关键工序都可以向前，并跟新后续的可挪动状态与开始时间约束 - 迭代更新
未排任务再次尝试 - 推紧之后，再次尝试将之前未排的任务进行排产
委外/外协的排产 - 委外的指定是针对供应商，排到日历中 - 根据关键工序的产能，按优先级将各委外的部分进行排产
车间过程2-倒排+顺排2¶
仍然是先排锁定任务
把所有任务按照交期和最早开工日期进行倒排或顺排，不考虑资源的约束本身 【带来的问题是：资源优先级的选择】
顺排的时候，按照job优先级 【指定 > 优先级】 - 每一个job都按第一道工序其最早开工日期开始，
车间过程3-按资源增量排产¶
输入: 排产任务(MO+计划单) 输出: 各工序的排产资源与结果 1. 筛选出主工单与部件工单，建立子部件的属性联系 2. 筛选出主工单中的关键工序与非关键工序 3. 初始化历史已排且其资源仍存在的关键工序的资源队列 4. 对于新任务计划单或资源不存在的情况下, 重新分配任务. 完成资源中任务队列初始化 5. 资源中任务队列重排 6. 主工单非关键工序的前推后拉 7. 部件工单和工序的前推
车间过程4¶
多工序排产 - 资源上尽量继承原排产顺序，保持结果稳定 -
可视化¶
资源在时间线上的计划情况
按订单，在时间线上的操作情况
可视化重排¶
输入: 资源和资源任务队列顺序 输出: 1. 初始化到增量排产队列任务
产能爬坡¶
Material_op一开始，解析爬坡配置, 得到按小时或按数量的map, 或爬升曲线配置
计算OP时间时, 该OP可能是单个工单，或一个计划单/MRP的跨作业单大工序. 每个OP, 都额外记录其在MaterialOP的时间, 根据该时间从map中找到额外消耗的时间，作为爬坡后的时间
同时每个op, 记录其爬坡阶段的的小时和按小时产能
计算最终详细排产结果时，根据一个op的初始时间和结束时间，划分落在每个班次的时长，和数量
[修正: 不能在结果生成时，才产出数量。结果时，每个op在资源那里拆成了按单班产能，结果生成时已经不知道具体的详细爬坡了?.在生成时就确定数量. 但最后一个的数量，可以在最后矫正]
车间排产¶
准备环境
2. 定义领域模型 Entity - Job - Resource - Timeslot
Planning entity - JobAssignment
Solution - Jobschedule
约束
Solver