## 3 A Greedy Insertion Heuristic Algorithm with Multi-Stage Filtering Mechanism
### Multi-Stage Filtering Mechanism Design
: _When Condition 4 is satisfied and \(d_{k+1}=0\), job \(i\) can be directly inserted into Position 1 without moving any already inserted jobs in period \(k-1\)._  
Proof. : Since \(\exists k\in A\), \(I_{k}>0\), there must be no jobs processed within period \(k-1\). It is only possible that a job, say job \(j\), \(j<i\), is processed across periods \(k-2\) and \(k-1\). Therefore, \(x_{j,k-2}\) may be the value of the maximal remaining idle time of all mid-peak periods before inserting job \(j\). Since \(\exists k^{\prime}\in B\), \(t_{i}\leq I_{k^{\prime}}\) and \(j<i\), it is understandable that \(t_{i}\leq I_{k^{\prime}}\leq x_{j,k-2}\). Now, job \(i\) is to be inserted, it follows that \(t_{i}+x_{j,k-1}\leq x_{j,k-2}+x_{j,k-1}=t_{j}\). As mentioned earlier, the processing times of all the jobs do not exceed the duration of the shortest on-peak period, that is, \(t_{j}\leq d_{k-1}\). Hence, \(t_{i}+x_{j,k-1}\leq d_{k-1}\). If job \(i\) is processed across periods \(k\) and \(k-1\), then \(x_{i,k-1}+x_{j,k-1}\leq x_{i,k-1}+x_{i,k}+x_{j,k-1}=t_{i}+x_{j,k-1}\leq d_{k+1}\). That is, \(x_{i,k-1}+x_{j,k-1}\leq d_{k-1}\). Thus, \(d_{k-1}-x_{j,k-1}-x_{i,k-1}=I_{k-1}\geq 0\). This suggests when job \(i\) is inserted into Position 1, period \(k-1\) cannot be full. Hence, job \(i\) can be directly inserted into Position 1 without moving any already inserted jobs in period \(k-1\). Note that this property applies to Scenario 2 as well. \(\Box\)  
According to Property 2, \(cost1=p_{i}\times(x_{i,k}\times c_{A}+x_{i,k-1}\times c_{\Gamma})\) is always satisfied. In the following part, three formulas for calculating the insertion costs of Positions 1, 3, and 4 are given. \[cost1=p_{i}\times(x_{i,k}\times c_{A}+x_{i,k-1}\times c_{\Gamma}); \tag{9}\]  
Figure 2:0  
Figure 2:1  
Since \(cost1\) is always less than \(cost2\), there is no need to compute \(cost2\). Eventually, the insertion costs of all the possible positions that job \(i\) can be inserted into can be easily and directly calculated by the above formulas, and then the position with minimum insertion cost will be chosen. Scenario 2: It can be seen from Figure 5(b) that the Positions 1, 4, and 5 in Scenario 2 are the same as the Positions 1, 3, and 4 in Scenario 1. The only difference between Scenarios 1 and 2 is whether \(d_{k+1}\)\(>0\) or not (i.e., period \(k+1\) exists). Since period \(k+1\) is a mid-peak period, two additional positions need to be considered in comparison with Scenario 1. 1. A set of already inserted jobs in period \(k\) are moved to the rightmost side of the period \(k+1\), and then job \(i\) is processed across periods \(k\) and \(k-1\). 2. A set of already inserted jobs in period \(k\) should be moved to the left until job \(i\) can be processed across periods \(k\) and \(k+1\). The size of the two insertion costs (i.e., the processing electricity cost of job 6 plus the movement costs of jobs 3, 4, and 5) corresponding to Positions 2 and 3 is uncertain, because the electricity cost for processing job \(i\) is greater at Position 2 than at Position 3, while the movement costs are just the opposite. Eventually, it should calculate insertion costs of five possible positions, and then choose the position with minimum cost. Condition 5: \(\forall k\in A,I_{k}=0\). When Condition 5 is satisfied, this means all the off-peak periods are full and job \(i\) can be directly processed within a mid-peak period. Layer 3 includes Conditions 6 and 7. Most of the jobs are processed across a pair of periods consisting of a mid-peak period and an on-peak period or processed within an on-peak period in this layer. Condition 6: \(t_{i}>\max_{k^{\prime}\in B}\{I_{k^{\prime}}\}>0\). If Condition 6 is satisfied, it means job \(i\) cannot be processed within any one of the mid-peak periods, let alone off-peak periods. In other words, job \(i\) can only be used to fill the remaining idle time of a certain period with lower electricity price.