摘要：This paper addresses a non-preemption case of a particular single machine scheduling problem with a pre-determined sequence for the jobs. The considered machine may switch between three different states (namely ON, OFF or Idle) to process all the jobs during a finite number of periods. Each state, as well as switching between the states, entails a certain energy consumption, and the objective is total energy consumption costs minimization under time varied electricity prices. This problem was already addressed in the literature, where the authors assumed it as an NP-hard problem and they introduced a meta-heuristic method to solve the problem. This study discusses the complexity of the problem to verify this fact. For this purpose, an exact polynomial method is proposed to solve the problem. In this approach, firstly the problem is modeled using a finite graph whose dimension (number of vertices and edges) is dependent on the total processing times and the total number of periods. Then, Dijkstra’s algorithm is applied to find the shortest path between the initial node and the final one, which provides the optimal solution in polynomial time. So, we can conclude that the problem is polynomial, and it does not need to use meta-heuristic approaches even for solving large instances of this problem. A numerical experiment study is also reported to show the effectiveness of the proposed approach for solving any instances of this problem in a negligible computation time.
关键词：KeywordsOR in EnergyTime-dependent energy costNon-preemption Single machine schedulingDynamic programmingDijkstra’s algorithm
