Tightened Formulation and Resolution of Energy-Efficient Job-Shop Scheduling
Tightened Formulation and Resolution of Energy-Efficient Job-Shop Scheduling
复制标题
DOI：
10.1109/case48305.2020.9217035
复制
发表时间：
2020-08
期刊：
影响因子：
--
通讯作者：
B. Yan;Mikhail A. Bragin;P. Luh
中科院分区：
文献类型：
--
作者：
B. Yan;Mikhail A. Bragin;P. Luh
作业车间是小批量、高品种制造的重要生产环境。当有紧急订单时，某些机器的速度可以调整，但能耗和磨损成本很高。在这样的环境下进行调度就是为了实现准时交货和低能源成本。然而，这个问题很复杂，因为零件加工时间取决于机器的速度，而且机器需要单独建模以捕捉能源成本。本文的目的是有效地获得近似最优解。为了有效地利用现有的混合整数线性规划方法，将问题描述为混合整数线性规划(MILP)的形式。这是通过在近似能源成本的同时为简化而对机器进行分组建模，并通过将零件加工状态和机器速度变量联系起来来实现的。然而，由此产生的问题仍然复杂。因此，通过扩展我们之前针对恒速机器的紧固方法，该公式得到了改变。其思想是，如果约束可以转化为直接描绘凸壳，那么问题就可以用线性规划方法来解决。为了有效地解决这个问题，我们使用了先进的分解和协调方法。数值结果表明，该方法获得了接近最优解，表明了该方法在准时交货和能源成本方面的显著优势。
Job shops are an important production environment for low-volume high-variety manufacturing. When there are urgent orders, the speeds of certain machines can be adjusted with a high energy and wear and tear cost. Scheduling in such an environment is to achieve on-time deliveries and low energy costs. The problem is, however, complicated because part processing time depends on machine speeds, and machines need to be modeled individually to capture energy costs. This paper is to obtain near-optimal solutions efficiently. The problem is formulated as a Mixed-Integer Linear Programming (MILP) form to make effective use of available MILP methods. This is done by modeling machines in groups for simplicity while approximating energy costs, and by linking part processing status and machine speed variables. Nevertheless, the resulting problem is still complicated. The formulation is therefore transformed by extending our previous tightening approach for machines with constant speeds. The idea is that if constraints can be transformed to directly delineate the convex hull, then the problem can be solved by linear programming methods. To solve the problem efficiently, our advanced decomposition and coordination method is used. Numerical results show that nearoptimal solutions are obtained, demonstrating significant benefits of our approach on on-time deliveries and energy costs.