IL
I.R. Luik
info
Please Note
<p>This page displays the records of the person named above and is not linked to a unique person identifier. This record may need to be merged to a profile.</p>
2 records found
1
In this thesis, a model and solution approach is proposed for the employee scheduling problem in a very flexible and general setting, encountered in practice at the online supermarket Picnic Technologies. It is called the People Scheduling Service (PSS). The purpose is to make a schedule that minimizes expected costs, where the costs considered are (1) lost revenue in case workload cannot be completed; (2) excess personnel costs in case of overcapacity; (3) employee satisfaction costs incurred when a schedule is unfavorable for an employee. People are assigned to shifts, based on a workload model called "workload packages", which work as follows: at some known release time, an amount of workload (in the form of small, independently executable tasks) is made available to employees. Employees can work on the workload until some known deadline, after which any uncompleted workload is lost. The release time and deadline time do not have to correspond to the start and end time of a shift, adding flexibility to the workload planning system. On top of that, it is not assumed that perfect information is available: the amount of workload in each package is modeled as a random variable. The model, therefore, minimizes the expected costs. On the scheduling side, very few restrictive assumptions are made. Shifts may overlap and they may vary in length. Employees may have full-time or part-time contracts and even contracts where the number of hours is not fixed. The model is formulated in a manner that makes it very easy to change the scheduling constraints that are applied to a given scheduling instance. This is necessary to support operations in an international environment, where the applicable laws can differ between jurisdictions. All in all, PSS is, compared to many other scheduling solutions considered in other papers, very versatile and widely applicable. The contributions of this paper are: (1) a mixed integer linear program (MILP) formulation of the scheduling problem explained above, which is much more general and practically applicable than many other papers in the field; (2) a comparison between two solution approaches: direct application of an off-the-shelf MILP-solver and the L-shaped algorithm, which is a specific implementation of Benders’ decomposition for two-stage stochastic optimization problems; (3) a comparison between scheduling with and without workload uncertainty taken into account, resulting in a clear practical use case for stochastic optimization; (4) a comparison between the performance of SCIP (an open-source MILP-solver) and Gurobi (a commercial MILP-solver) when applied to the scheduling problem considered in this thesis. PSS has been implemented and taken into production in practice. Practical experience shows that the proposed model works well and saves a lot of manual work. The experiments in this thesis show firstly the direct MILP-solver approach is much faster than the implementation of the L-shaped algorithm proposed in this thesis when applied to most real-world test instances (on very large instances in combination with SCIP as the solver, the L-shaped algorithm is faster). Secondly, there is real value in taking uncertainty into account: schedules created without uncertainty in the model had expected costs of up to approximately 60% higher compared to the ones created with uncertainty in the model. Thirdly, Gurobi was a lot faster than SCIP. When using a direct MILP-solver approach, Gurobi never took more than five minutes to reach an optimality gap of at most 1% on any of the test instances. SCIP, on the other hand, could not reach a 1% gap in two hours for the larger test cases. In two cases, it did not even find a feasible solution at all. Further research can be done to extend the model to contain a more general workload model (for example, one where the workload can both be lost or put on a back-log when the deadline is reached), a better uncertainty model modeling more uncertainty in workload more accurately and taking other sources of uncertainty into account as well and doing more practical testing.
...
In this thesis, a model and solution approach is proposed for the employee scheduling problem in a very flexible and general setting, encountered in practice at the online supermarket Picnic Technologies. It is called the People Scheduling Service (PSS). The purpose is to make a schedule that minimizes expected costs, where the costs considered are (1) lost revenue in case workload cannot be completed; (2) excess personnel costs in case of overcapacity; (3) employee satisfaction costs incurred when a schedule is unfavorable for an employee. People are assigned to shifts, based on a workload model called "workload packages", which work as follows: at some known release time, an amount of workload (in the form of small, independently executable tasks) is made available to employees. Employees can work on the workload until some known deadline, after which any uncompleted workload is lost. The release time and deadline time do not have to correspond to the start and end time of a shift, adding flexibility to the workload planning system. On top of that, it is not assumed that perfect information is available: the amount of workload in each package is modeled as a random variable. The model, therefore, minimizes the expected costs. On the scheduling side, very few restrictive assumptions are made. Shifts may overlap and they may vary in length. Employees may have full-time or part-time contracts and even contracts where the number of hours is not fixed. The model is formulated in a manner that makes it very easy to change the scheduling constraints that are applied to a given scheduling instance. This is necessary to support operations in an international environment, where the applicable laws can differ between jurisdictions. All in all, PSS is, compared to many other scheduling solutions considered in other papers, very versatile and widely applicable. The contributions of this paper are: (1) a mixed integer linear program (MILP) formulation of the scheduling problem explained above, which is much more general and practically applicable than many other papers in the field; (2) a comparison between two solution approaches: direct application of an off-the-shelf MILP-solver and the L-shaped algorithm, which is a specific implementation of Benders’ decomposition for two-stage stochastic optimization problems; (3) a comparison between scheduling with and without workload uncertainty taken into account, resulting in a clear practical use case for stochastic optimization; (4) a comparison between the performance of SCIP (an open-source MILP-solver) and Gurobi (a commercial MILP-solver) when applied to the scheduling problem considered in this thesis. PSS has been implemented and taken into production in practice. Practical experience shows that the proposed model works well and saves a lot of manual work. The experiments in this thesis show firstly the direct MILP-solver approach is much faster than the implementation of the L-shaped algorithm proposed in this thesis when applied to most real-world test instances (on very large instances in combination with SCIP as the solver, the L-shaped algorithm is faster). Secondly, there is real value in taking uncertainty into account: schedules created without uncertainty in the model had expected costs of up to approximately 60% higher compared to the ones created with uncertainty in the model. Thirdly, Gurobi was a lot faster than SCIP. When using a direct MILP-solver approach, Gurobi never took more than five minutes to reach an optimality gap of at most 1% on any of the test instances. SCIP, on the other hand, could not reach a 1% gap in two hours for the larger test cases. In two cases, it did not even find a feasible solution at all. Further research can be done to extend the model to contain a more general workload model (for example, one where the workload can both be lost or put on a back-log when the deadline is reached), a better uncertainty model modeling more uncertainty in workload more accurately and taking other sources of uncertainty into account as well and doing more practical testing.
In this thesis different mechanisms of stabilizing a power grid are tested. The grid dynamics are modelled by a second order extension of the Kuramoto coupled oscillator model, also known as the swing equation. First we prove basic properties of the model such as periodicity and existence and uniqueness. Then
we explore the properties of simple network topologies governed by the Kuramoto model. Finally we proceed to the testing of stabilization mechanisms. The stabilization mechanisms tested are (a) increasing the capacity of the power grid lines (b) implementing time delayed feedback mechanisms on the nodes and (c) decentralizing the power generation in the network. Moreover, we test whether examples of Braess’ paradox, which states that adding an edge in a network can locally improve flow but globally cause congestion, can be found in a small network. Increasing the capacity of the power grid lines and implementing time delayed feedback are shown to have a positive effect on the stability of the grid. For a specific grid (the German power grid) it is shown that replacing a large power generator by many smaller generators can indeed have a positive effect on the stability, but this result has mediocre statistical certainty (p-value of 0:16). No instances have been found where removing a line from the network has a positive effect (Braess’ paradox), however this is insufficient to conclude that no such instances exist. ...
we explore the properties of simple network topologies governed by the Kuramoto model. Finally we proceed to the testing of stabilization mechanisms. The stabilization mechanisms tested are (a) increasing the capacity of the power grid lines (b) implementing time delayed feedback mechanisms on the nodes and (c) decentralizing the power generation in the network. Moreover, we test whether examples of Braess’ paradox, which states that adding an edge in a network can locally improve flow but globally cause congestion, can be found in a small network. Increasing the capacity of the power grid lines and implementing time delayed feedback are shown to have a positive effect on the stability of the grid. For a specific grid (the German power grid) it is shown that replacing a large power generator by many smaller generators can indeed have a positive effect on the stability, but this result has mediocre statistical certainty (p-value of 0:16). No instances have been found where removing a line from the network has a positive effect (Braess’ paradox), however this is insufficient to conclude that no such instances exist. ...
In this thesis different mechanisms of stabilizing a power grid are tested. The grid dynamics are modelled by a second order extension of the Kuramoto coupled oscillator model, also known as the swing equation. First we prove basic properties of the model such as periodicity and existence and uniqueness. Then
we explore the properties of simple network topologies governed by the Kuramoto model. Finally we proceed to the testing of stabilization mechanisms. The stabilization mechanisms tested are (a) increasing the capacity of the power grid lines (b) implementing time delayed feedback mechanisms on the nodes and (c) decentralizing the power generation in the network. Moreover, we test whether examples of Braess’ paradox, which states that adding an edge in a network can locally improve flow but globally cause congestion, can be found in a small network. Increasing the capacity of the power grid lines and implementing time delayed feedback are shown to have a positive effect on the stability of the grid. For a specific grid (the German power grid) it is shown that replacing a large power generator by many smaller generators can indeed have a positive effect on the stability, but this result has mediocre statistical certainty (p-value of 0:16). No instances have been found where removing a line from the network has a positive effect (Braess’ paradox), however this is insufficient to conclude that no such instances exist.
we explore the properties of simple network topologies governed by the Kuramoto model. Finally we proceed to the testing of stabilization mechanisms. The stabilization mechanisms tested are (a) increasing the capacity of the power grid lines (b) implementing time delayed feedback mechanisms on the nodes and (c) decentralizing the power generation in the network. Moreover, we test whether examples of Braess’ paradox, which states that adding an edge in a network can locally improve flow but globally cause congestion, can be found in a small network. Increasing the capacity of the power grid lines and implementing time delayed feedback are shown to have a positive effect on the stability of the grid. For a specific grid (the German power grid) it is shown that replacing a large power generator by many smaller generators can indeed have a positive effect on the stability, but this result has mediocre statistical certainty (p-value of 0:16). No instances have been found where removing a line from the network has a positive effect (Braess’ paradox), however this is insufficient to conclude that no such instances exist.