An Approximation Algorithm for Unrelated Parallel Machine Scheduling Under TOU Electricity Tariffs

摘要

In an era of sustainable development, considerable emphasis has been put onto energy saving, environment friendly, and social welfare as well as productivity in the manufacturing sector. In this work, an unrelated parallel manufacturing setting with time-of-use (TOU) electricity price is explored, with an aim to reduce the electricity cost and increase productivity simultaneously. A nonlinear mathematical programming model is formulated to exploit the special structure of the scheduling problem, where the quadratic constraints are reformulated as second-order-cone (SOC) constraints, and several tailored cutting planes are introduced to further tighten the feasible region of the problem. Then, the original scheduling problem is transformed into several single-machine scheduling problems with TOU electricity price, which could be relaxed as a single-objective programming problem, and it could be solved rapidly via commercial solvers, such as CPLEX. Based on the optimal solution of the relaxed problem, an approximate algorithm is proposed, where a special rounding technique is employed to assign jobs to the unrelated parallel machines in a local search manner. Furthermore, a lower bound model is constructed by eliminating the nonpreemption constraint, and an iteration-based algorithm is devised to obtain the optimal solution of the lower bound problem. Meanwhile, a dispatch rule-based approach is proposed to provide an upper bound of the scheduling problem with TOU constraint. In the numerical analysis section, the proposed approximate algorithm is validated through extensive testing on various scales of instances, different emphasis on productivity and electricity price, and under two typical TOU electricity pricing policies. It is observed that the gap between the proposed approximate algorithm and CPLEX is mostly within 4%, and the lower/upper bound methods could obtain a relaxed/feasible solution within 0.01 s. Note to Practitioners-Energy saving together with productivity improvement in the manufacturing system becomes the focus of both academia and industry over the years due to the increasing deterioration of the environment and the advancement of commercialization. In order to maintain better social welfare, the government usually makes time-of-use (TOU) electricity pricing policies to rebalance energy demand. For each manufacturing company, a tradeoff analysis should be performed to adapt to the TOU electricity price, so as to achieve the most desirable outcome. During the decision-making process, the practitioners should assign weights to the productivity and the energy cost to match their anticipation. For a typical manufacturing setting where all the machines are unrelated parallel, the proposed approximate algorithm, also known as the F-SOC algorithm, could be employed to obtain a near-optimal schedule within a short period of time. The proposed approximate algorithm could also work well in situations where the TOU electricity pricing policies are switching, and the preferences for productivity versus energy cost are swaying. A near-optimal schedule could always be guaranteed within a 4% gap from the optimal solution for most cases.