Abstract: Research background.With the rising problem of environment pollution and energy shortage, adapting to the feature of energy supply side to reduce the operation cost and increase its competitiveness is becoming more and more important for manufacturers who need draw a huge amount of power. Time-of-Use tariff is a kind of method to encourage the manufacturing plants to move their power demand from the peak hours to the off-peak hours by setting different prices in different hours. Therefore, the managers need to know how to schedule the production plan in order to minimize the energy cost and satisfy the production deadline constraint at the same time. Almost articles in literature use the discrete-time model and meta-heuristic to solve this kind of problem. Our motivation is establishing a continuous-time model and designing an exact algorithm, which can be useful for the industrial practitioners and the following researchers.
Problem description. A set of jobs need to be processed during the production horizon[0, W], which is divided into some periods {[0,a₁];[a₁,a₂];…;[a_T-1,a_T]}.The energy price in the t^th period is e_t. It is needed to decide the start time s_i of each job J_i. Then, the energy cost of J_i in the t^th period can be calculated as e_t^*v^* max{0,min(a_t,s_i+p_i)-max(a_t-1,s_i)}, where v is the power demand of running machine and p_i is the processing time of J_i. Combining the assignment and positional formulation, which uses binary variables to directly assign jobs to positions in a permutation, a continuous-time mixed integer programming mathematical model for the single machine system under time-of-use tariff is established.
Algorithmdesigning.Firstly, for the subproblem with fixed jobs' sequence, the relation between jobs' start times and energy price period is analyzed. A theorem is proven as follows. The optimal start times of jobs can only be four scenarios. Scenario (a):this job is started at its arrival time. Scenario (b):this job is started at the beginning of one price period. Scenario (c):this job is started at some time and finished exactly at the ending of one price period. Scenario (d):this job is located in a compact block which consists of several consecutive jobs and the start time of this block satisfies the scenario (a) or (b) or (c). According to the theorem, the start times become discrete variables. Therefore, a structural branch-and-bound algorithm is designed based on branching the start times. Meanwhile, the method calculating lower bound and the method cutting branches are proposed to improve the efficiency of algorithm. Finally, four different strategies are designed to explore the impact of jobs' sequence on the total energy cost. The algorithm proposed solves the nonlinearity difficulty caused by the period, which can be used to solve other complicated extended problems, for example, the energy allocation problem in manufacturing plant when the renewable energy resources are considered.
Main results. Compared with the CPLEX which can only solve the small-sized problems, the computation time of our branch-and-bound is quite short. Comparing four strategies searching jobs' sequence, it shows that the impact of jobs' sequence is quite small and the manager should focus on the buffer time allocation. The numerical experiments show that the model proposed in this paper can reduce the energy cost significantly compared with the traditional way. No matter with the distribution of jobs' arrival time, the highest reduction reaches 40% when the number of price periods equals to 200. It also validates that the impact of increasing energy price is larger when the production deadline is rather tight.

Key words: production scheduling, energy cost, time-of-use, branch and bound