Investigation of the two-machine flow shop scheduling problem to minimize total energy costs with time-dependent energy prices

In this paper, the problem of two-machine flow shop scheduling to minimize total energy costs under time-of-use tariffs is investigated. As the objective function of this study is not a regular measure, allowing intentional idle-time can be advantageous. So this study considers two approaches, one for non-delay version of the problem and the other one for a situation when inserting intentional idle time is permitted. A mixed integer linear programming is formulated to determine the timing of jobs in order to minimize total energy costs while idle time insertion is allowed. For the non-delay version of the problem, a branch-and-bound algorithm is presented. A lower bound and several dominance properties are used to increase the speed of the branch-and-bound algorithm. Computational experiments are also given to evaluate the performance of the algorithm. Based on results, the proposed algorithms can optimally schedule jobs in small size samples but by increasing the number of jobs from 15 and cost periods from 3, the performance of branch-and-bound has been decreased.