An Energy-Efficient Unrelated Parallel Machine Scheduling Problem with Batch Processing and Time-of-Use Electricity Prices

Abstract

The extensive consumption of energy in manufacturing has led to a large amount of greenhouse gas emissions that have caused an enormous effect on the environment. Therefore, investigating how to reduce energy consumption in manufacturing is of great significance to cleaner production. This paper considers an energy-conscious unrelated parallel batch processing machine scheduling problem under time-of-use (TOU) electricity prices. Under TOU, electricity prices vary for different periods of a day. This problem is grouping jobs into batches, assigning the batches to machines and allocating time to the batches so as to minimize the total electricity cost. A mixed-integer linear programming model and two groups of heuristics are proposed to solve this problem. The first group of heuristics first forms batches, assigns the batches to machines and finally allocates time to the batches, while the second group of heuristics first assigns jobs to machines, batches the jobs on each machine and finally allocates time to each batch. The computational results show that the SPT-FBLPT-P1 heuristic in the second group can provide high-quality solutions for large-scaled instances in a short time, in which the jobs are assigned to the machines based on the shortest processing time rule, the jobs on each machine are batched following the full-batch longest processing time algorithm, and the time is allocated to each batch following an integer programming approach. The MDEC-FBLPT-P1 heuristic that uses the minimum difference of the power consumption algorithm to assign the jobs also performed well.

1. Introduction

The batch scheduling problem is an important type of production scheduling problem. Batch scheduling problems have attracted the attention of researchers and manufacturers because batch processing machines (BPMs) are often used in many manufacturing enterprises. A BPM can process a batch of jobs simultaneously as long as the total size of the jobs does not exceed its capacity. A wide range of applications of BPMs can be found in the semiconductor manufacturing industry, ceramic and glass factories, steel mills and other applications [1,2,3,4,5]. Most batch scheduling problems turn out to be NP-hard, which makes them difficult to solve [6].

Many manufacturing companies are energy-intensive, and their energy consumption accounts for a large share of energy consumption in a country. In China, almost half of the total electricity energy is consumed by manufacturing. Globally, manufacturing accounts for 37 percent of global carbon emissions [7]. The huge power consumption has put enormous pressure on manufacturing enterprises and the environment, and thus it is of great significance for the manufacturing industry to save electricity costs and to reduce the greenhouse gas emissions.

Replacing power-hungry equipment with new equipment that saves energy is the easiest way, but the cost of buying new equipment is often too high to afford for small- and medium-sized enterprises. Another approach is to optimize production planning and scheduling. Planning and scheduling can effectively reduce the energy consumption of enterprises in a short time with little investment. Therefore, scheduling has become the primary choice of more and more enterprises to reduce electricity consumption.

In the existing research, Saberi-Aliabad et al. [8] studied an unrelated parallel machine scheduling problem under time-of-use electricity tariffs. But batch processing, which can be widely found in the manufacturing industry, is not considered by them in reality. In this paper, we consider an energy-conscious unrelated parallel BPM scheduling problem under time-of-use (TOU) tariffs with the objective of minimizing the total electricity cost (TEC). In this problem, the processing times of the jobs are different for different BPMs. The TOU pricing policy (i.e., different electricity prices for different periods) provides managers with an opportunity to save on energy costs and optimize their production activities by moving production from periods of high electricity prices to periods of low or average electricity prices. A mixed-integer linear programming model is developed for the problem, and a number of heuristics are proposed to solve this problem.

The rest of this paper is organized as follows. In Section 2, we present a literature review on unrelated parallel BPM scheduling and batch scheduling under TOU electricity tariffs. We describe the problem under study and present a mixed-integer linear programming model in Section 3. In Section 4, we describe the developed heuristics. In Section 5, we present the experimental results. In Section 6, we summarize this study and give some future research directions.

2. Literature Review

2.1. Unrelated Parallel Batch Processing Machine Scheduling

A lot of researchers have paid attention to the scheduling problem in the environment of unrelated parallel batch processing machines. Their studies deal with unrelated parallel BPM scheduling problems with different contexts. Some of them considered unrelated parallel BPMs with unit-sized jobs. Lu et al. [9] considered an unrelated parallel machine scheduling problem with deteriorating maintenance activities, parallel batch processing and deteriorating jobs. The objective was to minimize the makespan. Firstly, they formulated a mixed-integer programming model for the problem. Then, to solve the problem in a reasonable amount of time, they developed a hybrid ABC-TS algorithm by combing the artificial bee colony (ABC) and tabu search (TS) algorithms. A special case where all jobs have been assigned to machines was analyzed, and polynomial time-optimal algorithms were provided to solve it. Kong et al. [10] considered an unrelated parallel machine scheduling problem with job deterioration and proposed a hybrid SFLA-VNS algorithm combining the shuffle frog leap algorithm (SFLA) with the variable neighborhood search algorithm to solve the problem.

There are a few studies that considered unrelated parallel BPM scheduling problems with non-identical job sizes. Li et al. [11] investigated the unrelated parallel BPM problem with the objective of minimizing the makespan. A lower bound and several heuristics based on the best fit longest processing time in two groups were proposed for the problem.

Several studies consider unrelated BPM scheduling with unequal job ready times. Klemmt et al. [12] investigated an unrelated parallel BPM problem with incompatible job families and unequal ready times found in the diffusion and oxidation of semiconductor wafer fabrication facilities. To minimize the total weighted tardiness of the jobs, two solution approaches which were based on mixed-integer programming decomposition and variable neighborhood search were proposed. Shahvari and Logendran [13] developed an efficient tabu search meta-heuristic to address an unrelated parallel machine batch scheduling problem with sequence and machine-dependent set-up times, where the objective was to minimize a linear combination of the total weighted completion time and total weighted tardiness.

A number of researchers have investigated unrelated BPM scheduling problems with non-identical job sizes and ready times. Arroyo and Leung [14] proposed several heuristics based on first-fit and best-fit earliest job ready time rules to minimize the makespan. Later, Arroyo and Leung [15] provided a lower bound, a mixed-integer programming model and a meta-heuristic based on the iterated greedy algorithm for the case of different capacities. Zhou et al. [16] proposed a genetic algorithm based on random key encoding for the same problem as that addressed by Arroyo and Leung [15]. Arroyo et al. [17] also proposed a simple and effective iterated greedy algorithm to minimize the total flow time of the jobs. Shahvari and Logendran [18] presented a mathematical programming model in four layers and four bi-objective particle swarm optimization algorithms to minimize the production time and cost. Shahidi-Zadeh et al. [19] proposed a multi-objective harmony search algorithm to minimize the makespan, tardiness or earliness penalties and the purchasing cost of machines. Zarook et al. [20] proposed a mixed-integer linear programming model, two categories of the heuristic procedures and a meta-heuristic algorithm to solve the problem.

2.2. Batch Scheduling under TOU Electricity Tariffs

Many researchers have studied single-machine batch scheduling problems under TOU electricity tariffs with the objective of minimizing the makespan and TEC. Wang et al. [3] proposed an integer-programming model for a single-machine batch scheduling problem with energy cost consideration and used an exact $ϵ$ constraint method and two heuristic methods to obtain the Pareto fronts. Zhang et al. [21] proposed a continuous-time mixed-integer linear programming model for speed-scaling single-machine batch scheduling and two improved heuristics based on the model. Cheng et al. [22] considered a single-machine batch scheduling problem with machine on and off switching under TOU tariffs and proposed a bi-objective mixed-integer linear programming formulation and a heuristic-based $ϵ$ constraint method. Cheng et al. [23] proposed two mixed-integer linear programming models to minimize the TEC for single-machine batch scheduling under TOU tariffs, which were based on time index formulation and time interval formulation. Later, Wu et al. [24] developed two fast, new $ϵ$ constraint-based constructive heuristic algorithms to simultaneously minimize the TEC and makespan. Zhou et al. [25] developed a mathematical formulation for a single-machine batch scheduling problem with dynamic job arrival times. Then a three-stage algorithm that used a particle swarm optimization algorithm to find a job sequence, two constructive heuristics to group a sequence of jobs into batches and the earliest ready time rule to obtain a schedule were presented to find the Pareto front.

A few studies investigated energy-oriented flow shop batch scheduling problems under TOU electricity tariffs. Liu et al. [26] studied a bi-objective three-stage hybrid flow shop scheduling problem, where the first two processing stages consisted of non-identical parallel machines and the last processing stage was made up of a batch processing machine. They proposed an integer programming model and then developed a model-based heuristic and a bi-objective differential evolution algorithm to solve the problem. Zheng et al. [27] presented a multi-objective hybrid ant colony optimization algorithm and a mixed-integer programming model to minimize the makespan and TEC.

A few papers addressed the energy-conscious scheduling problem of BPMs in parallel. Zhou et al. [7] proposed a mixed-integer nonlinear programming model and a multi-objective differential evolution algorithm to minimize the makespan and TEC. Qian et al. [28] extended the problem to the case of arbitrary job sizes and developed a multi-objective evolutionary algorithm based on adaptive clustering. To the best of our knowledge, there is no study that considers energy-efficient unrelated parallel BPM scheduling. This paper is the first to investigate the problem and proposes a mixed-integer linear programming model and a number of heuristic algorithms for the problem.

3. Problem Description and Model

In this section, the energy-efficient unrelated parallel BPM scheduling problem under TOU electricity tariffs is described, and then the notation and a mixed-integer linear programming model are presented.

3.1. Problem Description

• There are n jobs to be processed on m unrelated parallel BPMs. The processing time of a job depends on the machine processing it, and let $p_{ji}$ denote the processing time of job j on machine i. All jobs have unit sizes, and the maximum capacity of the machines is B (i.e., a machine can process up to B jobs at a time). The power of machine i is denoted by ${\rho }_i$.
• Once a batch starts to be processed on a machine, it cannot be terminated, and no jobs can be added to the machine until processing is finished. The processing time of a batch on a machine is determined by the longest processing time of the jobs in the batch for the machine.
• TOU electricity tariffs are used in this paper (i.e., the electricity price of each period is not the same). An allowable scheduling horizon T is considered, which consists of K periods. The duration and electricity price of period k are denoted by $c_k$ and $T_k$, respectively. The scheduling problem is to group the jobs into batches, assign the batches to the machines and allocate time to the batches on each machine in order to minimize the total electricity cost within the scheduling horizon.

3.2. Mathematical Model

The parameters are as follows: n is the number of jobs, m, is the number of machines, K is the number of periods, $p_{ji}$ is the processing time of job j on machine i, ${\rho }_i$ is the power of machine i, $c_k$ is the electricity price of period k, $T_k$ is the duration of period k, B is the capacity of all machines, and M is a big enough positive number.

The decision variables are as follows: $x_{jb}$ is one if job j is assigned to batch b and is zero otherwise, $t_{bi}$ is the processing time of batch b on machine i, $a_{bik}$ denotes the real amount of processing time of batch b for machine i in period k, $y_{bik}$ is one if batch b is processed on machine i in period k and is zero otherwise, and $w_{bi}$ is one if batch b is processed for machine i and is zero otherwise.

The mixed-integer linear programming (MILP) model is formulated as follows.

The objective of Equation (1) is to minimize the total electricity cost:

$$MinTEC=\sum _{b=1}^n\sum _{i=1}^m\sum _{k=1}^K{\rho }_i{c}_k{a}_{bik}$$

(1)

The constraint in Equation (2) ensures that each job can be assigned to only one batch:

$$\sum _{b=1}^n{x}_{jb}=1j=1,\dots ,n.$$

(2)

The constraint in Equation (3) ensures that there are no more than B jobs in a batch:

$$\sum _{j=1}^n{x}_{jb}\le Bb=1,\dots ,n.$$

(3)

The constraints in Equations (4) and (5) denote that the processing time of batch b for machine i is equal to the longest processing time of the jobs in the batch if batch b is processed on machine i (i.e., $w_{bi}=1$) and is equal to zero otherwise:

$$t_{bi}\ge p_{ji}{x}_{jb}-M(1-w_{bi})j=1,\dots ,n;b=1,\dots ,n;i=1,\dots ,m.$$

(4)

$$t_{bi}\le M{w}_{bi}b=1,\dots ,n;i=1,\dots ,m.$$

(5)

The constraint in Equation (6) ensures that the total processing time of batch b in all periods on machine i is equal to its processing time for the machine:

$$\sum _{k=1}^K{a}_{bik}=t_{bi}b=1,\dots ,n;i=1,\dots ,m.$$

(6)

The constraint in Equation (7) forces the processing time of batch b in period k for machine i to be zero if the batch is not processed in the period on the machine (i.e., $y_{bik}=0$):

$$a_{bik}\le T_k{y}_{bik}b=1,\dots ,n;i=1,\dots ,m;k=1,\dots ,K.$$

(7)

The constraint in Equation (8) ensures that the total processing time of all batches in period k on machine i is not more than the length of the period:

$$\sum _{b=1}^n{a}_{bik}\le T_{k}i=1,\dots ,m;k=1,\dots ,K.$$

(8)

The constraint in Equation (9) means that if a batch is processed across more than one period, then these periods must be adjacent:

$$\sum _{l=k+2}^K{y}_{bil}\le K(1-y_{bik}+y_{bi(k+1)})b=1,\dots ,n;i=1,\dots ,m;k=1,\dots ,K-2.$$

(9)

The constraint in Equation (10) means that batch b should occupy the whole period k for machine i if the batch is processed in both period k − 1 and period k + 1 on the machine:

$$a_{bik}\ge T_k(y_{bi(k-1)}+y_{bi(k+1)}-1)b=1,\dots ,n;i=1,\dots ,m;k=2,\dots ,K-1.$$

(10)

The constraint in Equation (11) indicates that, at most, one batch can arbitrarily cross two adjacent periods on a machine:

$$y_{bik}+y_{bi(k+1)}+y_{b^{\prime }ik}+y_{b^{\prime }i(k+1)}\le 31\le b<b^{\prime }\le n;i=1,\dots ,m;k=1,\dots ,K-1.$$

(11)

The constraint in Equation (12) means that if batch b is not processed on machine i, then it cannot be processed in any periods on the machine:

$$K{w}_{bi}\ge \sum _{k=1}^K{y}_{bik}b=1,\dots ,n;i=1,\dots ,m.$$

(12)

The constraint in Equation (13) denotes that each batch can be assigned to only one machine:

$$\sum _{i=1}^m{w}_{bi}=1b=1,\dots ,n.$$

(13)

The constraint in Equation (14) defines the ranges of the decision variables:

$$\begin{array}{c}\hfill x_{jb},y_{bik},w_{bi}\in \{0,1\},t_{bi}\ge 0,a_{bik}\ge 0\\ \hfill j=1,\dots ,n;b=1,\dots ,n;i=1,\dots ,m;k=1,\dots ,K.\end{array}$$

(14)

4. Heuristic Algorithms

The energy-efficient unrelated parallel BPM scheduling problem is strongly NP-hard, and thus it is necessary to develop heuristics to solve the problem in a reasonable computation time. The studied problem consists of several interdependent subproblems. There are two ways to solve the problem. The first way is batching jobs, assigning the batches to machines and allocating time to the batches for each machine, and the other is assigning jobs to machines, batching the jobs on each machine and allocating time to each batch for each machine. This paper develops a group of six heuristics with the first method and a group of three heuristics with the other method. The details of the two groups of heuristics are described below.

4.1. The First Group of Heuristics

In this group, three modified heuristics based on the full-batch longest processing time (FBLPT) algorithm [29] are presented to group the jobs into batches. Then, two heuristics, the shortest completion time (SCT) and minimum electricity cost (MEC), are developed to assign the batches to the machines, and finally an integer linear programming model is developed to allocate time to the batches for each machine.

The jobs are divided into batches (the last batch may have fewer than B jobs) as the heuristics FBLPT_max, FBLPT_avg and FBLPT_min:

• Let $t_j^{max}$, $t_j^{avg}$ and $t_j^{min}$ denote the longest, average and shortest processing time of job j on all machines, respectively. The jobs are arranged in non-increasing order of $t_j^{max}$ in FBLPT_max, $t_j^{avg}$ in FBLPT_avg and $t_j^{min}$ in FBLPT_min.
• According to the order of the jobs obtained in Step 1, every B jobs are grouped into a batch starting from the first job. Note that the last batch may contain less than B jobs. Finally a list of batches is created.

We used a 10 job problem instance with two machines, as is shown in

Table 1. A 10 job problem instance with two machines.

Job j	1	2	3	4	5	6	7	8	9	10
$t_{j1}$	1	2	7	1	4	1	7	9	7	3
$t_{j2}$	8	3	5	8	2	8	7	1	6	2
$t_j^{max}$	8	3	7	8	4	8	7	9	7	3

, to illustrate the FBLPT_max algorithm. The capacity of the machines was assumed to be two. According to Step 1, the job sequence was {8,1,4,6,3,7,9,5,2,10}. The batches generated according to Step 2 are then presented in

Table 2. The batches generated by heuristic FBLPT_max.

Batch	B1	B2	B3	B4	B5
Job	1,8	4,6	3,7	5,9	2,10
$t_{b1}$	9	1	7	7	3
$t_{b2}$	8	8	7	6	3

.

After the jobs were batched, the SCT and MEC heuristics were used to assign the batches to the machines. The two heuristics are described in detail below.

The heuristic SCT was designed to assign a batch to the machine for which the completion time of the batch was the earliest. The heuristic is described below:

• Select the batch at the head of the batch list.
• Calculate the completion times of the batches for each machine and assign them to the machines that enable them to have the shortest completion time. Repeat Step 1 until all batches have been assigned to a machine.

The MEC heuristic was designed to assign a batch to the machine on which the electricity cost for processing the batch was the least under the preemptive circumstance. The MEC heuristic is described below:

• Select the batch at the head of the batch list.
• Preemptive processing is considered. Calculate the lowest electricity cost of the batch for each machine. Assign the batch to the machine for which the electricity cost of the batch is the lowest. Remove the periods occupied by the batch. Repeat Step 1 until all batches have been assigned to a machine.

We used the generated batches in Table 2 to illuminate the SCT and MEC heuristics. The powers of machines 1 and 2 were three and two, respectively. According to the SCT heuristic, the completion times of batch B1 on machines 1 and 2 were nine and eight, respectively, and thus batch B1 was assigned to machine 2. Next, the completion times of batch B2 on machines 1 and 2 were 1 and 16, respectively, and thus batch B2 was assigned to machine 1. The other batches were assigned in a similar way, and the final batch assignments are shown in Figure 1. The durations and prices of the periods are shown at the bottom of the figure. According to the MEC heuristic, the lowest electricity costs of batch B1 on machines 1 and 2 were 63 and 36, respectively, and thus batch B1 was assigned to machine 2. Next, the lowest electricity costs of batch B2 on machines 1 and 2 were 6 and 74, respectively, and thus batch B2 was assigned to machine 1. The other batches were assigned in a similar way, and the final batch assignments are shown in Figure 2.

After the batches were assigned to the set of BPMs, the problem was to allocate time to the batches on each individual BPM. We could regard a batch as an independent job, and then the problem was transformed into a set of m individual machine scheduling problems under TOU electricity tariffs with the objective of minimizing the TEC. To solve the single machine versions, an integer programming model is proposed.

The parameters are as follows: v is the number of batches assigned to a machine, $\rho$ is the machine power, and $t_b$ is the processing time of batch b.

The decision variables are as follows: $w_{bk}$ is one if batch b is processed in period k and is zero otherwise, and $x_{bk}$ is the real amount of processing time of batch b in period k.

The integer programming model (P1) for the single machine version is as follows.

The objective of Equation (15) is to minimize the total electricity cost of the machine:

$$Min\sum _{b=1}^v\sum _{k=1}^K\rho c_k{x}_{bk}$$

(15)

The constraint in Equation (16) ensures that the total processing time of batch b in all periods for the machine is equal to its processing time:

$$\sum _{k=1}^K{x}_{bk}=t_{b}b=1\dots ,v.$$

(16)

The constraint in Equation (17) forces the processing time of batch b in period k to be zero if the batch is not processed in the period (i.e., $w_{bk}$ = 0):

$$x_{bk}\le T_k{w}_{bk}b=1\dots ,v;k=1,\dots ,K.$$

(17)

The constraint in Equation (18) ensures that the total processing time of all batches in period k is not more than the length of the period:

$$\sum _{b=1}^v{x}_{bk}\le T_{k}k=1,\dots ,K.$$

(18)

The constraint in Equation (19) means that if a batch is processed across more than one period, then these periods must be adjacent:

$$\sum _{l=k+2}^K{w}_{bl}\le K(1-w_{bk}+w_{b(k+1)})b=1\dots ,v;k=1,\dots ,K-2.$$

(19)

The constraint in Equation (20) means that batch b should occupy the whole period k if the batch is processed in both period $k-1$ and period k + 1:

$$x_{bk}\ge T_k(w_{b(k-1)}+w_{b(k+1)}-1)b=1\dots ,v;k=2,\dots ,K-1.$$

(20)

The constraint in Equation (21) indicates that, at most, one batch can arbitrarily cross two adjacent periods for the machine:

$$w_{bk}+w_{b(k+1)}+w_{b^{\prime }k}+w_{b^{\prime }(k+1)}\le 31\le b<b^{\prime }\le n;k=1,\dots ,K-1.$$

(21)

The constraint in Equation (22) defines the ranges of the decision variables:

$$x_{bk}\ge 0,w_{bk}\in \{0,1\}b=1\dots ,v;k=1,\dots ,K.$$

(22)

4.2. The Second Group of Heuristics

In this group, three heuristics, the shortest processing time (SPT), minimum difference of power consumption (MDPC) and minimum difference of electricity cost (MDEC) are presented to assign the jobs to the machines. Then, the FBLPT rule is used to batch the jobs for each machine, and finally the P1 model proposed in Section 4.1 is used to solve a set of single-machine scheduling problems.

The SPT heuristic is found as detailed below:

• Arrange the jobs in some arbitrary order.
• Select the job at the head of the list and assign it to the machine with the shortest processing time. Repeat this step until all jobs are assigned to machines.

The MDPC heuristic is found as detailed below:

• Calculate the power consumption $e_{ji}$ of job j for each machine i, and let ${\phi }_j$ denote the difference between the two smallest values $e_{ji}$ and $i=1,\dots ,m$. Arrange the jobs in non-increasing order of ${\phi }_j$.
• Preemptive processing is considered. Select the job at the head of the list, and calculate the lowest electricity cost of the job on each machine. Assign the job to the machine for which the electricity cost of the job is the lowest. Remove the periods occupied by the job. Repeat this step until all jobs have been assigned to machines.

The MDEC heuristic is found as detailed below:

• Preemptive processing is considered. Calculate the lowest electricity cost $E{C}_{ji}$ of job j for each machine i, and let ${\psi }_j$ denote the difference between the two smallest values $E{C}_{ji}$ and $i=1,\dots ,m$. Select the job with the largest ${\psi }_j$ value.
• Assign the job to the periods for the machine with the lowest electricity cost. Remove the job and the occupied time for this machine. Return to Step 1 until all jobs are assigned to machines.

We used the instance in Table 1 to illustrate the three heuristics. The powers of machines 1 and 2 were three and two, respectively. The durations and prices of the periods are shown in

Table 3. The durations and prices of periods.

Periods	1	2	3	4	5	6	7	8	9	10
Duration	7	3	5	3	3	2	8	3	5	1
Price	0.4	0.8	1.3	0.8	1.3	0.8	0.4	0.8	1.3	0.8

. The processing time of job 1 was the shortest when processed on machine 1, and thus job 1 was assigned to machine 1 according to the SPT. The other jobs were assigned in a similar way. According to the MDPC, we calculated the ${\phi }_j$ of all 10 jobs, and {${\phi }_1,\dots ,{\phi }_{10}$} were {13,0,11,13,8,13,7,25,9,5}. We sorted the jobs according to ${\phi }_j$, and the job order was {8,1,4,6,3,9,5,7,10,2}. Therefore, job 8 was selected first according to the job order. The lowest electricity costs of job 8 on machines 1 and 2 were 10.8 and 0.8, respectively, and thus job 8 was assigned to machine 2. Next, we removed the time occupied by job 8 on machine 2 and calculated the lowest electricity costs of job 1 on machines 1 and 2, which were 1.2 and 6.4, respectively. Therefore, job 1 was assigned to machine 1. The other jobs were assigned in a similar way. According to the MDEC, we calculated ${\psi }_j$ for all jobs, and {${\psi }_1,\dots ,{\psi }_{10}$} were {5.2,0,4.4,5.2,3.2,5.2,2.8,10,3.6,2}. Here, ${\psi }_8$ was the largest one, and thus job 8 was selected first. The lowest electricity costs of job 8 on machines 1 and 2 were 10.8 and 0.8, respectively, and thus job 8 was assigned to machine 2. After job 8 was assigned, we removed the time occupied by it on machine 2. Next, we recalculated ${\psi }_j$ for the rest of the jobs, and {${\psi }_1,\dots ,{\psi }_7$,${\psi }_9$,${\psi }_{10}$} were {5.2,0,4.4,5.2,3.2,5.2,2.8,3.6,2}. Here, ${\psi }_1$ was the largest one, and thus job 1 was selected. The lowest electricity costs of job 8 on machines 1 and 2 were 1.2 and 6.4, respectively, and thus job 1 was assigned to machine 1. The other jobs were assigned in a similar way. The job assignment results of the three heuristics are shown in

Table 4. The final job assignments by the three heuristics.

Heuristics	SPT	MDPC	MDEC
Machine 1	1,2,4,6,7	1,2,4,6,9	1,2,4,6,7
Machine 2	3,5,8,9,10	3,5,7,8,10	3,5,8,9,10

.

After the jobs were assigned to the machines, we used the FBLPT rule to batch jobs for each machine. We arranged the jobs in non-increasing order of processing times, and then every B jobs were grouped into a batch starting from the first job. After the jobs were grouped into batches, the P1 model was used to allocate time to the batches for each machine.

The framework of the heuristics in group one is shown in Figure 3, and the framework of the heuristics in group two is shown in Figure 4.

5. Computational Experiments

5.1. Data Generation

The problem parameters included the job number, machine number, machine capacity, machine powers and processing times of the jobs. Five levels of the number of jobs and two levels of the number of machines were considered in our instances (i.e., n = 20, 50, 100, 200, 300 and m = 2, 3). The machine power ${\rho }_i$ was randomly generated in {2,3}, and the machine capacity B was fixed to three. The processing times $p_{ji}$ of the jobs on the machines were randomly generated from a discrete uniform distribution [1,10]. The production horizon T was set by Equation (23). The TOU electricity prices used in this study are described in

Table 5. TOU electricity prices.

Period Type	Electricity Price	Time Periods
On-peak	1.3 CNY/kWh	10:00 a.m.–3:00 p.m.
		6:00 p.m.–9:00 p.m.
Mid-peak	0.8 CNY/kWh	7:00 a.m.–10:00 a.m.
		3:00 p.m.–6:00 p.m.
		9:00 p.m.–11:00 p.m.
Off-peak	0.4 CNY/kWh	11:00 p.m.–7:00 a.m.

.

$$T=\lceil n/B\rceil \times max\left\{p_{ji}\right\}$$

(23)

All the algorithms were coded in Python. A Windows 11 computer with an AMD Ryzen 7 4800U, 1.8 GHz processor and 16 GB of RAM was used to run the experiments.

5.2. Comparison between the MILP Model and the Heuristics

In this subsection, we use CPLEX 12.7 to solve the MILP model proposed in Section 3. The time limit for CPLEX was set to 3600 s, and one thread was used when solving this model. The MILP model was compared with the second group of three heuristics. In these heuristics, the P1 model was solved using CPLEX with a time limit of 600 s.

Table 6. Results obtained by the MILP and the second group of three heuristics for two machine instances.

n	No.	MILP				SPT			MDPC			MDEC
						FBLPT
						P1
		TEC	${\mathit{C}}_{\mathit{max}}$	Time (s)	Gap (%)	TEC	${\mathit{C}}_{\mathit{max}}$	Time (s)	TEC	${\mathit{C}}_{\mathit{max}}$	Time (s)	TEC	${\mathit{C}}_{\mathit{max}}$	Time (s)
20	1	28.4	53	412.16	0.00	29.6	54	0.04	29.2	53	0.03	29.2	53	0.03
	2	29.6	53	79.75	0.00	31.2	54	0.03	34.0	56	0.03	32.0	53	0.03
	3	25.6	55	123.28	0.00	28.8	56	0.03	31.2	56	0.03	28.0	57	0.03
	4	33.2	54	175.43	0.00	40.0	57	0.04	44.8	57	0.03	40.8	57	0.03
	5	25.2	54	174.88	0.00	28.0	57	0.03	34.4	57	0.03	32.4	57	0.03
50	1	66.4	151	3600.06	50.00	70.0	170	0.20	74.0	170	0.20	67.2	170	0.20
	2	72.0	153	3600.06	77.79	78.8	170	0.23	80.8	168	0.20	74.4	170	0.21
	3	72.4	151	3600.01	76.20	74.4	147	0.20	79.6	170	0.20	75.6	147	0.21
	4	-	-	-	-	66.0	170	0.22	72.0	170	0.22	63.2	170	0.21
	5	70.0	168	3600.07	78.29	73.2	170	0.20	74.4	170	0.19	71.6	170	0.21
100	1	286.8	340	3600.19	97.77	148.4	340	1.68	156.8	338	1.74	145.6	340	1.58
	2	-	-	-	-	144.0	338	1.52	152.8	317	1.56	140.8	340	1.51
	3	-	-	-	-	138.0	339	1.53	146.4	339	1.75	136.4	338	1.58
	4	-	-	-	-	130.0	340	1.47	141.6	338	1.75	128.4	339	1.57
	5	-	-	-	-	114.8	339	1.42	127.6	340	1.65	116.0	339	1.47

shows the results obtained by the MILP model and the three heuristics for instances with 20, 50, or 100 jobs and 2 machines. Column one represents the number of jobs, and column two represents the instance number. Columns 3–6 give the $TEC$, $C_{max}$, time (s) and gap (%) values obtained by the MILP, respectively, and columns 7–15 give the $TEC$, $C_{max}$ and time (s) values obtained by the three heuristics, while “-” denotes that CPLEX could not find a feasible solution within the time limit. The best value is shown in bold. It can be seen from Table 6 that all the 20 job instances could be solved to optimality by the MILP. The $TEC$ obtained by the SPT-FBLPT-P1 heuristic for the 20 job instances was a bit worse than that of the optimal solution. For 4 out of the 5 instances with 50 jobs, the $TEC$ obtained by the MILP was the best, and the MDEC-FBLPT-P1 heuristic performed nearly as well as the MILP. The MILP did not find a feasible solution for the other 50 job instance. The MILP could not solve the 50 job instances optimally within 3600 s. The MILP could not obtain feasible solutions for the 100 job instances, except for one. The computational time of all the heuristics was quite small (less than 2 s even for a 100 job instance).

Table 7. Results obtained by the MILP and the second group of three heuristics for three-machine instances.

n	No.	MILP				SPT			MDPC			MDEC
						FBLPT
						P1
		TEC	${\mathit{C}}_{\mathit{max}}$	Time (s)	Gap (%)	TEC	${\mathit{C}}_{\mathit{max}}$	Time (s)	TEC	${\mathit{C}}_{\mathit{max}}$	Time (s)	TEC	${\mathit{C}}_{\mathit{max}}$	Time (s)
20	1	28.0	53	160.52	0.00	30.0	30	0.04	33.2	31	0.05	33.2	31	0.04
	2	26.8	55	256.05	0.00	32.0	56	0.03	32.0	57	0.05	34.4	56	0.04
	3	24.4	55	184.98	0.00	28.8	56	0.04	30.0	56	0.04	30.0	56	0.04
	4	25.6	49	156.01	0.00	32.8	56	0.03	29.6	57	0.04	32.8	57	0.04
	5	29.6	57	235.00	0.00	35.6	56	0.05	40.4	56	0.05	32.8	56	0.04
50	1	60.4	168	3600.03	66.91	64.0	170	0.23	63.2	170	0.20	65.2	170	0.24
	2	54.0	149	3600.06	59.11	55.6	170	0.23	61.6	55	0.21	58.0	55	0.25
	3	49.2	168	3600.04	69.69	54.8	55	0.21	52.4	169	0.21	51.6	169	0.21
	4	60.0	169	3600.06	72.02	68.4	79	0.24	68.8	152	0.24	65.6	170	0.23
	5	63.2	147	3600.05	66.99	65.2	170	0.21	74.0	170	0.23	70.8	170	0.22
100	1	-	-	-	-	101.2	340	1.46	102.0	340	1.44	102.0	340	2.28
	2	339.5	340	3602.11	98.00	93.2	340	1.55	95.6	339	1.54	93.2	340	2.12
	3	-	-	-	-	111.6	340	1.52	113.6	340	1.70	112.4	336	2.37
	4	-	-	-	-	108.0	340	1.62	110.0	339	1.39	108.8	340	2.06
	5	-	-	-	-	102.0	340	1.47	104.0	340	1.37	105.6	339	2.29

provides the results for the instances with three machines. It can be seen from the table that all the 20 job instances were optimally solved by the MILP. None of the 50 job instances were solved to optimality by the MILP within 3600 s. The MILP could find a feasible solution for only one out of the five instances when the number of jobs was 100. The $TEC$ obtained by the three heuristics was worse than that obtained by the MILP for the instances with 20 and 50 jobs. However, the three heuristics performed better than the MILP as the number of jobs increased to 100. All the heuristics were quite quick compared with the MILP.

5.3. Comparison of the Heuristics

This subsection compares the nine heuristics proposed in this paper with each other.

Table 8. The average $TEC$ and $C_{max}$ obtained by the nine heuristics.

m	n	FBLPT_max				FBLPT_avg				FBLPT_min				SPT		MDPC		MDEC
		SCT		MEC		SCT		MEC		SCT		MEC		FBLPT
		P1				P1				P1				P1
		TEC	${\mathit{C}}_{\mathit{max}}$	TEC	${\mathit{C}}_{\mathit{max}}$	TEC	${\mathit{C}}_{\mathit{max}}$	TEC	${\mathit{C}}_{\mathit{max}}$	TEC	${\mathit{C}}_{\mathit{max}}$	TEC	${\mathit{C}}_{\mathit{max}}$	TEC	${\mathit{C}}_{\mathit{max}}$	TEC	${\mathit{C}}_{\mathit{max}}$	TEC	${\mathit{C}}_{\mathit{max}}$
2	20	46.5	56.2	43.6	56.2	44.7	56.4	39.8	57.1	44.4	56.7	39.4	56.6	29.5	54.5	32.1	53.1	30.4	54.4
	50	122.8	166.4	119.4	168.0	121.9	169.6	118.4	169.8	117.0	167.9	108.9	169.7	72.2	165.9	76.7	166.2	70.6	165.9
	100	247.8	339.9	240.1	339.9	248.4	339.6	232.0	339.9	234.3	339.7	221.8	340.0	136.2	337.8	337.0	329.8	137.0	339.6
	200	482.7	655.1	472.1	656.1	469.4	655.1	442.4	656.1	437.2	655.4	403.7	657.0	260.2	654.3	275.6	652.7	260.0	652.6
	300	728.8	992.0	696.5	992.0	700.0	991.1	664.3	991.8	667.2	991.4	635.7	992.4	387.6	990.6	415.0	989.4	378.8	987.3
3	20	55.0	55.6	51.0	56.5	51.4	55.1	47.8	57.5	53.7	56.4	44.8	56.9	30.0	45.8	31.3	46.4	31.1	48.5
	50	137.5	157.7	120.6	166.4	125.4	161.1	109.7	168.0	129.1	162.5	111.3	166.2	63.8	140.2	66.2	154.7	65.3	152.8
	100	262.2	339.6	225.6	339.6	242.1	339.5	199.3	339.8	230.4	339.6	193.8	339.8	107.0	339.3	108.6	339.4	107.6	339.1
	200	526.2	655.6	448.6	655.4	489.4	650.6	400.9	655.8	476.7	655.3	397.8	655.2	222.4	652.7	225.2	627.6	224.9	652.3
	300	796.9	991.6	690.2	991.3	739.4	991.4	611.0	991.6	715.0	991.2	608.0	991.7	334.2	990.4	338.3	990.2	337.7	989.5

shows the results obtained by the heuristics. For each combination of a machine number and job number, 10 instances were randomly generated, and the average results of the 10 instances obtained by a heuristic were reported. In Table 8, columns one and two denote the machine number and job number, respectively, and the other columns present the average $TEC$ and $C_{max}$ values from the nine heuristics. It can be seen from Table 8 that the $TEC$ from the second group of three heuristics was better than that of the first group of six heuristics. Among the first group of heuristics, the ones using the MEC algorithm to assign batches to machines were superior than the ones using the SCP algorithm for all the instances. Among the second group of heuristics, the SPT-FBLPT-P1 and MDEC-FBLPT-P1 heuristics were always the best two heuristics for all the instances. The difference between the performance of the SPT-FBLPT-P1 and MDEC-FBLPT-P1 was quite small.

Table 9. The average run times of the heuristics.

m	n	FBLPT_max		FBLPT_avg		FBLPT_min		SPT	MDPC	MDEC
		SCT	MEC	SCT	MEC	SCT	MEC	FBLPT
		P1		P1		P1		P1
2	20	0.1	0.1	0.1	0.1	0.1	0.0	0.0	0.0	0.0
	50	0.5	1.6	0.4	0.6	0.3	0.7	0.2	0.2	0.2
	100	4.5	20.3	82.9	40.1	2.64	13.6	1.6	1.7	1.6
	200	307.6	319.4	244.0	177.0	84.9	376.4	17.1	17.9	17.1
	300	659.6	437.9	265.3	556.1	183.3	572.1	77.4	94.0	89.1
3	20	0.1	0.1	0.1	0.1	0.1	0.1	0.0	0.0	0.0
	50	0.3	0.3	0.4	11.7	0.4	0.6	0.2	0.2	0.2
	100	1.6	61.9	1.6	18.4	1.7	67.02	1.5	1.5	2.2
	200	18.2	139.6	16.1	190.4	18.5	370.9	15.1	15.0	15.2
	300	86.0	256.7	77.7	388.6	84.0	504.6	64.0	52.2	52.3

shows the average run times (s) of the nine heuristics. It can be seen from the table that the average run times of the second group of heuristics were lower than those of the first group of heuristics. Note that the number of machines has an impact on the run time of an algorithm that reduces as the number of machines increases.

For the second group of algorithms with better performance, we conducted experiments for five-machine instances. The results are shown in

Table 10. Results obtained by the second group of heuristics for five-machine instances.

n	SPT			MDPC			MDEC
	FBLPT
	P1
	TEC	Cmax	Time (s)	TEC	Cmax	Time (s)	TEC	Cmax	Time (s)
20	22.8	11.7	0.05	25.1	22.0	0.04	24.5	22.0	0.04
50	45.5	35.0	0.23	47.2	105.5	0.22	47.5	80.3	0.28
100	73.2	54.5	1.40	74.4	207.5	1.41	74.8	207.4	1.58
200	155.2	446.0	14.35	158.1	520.4	18.86	155.0	496.7	18.71
300	218.0	804.1	76.49	219.6	989.1	77.93	219.6	987.6	80.32

, and it can be seen that all three heuristics could solve the maximum scale instance with 5 machines and 300 jobs within about 80 s. It was proven that the second group of heuristics also had great potential for solving larger-scale problems. Among the three heuristics, the performance of SPT-FBLPT-P1 was always the best for almost all instances.

6. Conclusions

This paper addressed the scheduling problem of unrelated parallel batch processing machines under TOU electricity prices with the objective of minimizing the total electricity cost. We proposed a mixed-integer programming model and two groups of heuristics in different ways. The model and heuristics were evaluated through many computational experiments. The results show that the model was quite efficient for small-scaled instances, and several of the heuristics could provide high-quality solutions for large-scaled instances in a short amount of time. Among the first group of heuristics, the ones using the MEC algorithm to assign batches to machines were superior to the ones using the SCP algorithm for all instances. Among the second group of heuristics, the SPT-FBLPT-P1 and MDEC-FBLPT-P1 heuristics were always the best two heuristics for all the instances. The difference between the performance of SPT-FBLPT-P1 and MDEC-FBLPT-P1 was rather small.

There are several directions for future research to investigate. First, the job sizes in this study were equal, and future research can consider jobs with different sizes. Second, dynamic job arrivals can be considered as well. Third, this research could be extended to flow shop and other manufacturing environments. In addition, other performance measures can also be introduced into the problem.