# Charging Schedule for Load Peak Minimization on Large-Scale Electric Bus Depots
## 4 Methodology and the Proposed Algorithms  
### Methodology  
There are two perspectives to scheduling with electrical buses that can be observed independent or in correlation with each other; routes scheduling (which bus takes which route) and charging schedule (when and how much do the buses charge). This paper focuses on charging schedule, considering the routes are fixed as already discussed in Section 2.3. Each bus therefore has an already defined arrival and departure time. The time in between can be used for charging. Figure 4 gives a graphical  
Figure 3: (**a**) Bus Depot Simulator user interface with the tab “Inside Depot”, showing the buses currently at the depot and their SoC and (**b**) the cosimulation procedure presented with a flowchart. representation of the mentioned timeline. The blocks represent the buses. Each bus draws power from the grid for two different tasks, charging, and preconditioning. Accordingly, there are two types of blocks, charging and preconditioning blocks. They can overlap or occur in different time slots. The length of the block is the time needed for preconditioning/charging. The height of the block is the power demand of the bus normalized based on the maximum charging power of 150 kW. There are three possible heights:  
1. Block height is 1: Bus is charging with 150 kW and there is no preconditioning. 2. Block height is 0.567: Preconditioning is active and bus is charging with 85 kW. 3. Block height is 0.433: Bus is not charging but there is preconditioning with 65 kW. Preconditioning blocks are fixed in time and cannot be moved. Charging blocks can be freely moved in the time window between the arrival and departure time. A certain number of buses in Figure 4 already arrived at the depot and started charging (white blocks in the figure). The number of buses charging simultaneously directly corresponds to the load at the depot. The problem is defined as follows; Where exactly between its arrival and departure time should the new coming bus 27 (green block in the figure) charge in order to minimize the number of buses charging simultaneously? By observing the bus charging as a non-preemptive task, it is easy to reduce the above mentioned problem to a classical job scheduling problem. Two very similar variations of this problem have already been analyzed:  
1. Scheduling with release time and deadlines on a minimum number of machines. 2. Scheduling non-preemptive jobs to minimize the peak demand. [PERSON] et al. propose several exact and approximation algorithms for solving the problem of scheduling with release time and deadlines on a minimum number of machines [25]. Although this is a very similar problem to the bus depot, there is one fundamental difference. The jobs in the bus depot problem have three possible heights and [PERSON] et al. schedule jobs with the same height. [PERSON] et al. propose an exact algorithm, an approximation and a simple heuristic for the problem of scheduling non-preemptive jobs to minimize the peak demand in a smart grid [26]. They are scheduling jobs such as household appliances (dishwasher or water heater). These jobs have different heights, which makes it similar to the depot problem. However, this study focuses on non-resizable jobs. Using the example from Figure 4, this would mean that the blocks have fixed lengths. On the other hand, in the bus depot problem, the bus charging is considered a resizable job. The charging job resizing occurs due to preconditioning as shown in Figure 5. Bus 27 arrived to the depot at 23:00 in the evening  
Figure 4: Graphical representation of the scheduling problem with several random buses already charging (white blocks) and a new bus arriving at the depot (green block). and leaves again at 06:00 the following morning. It needs to charge for 1 h and 50 min with the maximum power of 150 kW. The bus is also preconditioning from 05:00 to 06:00 in the morning, before its departure.