pyschedule, 在 python 中,pyschedule资源约束调度

分享于 

11分钟阅读

GitHub

  繁體
pyschedule - fast-forward resource-constrained scheduling in python
  • 源代码名称:pyschedule
  • 源代码网址:http://www.github.com/timnon/pyschedule
  • pyschedule源代码文档
  • pyschedule源代码下载
  • Git URL:
    git://www.github.com/timnon/pyschedule.git
    Git Clone代码到本地:
    git clone http://www.github.com/timnon/pyschedule
    Subversion代码到本地:
    $ svn co --depth empty http://www.github.com/timnon/pyschedule
    Checked out revision 1.
    $ cd repo
    $ svn up trunk
    
    在 python 中的pyschedule资源调度

    pyschedule是使用资源进行 MATCH 任务的最简单方法。 你需要计划一个会议或者安排你的员工,还有很多需求,如房间或者最大允许工作时间。 那么pyschedule可能是为你准备的。 用pip安装它:

    pip install pyschedule

    下面是一个 Hello World 示例,你还可以将这里文档作为一个笔记本文件找到。 这里有更多的示例笔记本,在这里有一个例子,在示例中有更简单的示例。 有关技术概述,请到这里的

    # Load pyschedule and create a scenario with ten steps planning horizonfrom pyschedule import Scenario, solvers, plotters
    S = Scenario('hello_pyschedule',horizon=10)# Create two resourcesAlice, Bob = S.Resource('Alice'), S.Resource('Bob')# Create three tasks with lengths 1,2 and 3cook, wash, clean = S.Task('cook',1), S.Task('wash',2), S.Task('clean',3)# Assign tasks to resources, either Alice or Bobcook += Alice|Bob
    wash += Alice|Bob
    clean += Alice|Bob# Solve and print solutionS.use_makespan_objective()
    solvers.mip.solve(S,msg=1)# Print the solutionprint(S.solution())
    
    INFO: execution time for solving mip (sec) = 0.025879621505737305
    
    
    INFO: objective = 3.0
    
    
    [(clean, Alice, 0, 3), (cook, Bob, 0, 1), (wash, Bob, 1, 3), (MakeSpan, Alice, 3, 4)]
    
    
    
    

    在本例中,我们使用一个makespan目标,这意味着我们希望最小化最后一个任务的完成时间。 ,Bob cooking cooking cooking cooking cooking washing washing washing washing Alice Alice Alice Alice Alice Alice cleaning cleaning cleaning cleaning cleaning cleaning cleaning。 这将确保在三个小时后完成。 这个表表示有点难以阅读,我们可以使用matplotlib来可视化计划:

    %matplotlib inline
    plotters.matplotlib.plot(S,fig_size=(10,5))

    png

    pyschedule支持不同的解决方案,经典的MIP,以及 CP -based。 所有解算器及其功能都在概述笔记本中列出。 上面使用的默认求解器使用标准的mip模型和 CBC,这是包的一部分。 如果你安装了 SCIP ( 命令"SCIP"必须运行),你可以使用以下方法轻松地对SCIP进行 switch 操作:

    solvers.mip.solve(S,kind='SCIP')

    同样,如果你安装了 CPLEX ( 命令"CPLEX"必须运行),则可以使用以下方法对CPLEX进行 switch 操作:

    solvers.mip.solve(S,kind='CPLEX')

    pyschedule处于活动开发状态,可能有non-backward-compatible更改。 下面的示例解释了更多基本特性。

    Alice和Bob用pyschedule优化他们的自行车油漆店

    Alice和Bob正在为自行车开一个油漆商店,那里有pimp的fresh。 今天他们必须画一个绿色和红色的自行车。 为了开始,他们导入pyschedule并创建一个新的场景。 我们使用小时作为粒度,预计每天的工作时间最多为 10小时,因此我们将计划范围设置为 10. 某些求解器不需要此参数,但默认求解器需要它:

    from pyschedule import Scenario, solvers, plotters
    S = Scenario('bike_paint_shop', horizon=10)

    然后,它们将自己作为资源创建:

    Alice = S.Resource('Alice')
    Bob = S.Resource('Bob')

    画自行车需要两个小时。 而且,在绘制完自行车之后,它需要得到post处理( 比如。 轮胎抽水需要一小时( 这是默认的)。 这将转换为四个任务:

    green_paint, red_paint = S.Task('green_paint', length=2), S.Task('red_paint', length=2)
    green_post, red_post = S.Task('green_post'), S.Task('red_post')

    显然,只能在绘画之后使用任意间隙进行贴图处理。 对于红色漆我们有点严重,这里我们要在画后一小时开始,因为这是颜色需要干燥的时间。

    S += green_paint < green_post, red_paint +1<= red_post

    每个任务都可以由Alice或者Bob完成。

    green_paint += Alice|Bob
    green_post += Alice|Bob
    red_paint += Alice|Bob
    red_post += Alice|Bob

    让我们来看看这个场景:

    S.clear_solution()print(S)
    
    ###############################################
    
    
    
    SCENARIO: bike_paint_shop/horizon: 10
    
    
    
    OBJECTIVE: None
    
    
    
    RESOURCES:
    
    
    Alice
    
    
    Bob
    
    
    
    TASKS:
    
    
    green_paint : Alice|Bob
    
    
    red_paint : Alice|Bob
    
    
    green_post : Alice|Bob
    
    
    red_post : Alice|Bob
    
    
    
    JOINT RESOURCES:
    
    
    Alice|Bob : red_paint
    
    
    Alice|Bob : red_post
    
    
    Alice|Bob : green_paint
    
    
    Alice|Bob : green_post
    
    
    
    LAX PRECEDENCES:
    
    
    green_paint <green_post
    
    
    
    TIGHT PRECEDENCES:
    
    
    red_paint + 1 <= red_post
    
    
    
    ###############################################
    
    
    
    

    我们还没有定义一个目标,让我们使用最大长度并再次检查场景:

    S.use_makespan_objective()print(S)
    
    ###############################################
    
    
    
    SCENARIO: bike_paint_shop/horizon: 10
    
    
    
    OBJECTIVE: MakeSpan
    
    
    
    RESOURCES:
    
    
    Alice
    
    
    Bob
    
    
    
    TASKS:
    
    
    green_paint : Alice|Bob
    
    
    red_paint : Alice|Bob
    
    
    green_post : Alice|Bob
    
    
    red_post : Alice|Bob
    
    
    MakeSpan : Alice
    
    
    
    JOINT RESOURCES:
    
    
    Alice|Bob : red_paint
    
    
    Alice|Bob : red_post
    
    
    Alice|Bob : green_paint
    
    
    Alice|Bob : green_post
    
    
    
    LAX PRECEDENCES:
    
    
    green_paint <green_post
    
    
    green_paint <MakeSpan
    
    
    red_paint <MakeSpan
    
    
    green_post <MakeSpan
    
    
    red_post <MakeSpan
    
    
    
    TIGHT PRECEDENCES:
    
    
    red_paint + 1 <= red_post
    
    
    
    ###############################################
    
    
    
    

    因这里,我们希望最小化完成时间任务的位置受它的所有它的他任务之后的约束。 因此,MakeSpan的位置就是我们计划的长度。 现在我们有了场景的第一个版本,让我们来解决它,并对它进行 plot:

    # Set some colors for the taskstask_colors = { green_paint : '#A1D372',
     green_post : '#A1D372',
     red_paint : '#EB4845',
     red_post : '#EB4845',
     S['MakeSpan'] : '#7EA7D8'}# A small helper method to solve and plot a scenariodefrun(S) :
     if solvers.mip.solve(S):
     %matplotlib inline
     plotters.matplotlib.plot(S,task_colors=task_colors,fig_size=(10,5))
     else:
     print('no solution exists')
    run(S)

    png

    鲍瑟很烦,如果他画了红色自行车,他也想做邮件处理,切换自行车花费太多时间。 我们使用以下约束来确保。 他们确保画和处理红色自行车都是由Alice或者Bob完成的。 绿色的也是一样的:

    # First remove the old resource to task assignmentsgreen_paint -= Alice|Bob
    green_post -= Alice|Bob
    red_paint -= Alice|Bob
    red_post -= Alice|Bob# Add new shared onesgreen_resource = Alice|Bob
    green_paint += green_resource
    green_post += green_resource
    red_resource = Alice|Bob
    red_paint += red_resource
    red_post += red_resource
    run(S)

    png

    这个计划在四小时后完成,并建议同时绘制两个自行车。 但是,Alice和Bob只有一家油漆店,他们需要共享:

    Paint_Shop = S.Resource('Paint_Shop')
    red_paint += Paint_Shop
    green_paint += Paint_Shop
    run(S)

    png

    很好,大家五小时后还可以回家吃午饭 ! 不幸的是,Alice接到一个电话,红色自行车只有两个小时后才会到达:

    S += red_paint >2run(S)

    png

    太糟糕了,现在需要六个小时才能完成。 因这里Alice和Bob决定在第三个小时之后和第五小时之前安排一个午餐:

    Lunch = S.Task('Lunch')
    Lunch += {Alice, Bob}
    S += Lunch >3, Lunch <5task_colors[Lunch] ='#7EA7D8'run(S)

    png

    最后,Alice是一个早起的人,希望在午饭前完成三个小时的工作,即在三个小时之前:

    S += Alice['length'][:3] >=3run(S)

    png

    所有这些听起来很简单,但是考虑到许多自行车和许多人的同样问题 !


    CONS  resource  Const  计划  
    相关文章