生产调度（排序）

生产调度（排序）的思维导图，内容有单机、最大延误问题Lmax、批调度与平行机、流水车间、开放车间、作业车间。

生产调度

• 单机
  • 1| |Cmax
    • 按顺序即可，分顺序和逆序
  • 1| rj |Cmax（带施放时间）
  • 1 | rj | 求和Cj
    • 最短剩余处理时间SRPT规则 先看释放时间，满足施放时间要求之后再看谁的处理时间p短，谁先来
  • 1 | rj ，prmp| 求和Cj
    • SRTP（每一时刻都要暂停观察剩余处理时间）
  • 1 | | 求和Cj
    • SPT规则
  • 1 | | 求和WjCj
    • WSPT规则:Pj/Wj，按从小到大排，即权重大，值就小，就往前排
    • 证明
      • • 证明：SWPT规则，按P/W从小到大排序（升序）： 假设J>k；并且从大到小排（降序）。 那么J先k后为最优L，k先J后不是最优L； 所以L<=L； 但是最终L>L 所以假设不成立；证毕
• 最大延误问题Lmax
  • 1 | | Lmax
    • EDD最早开始时间规则
    • 证明
      • • 证明：EDD规则，按照d从小到大排序（升序）： 假设dj>dk，并且从大到小排（降序）。 所以先j后k为最优d，先k后j不是最优d； 所以L<L； 但是最终L>L 矛盾，所以不成立，证毕；
  • 1 | rj | Lmax
    • 强NP难
  • 1 | rj，prmp| Lmax
    • PEDD规则（停下来看谁的d，开始时间短就换谁）
    • 分支定界不考
• 批调度与平行机
  • 1 |S（serial串行），GT（group technology成组技术）| 求和Cj
    • 1.先组内按SPT排序
    • 2.算Q，Q=S（调整时间）+（各个处理时间Pj）
    • 3.计算顺序，从小到大排，Q/n
  • 平行机（P） 1| batch |Cmax
    • 处理时间p从大到小排序，然后分b组
  • Pm | | Cmax（按顺序排，谁最小加到谁）或者LPT
  • Pm | | 求和Cj
    • SPT
  • Pm | | 求和WjCj
    • NP难
      • WSPT/OPT=(1+根号2)/2
  • Pm|Pj=1 tree |Cmax
    • 关键路线法
      • • 最优比4/3
  • Pm| prmp |Cmax
    • 分割算法
    • LRPT最大剩余时间
• 流水车间
  • Fm | | Cmax
    • johnson rule： 1.分两组，第一组是第一台小于第二台的时间；其中按照第一台机器处理时间SPT排序；第二组按照第二台机器的处理时间LPT排序
    • prmu
    • GS算法（m=4）
      • 以M1 M2和M3 M4两次johnson rule后选小的
  • Fm | | Cmax
    • 分支定界算法
  • F2 | | 求和Cj
    • SPT（哪个工件完工时间和最小哪个先做）
    • 分支定界
• 开放车间
  • O2 | | Cmax
    • LAPT（最长它机处理时间）
    • DS-LPT
• 作业车间
  • jackson rule