Job shop 调度问题中的设置时间

Question

我正在研究 google or-tools 在调度问题上的应用。我对 cp_model api 非常满意，但它似乎缺少一些仅在车辆路径模块 pywrapcp 中可用的功能。

以下是使用官方页面上提供的 cp_model 模块的程序的基本示例：https://developers.google.com/optimization/scheduling/job_shop#entire-program

我的问题是：是否可以在上面的代码中引入设置时间维度，就像我们在常规 TSP 问题中所做的那样：

    def distance_callback(from_index, to_index):
        """Returns the distance between the two nodes."""
        # Convert from routing variable Index to distance matrix NodeIndex.
        from_node = manager.IndexToNode(from_index)
        to_node = manager.IndexToNode(to_index)
        return data['distance_matrix'][from_node][to_node]

    transit_callback_index = routing.RegisterTransitCallback(distance_callback)

    # Define cost of each arc.
    routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)

找到的唯一接近的例子是这个：https://github.com/google/or-tools/blob/stable/examples/python/single_machine_scheduling_with_setup_release_due_dates_sat.py 但是，它似乎只能在一台机器上工作。

Answer 1

有 3 个示例来描述设置时间：

Job shop 调度问题中的设置时间

Setup times in a Job shop scheduling problem

optimization

or-tools