TJ
T.M.L. Janssen
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>
12 records found
1
Problem definition and Research question
Warehouses rely on order pickers moving through aisles to collect items for shop orders. Large retailers already use algorithms to decide how items are grouped onto load carriers (a process referred to as batching) and which route a picker takes in order to minimize travel time. These algorithms do not account for what happens when many pickers execute their routes at the same time, however: workers can end up needing the same aisle at the same moment, forcing them to wait for one another. This congestion adds time on top of what was planned and becomes more pronounced during busy periods.
This thesis treats batching and routing as fixed, since they are already handled by existing systems, and instead asks whether congestion can be reduced through a different lever: when, and to whom, pick orders are assigned. The resulting research question is: how can order-to-picker assignment be optimized to minimize peak aisle congestion in a warehouse?
Methodology
We formalize the problem as a scheduling problem, with pickers as parallel machines and pick orders, referred to as batches, treated as jobs consisting of a fixed sequence of aisle visits. We prove a simplified version, the Aisle Load Balancing Problem (ALBP), to be NP-complete through a reduction from graph edge colouring. An extended version builds on this with realistic constraints: batches visit aisles in sequence with individual processing times and must start within an earliest and latest allowed time drawn from real delivery deadlines.
Since solving this problem’s ILP exactly can take from seconds to hours, we developed two greedy heuristics as faster alternatives. The NeighborhoodN Greedy builds a schedule while actively avoiding congestion increases, using a limited look-ahead among already available batches. MaxM Greedy instead takes a maximum aisle load as a fixed input and schedules as many batches as possible within it.
We tested all methods, plus a benchmark reflecting current practice, on real data from two large distribution centres, across eight representative days each, in the pickzone with the highest realized number of pick orders.
Results
Across all sixteen instances tested, the ILP achieved the lowest maximum aisle load (𝑀 = 2, 3, 4), followed closely by MaxM Greedy (𝑀 between 3 and 6). Both stay well below the operational congestion threshold of six pickers per aisle. Current assignment practice, and its heuristic approximation of real-world practice (NeighborhoodN Greedy (𝑁 = 0)), reach an average close to 𝑀 ≈ 9 to 10, regularly exceeding this threshold.
There are several important caveats. The ILP achieves its result by using the full width of each batch’s allowed time window, which lengthens the schedule, though it never finishes a batch late. MaxM Greedy trades off differently: pushing its bound too low causes batches to finish too late instead. The ILP is also expensive and unpredictable to compute, ranging from 21 seconds to over two hours with no clear relation to instance size, while both heuristics run in under one second on every instance. This pattern—ILP strongest but slowest, MaxM Greedy fast and close behind, and current practice weakest—holds consistently across all eight days and both warehouses.
Conclusions
Aisle congestion can be reduced substantially through scheduling alone, without changing how orders are batched or routed, and this holds regardless of warehouse or workload. Achieving the largest reduction exactly with the ILP requires accepting a longer schedule or an unpredictable amount of computation time, limiting it to a benchmark rather than a daily tool. Achieving it approximately with MaxM Greedy gives up only a small amount of congestion reduction for a schedule produced in under a second and tunable to whatever aisle load a warehouse accepts. Of the methods tested, MaxM Greedy is the most realistic candidate for day-to-day use.
Further work
Several directions remain open. The model’s inputs could be made more realistic through finer norm time estimation, picker breaks, and a safety buffer against real-world delays such as forklift resupply operations. Two assumptions set in this thesis could be relaxed: a constant number of pickers throughout the day, and batching and routing that ignore congestion. The heuristics could also be extended, for instance by allowing a previously raised aisle load bound to decrease again as time advances. Finally, alternative objectives, such as minimizing makespan under a fixed congestion limit or a genuine bi-objective formulation producing a full tradeoff curve, would let a warehouse choose its own balance rather than the discrete points explored here. ...
Warehouses rely on order pickers moving through aisles to collect items for shop orders. Large retailers already use algorithms to decide how items are grouped onto load carriers (a process referred to as batching) and which route a picker takes in order to minimize travel time. These algorithms do not account for what happens when many pickers execute their routes at the same time, however: workers can end up needing the same aisle at the same moment, forcing them to wait for one another. This congestion adds time on top of what was planned and becomes more pronounced during busy periods.
This thesis treats batching and routing as fixed, since they are already handled by existing systems, and instead asks whether congestion can be reduced through a different lever: when, and to whom, pick orders are assigned. The resulting research question is: how can order-to-picker assignment be optimized to minimize peak aisle congestion in a warehouse?
Methodology
We formalize the problem as a scheduling problem, with pickers as parallel machines and pick orders, referred to as batches, treated as jobs consisting of a fixed sequence of aisle visits. We prove a simplified version, the Aisle Load Balancing Problem (ALBP), to be NP-complete through a reduction from graph edge colouring. An extended version builds on this with realistic constraints: batches visit aisles in sequence with individual processing times and must start within an earliest and latest allowed time drawn from real delivery deadlines.
Since solving this problem’s ILP exactly can take from seconds to hours, we developed two greedy heuristics as faster alternatives. The NeighborhoodN Greedy builds a schedule while actively avoiding congestion increases, using a limited look-ahead among already available batches. MaxM Greedy instead takes a maximum aisle load as a fixed input and schedules as many batches as possible within it.
We tested all methods, plus a benchmark reflecting current practice, on real data from two large distribution centres, across eight representative days each, in the pickzone with the highest realized number of pick orders.
Results
Across all sixteen instances tested, the ILP achieved the lowest maximum aisle load (𝑀 = 2, 3, 4), followed closely by MaxM Greedy (𝑀 between 3 and 6). Both stay well below the operational congestion threshold of six pickers per aisle. Current assignment practice, and its heuristic approximation of real-world practice (NeighborhoodN Greedy (𝑁 = 0)), reach an average close to 𝑀 ≈ 9 to 10, regularly exceeding this threshold.
There are several important caveats. The ILP achieves its result by using the full width of each batch’s allowed time window, which lengthens the schedule, though it never finishes a batch late. MaxM Greedy trades off differently: pushing its bound too low causes batches to finish too late instead. The ILP is also expensive and unpredictable to compute, ranging from 21 seconds to over two hours with no clear relation to instance size, while both heuristics run in under one second on every instance. This pattern—ILP strongest but slowest, MaxM Greedy fast and close behind, and current practice weakest—holds consistently across all eight days and both warehouses.
Conclusions
Aisle congestion can be reduced substantially through scheduling alone, without changing how orders are batched or routed, and this holds regardless of warehouse or workload. Achieving the largest reduction exactly with the ILP requires accepting a longer schedule or an unpredictable amount of computation time, limiting it to a benchmark rather than a daily tool. Achieving it approximately with MaxM Greedy gives up only a small amount of congestion reduction for a schedule produced in under a second and tunable to whatever aisle load a warehouse accepts. Of the methods tested, MaxM Greedy is the most realistic candidate for day-to-day use.
Further work
Several directions remain open. The model’s inputs could be made more realistic through finer norm time estimation, picker breaks, and a safety buffer against real-world delays such as forklift resupply operations. Two assumptions set in this thesis could be relaxed: a constant number of pickers throughout the day, and batching and routing that ignore congestion. The heuristics could also be extended, for instance by allowing a previously raised aisle load bound to decrease again as time advances. Finally, alternative objectives, such as minimizing makespan under a fixed congestion limit or a genuine bi-objective formulation producing a full tradeoff curve, would let a warehouse choose its own balance rather than the discrete points explored here. ...
Problem definition and Research question
Warehouses rely on order pickers moving through aisles to collect items for shop orders. Large retailers already use algorithms to decide how items are grouped onto load carriers (a process referred to as batching) and which route a picker takes in order to minimize travel time. These algorithms do not account for what happens when many pickers execute their routes at the same time, however: workers can end up needing the same aisle at the same moment, forcing them to wait for one another. This congestion adds time on top of what was planned and becomes more pronounced during busy periods.
This thesis treats batching and routing as fixed, since they are already handled by existing systems, and instead asks whether congestion can be reduced through a different lever: when, and to whom, pick orders are assigned. The resulting research question is: how can order-to-picker assignment be optimized to minimize peak aisle congestion in a warehouse?
Methodology
We formalize the problem as a scheduling problem, with pickers as parallel machines and pick orders, referred to as batches, treated as jobs consisting of a fixed sequence of aisle visits. We prove a simplified version, the Aisle Load Balancing Problem (ALBP), to be NP-complete through a reduction from graph edge colouring. An extended version builds on this with realistic constraints: batches visit aisles in sequence with individual processing times and must start within an earliest and latest allowed time drawn from real delivery deadlines.
Since solving this problem’s ILP exactly can take from seconds to hours, we developed two greedy heuristics as faster alternatives. The NeighborhoodN Greedy builds a schedule while actively avoiding congestion increases, using a limited look-ahead among already available batches. MaxM Greedy instead takes a maximum aisle load as a fixed input and schedules as many batches as possible within it.
We tested all methods, plus a benchmark reflecting current practice, on real data from two large distribution centres, across eight representative days each, in the pickzone with the highest realized number of pick orders.
Results
Across all sixteen instances tested, the ILP achieved the lowest maximum aisle load (𝑀 = 2, 3, 4), followed closely by MaxM Greedy (𝑀 between 3 and 6). Both stay well below the operational congestion threshold of six pickers per aisle. Current assignment practice, and its heuristic approximation of real-world practice (NeighborhoodN Greedy (𝑁 = 0)), reach an average close to 𝑀 ≈ 9 to 10, regularly exceeding this threshold.
There are several important caveats. The ILP achieves its result by using the full width of each batch’s allowed time window, which lengthens the schedule, though it never finishes a batch late. MaxM Greedy trades off differently: pushing its bound too low causes batches to finish too late instead. The ILP is also expensive and unpredictable to compute, ranging from 21 seconds to over two hours with no clear relation to instance size, while both heuristics run in under one second on every instance. This pattern—ILP strongest but slowest, MaxM Greedy fast and close behind, and current practice weakest—holds consistently across all eight days and both warehouses.
Conclusions
Aisle congestion can be reduced substantially through scheduling alone, without changing how orders are batched or routed, and this holds regardless of warehouse or workload. Achieving the largest reduction exactly with the ILP requires accepting a longer schedule or an unpredictable amount of computation time, limiting it to a benchmark rather than a daily tool. Achieving it approximately with MaxM Greedy gives up only a small amount of congestion reduction for a schedule produced in under a second and tunable to whatever aisle load a warehouse accepts. Of the methods tested, MaxM Greedy is the most realistic candidate for day-to-day use.
Further work
Several directions remain open. The model’s inputs could be made more realistic through finer norm time estimation, picker breaks, and a safety buffer against real-world delays such as forklift resupply operations. Two assumptions set in this thesis could be relaxed: a constant number of pickers throughout the day, and batching and routing that ignore congestion. The heuristics could also be extended, for instance by allowing a previously raised aisle load bound to decrease again as time advances. Finally, alternative objectives, such as minimizing makespan under a fixed congestion limit or a genuine bi-objective formulation producing a full tradeoff curve, would let a warehouse choose its own balance rather than the discrete points explored here.
Warehouses rely on order pickers moving through aisles to collect items for shop orders. Large retailers already use algorithms to decide how items are grouped onto load carriers (a process referred to as batching) and which route a picker takes in order to minimize travel time. These algorithms do not account for what happens when many pickers execute their routes at the same time, however: workers can end up needing the same aisle at the same moment, forcing them to wait for one another. This congestion adds time on top of what was planned and becomes more pronounced during busy periods.
This thesis treats batching and routing as fixed, since they are already handled by existing systems, and instead asks whether congestion can be reduced through a different lever: when, and to whom, pick orders are assigned. The resulting research question is: how can order-to-picker assignment be optimized to minimize peak aisle congestion in a warehouse?
Methodology
We formalize the problem as a scheduling problem, with pickers as parallel machines and pick orders, referred to as batches, treated as jobs consisting of a fixed sequence of aisle visits. We prove a simplified version, the Aisle Load Balancing Problem (ALBP), to be NP-complete through a reduction from graph edge colouring. An extended version builds on this with realistic constraints: batches visit aisles in sequence with individual processing times and must start within an earliest and latest allowed time drawn from real delivery deadlines.
Since solving this problem’s ILP exactly can take from seconds to hours, we developed two greedy heuristics as faster alternatives. The NeighborhoodN Greedy builds a schedule while actively avoiding congestion increases, using a limited look-ahead among already available batches. MaxM Greedy instead takes a maximum aisle load as a fixed input and schedules as many batches as possible within it.
We tested all methods, plus a benchmark reflecting current practice, on real data from two large distribution centres, across eight representative days each, in the pickzone with the highest realized number of pick orders.
Results
Across all sixteen instances tested, the ILP achieved the lowest maximum aisle load (𝑀 = 2, 3, 4), followed closely by MaxM Greedy (𝑀 between 3 and 6). Both stay well below the operational congestion threshold of six pickers per aisle. Current assignment practice, and its heuristic approximation of real-world practice (NeighborhoodN Greedy (𝑁 = 0)), reach an average close to 𝑀 ≈ 9 to 10, regularly exceeding this threshold.
There are several important caveats. The ILP achieves its result by using the full width of each batch’s allowed time window, which lengthens the schedule, though it never finishes a batch late. MaxM Greedy trades off differently: pushing its bound too low causes batches to finish too late instead. The ILP is also expensive and unpredictable to compute, ranging from 21 seconds to over two hours with no clear relation to instance size, while both heuristics run in under one second on every instance. This pattern—ILP strongest but slowest, MaxM Greedy fast and close behind, and current practice weakest—holds consistently across all eight days and both warehouses.
Conclusions
Aisle congestion can be reduced substantially through scheduling alone, without changing how orders are batched or routed, and this holds regardless of warehouse or workload. Achieving the largest reduction exactly with the ILP requires accepting a longer schedule or an unpredictable amount of computation time, limiting it to a benchmark rather than a daily tool. Achieving it approximately with MaxM Greedy gives up only a small amount of congestion reduction for a schedule produced in under a second and tunable to whatever aisle load a warehouse accepts. Of the methods tested, MaxM Greedy is the most realistic candidate for day-to-day use.
Further work
Several directions remain open. The model’s inputs could be made more realistic through finer norm time estimation, picker breaks, and a safety buffer against real-world delays such as forklift resupply operations. Two assumptions set in this thesis could be relaxed: a constant number of pickers throughout the day, and batching and routing that ignore congestion. The heuristics could also be extended, for instance by allowing a previously raised aisle load bound to decrease again as time advances. Finally, alternative objectives, such as minimizing makespan under a fixed congestion limit or a genuine bi-objective formulation producing a full tradeoff curve, would let a warehouse choose its own balance rather than the discrete points explored here.
When designing a railway timetable, it is important to consider that small delays can frequently occur. If a timetable can recover from small delays and this leads to little hindrance for other trains, we call this a robust timetable. Time supplement is planned in a timetable to improve robustness. Finding the best possible allocation of time supplement is computationally expensive. In this thesis, we instead use a group of algorithms called metaheuristics, which try to efficiently explore a search space to find near-optimal solutions. These metaheuristics are used to reallocate time supplement in a timetable. The timetable is only modified within a network, without requiring changes to the timetable outside of this network.
A graph-based model is used to evaluate timetables created by the metaheuristics based on a set of delay scenarios. These delay scenarios first consisted of sampled entrance delays and dwell times, later also fluctuations in running time were added. A computational study on the Utrecht-Arnhem corridor showed that metaheuristics are suitable for improving allocation of time supplement within limited time. Therefore, metaheuristics deserve more attention in future research to improve the robustness of railway timetables.
...
A graph-based model is used to evaluate timetables created by the metaheuristics based on a set of delay scenarios. These delay scenarios first consisted of sampled entrance delays and dwell times, later also fluctuations in running time were added. A computational study on the Utrecht-Arnhem corridor showed that metaheuristics are suitable for improving allocation of time supplement within limited time. Therefore, metaheuristics deserve more attention in future research to improve the robustness of railway timetables.
...
When designing a railway timetable, it is important to consider that small delays can frequently occur. If a timetable can recover from small delays and this leads to little hindrance for other trains, we call this a robust timetable. Time supplement is planned in a timetable to improve robustness. Finding the best possible allocation of time supplement is computationally expensive. In this thesis, we instead use a group of algorithms called metaheuristics, which try to efficiently explore a search space to find near-optimal solutions. These metaheuristics are used to reallocate time supplement in a timetable. The timetable is only modified within a network, without requiring changes to the timetable outside of this network.
A graph-based model is used to evaluate timetables created by the metaheuristics based on a set of delay scenarios. These delay scenarios first consisted of sampled entrance delays and dwell times, later also fluctuations in running time were added. A computational study on the Utrecht-Arnhem corridor showed that metaheuristics are suitable for improving allocation of time supplement within limited time. Therefore, metaheuristics deserve more attention in future research to improve the robustness of railway timetables.
A graph-based model is used to evaluate timetables created by the metaheuristics based on a set of delay scenarios. These delay scenarios first consisted of sampled entrance delays and dwell times, later also fluctuations in running time were added. A computational study on the Utrecht-Arnhem corridor showed that metaheuristics are suitable for improving allocation of time supplement within limited time. Therefore, metaheuristics deserve more attention in future research to improve the robustness of railway timetables.
Preference-based and optimization-based decision support for port infrastructure renewal
A two-part research combining preference function modelling and net present value optimization at the Port of Rotterdam
Master thesis
(2026)
-
E.D. van Mensvoort, R. Binnekamp, A.A. Roubos, T.M.L. Janssen, Vasiliki E. Kralli
Ports are critical in global supply chains, and quay walls form one of their most expensive and durable assets. The design and renewal of these structures involve complex decisions in which technical, financial, and other considerations must be balanced against one another. In current practice, such decisions are commonly supported by a Multi-Criteria Decision Analysis (MCDA), yet the methodology is often applied in a qualitative and project-specific manner that leaves the derivation of weights and the treatment of soft criteria unstandardized. Moreover, the design process tends to evaluate a limited set of predefined alternatives and to minimize cost and material use, which does not guarantee that a design is either fit-for-purpose or economically optimal. This thesis therefore develops a two-part decision-support framework that is verified and validated through two case studies at the Port of Rotterdam (PoR).
Part I improves the evaluation process through the application of the Preference Function Modelling (PFM) methodology (Barzilai, 2010) within the Tetra software. Three weighting scenarios were constructed for case study I, in which equal weights, standardized survey weights, and project-specific weights were applied to nine decision criteria. The project-specific scenario reproduced the real-world decision, whereas the equal-weight and standardized survey scenarios did not. These results suggest that the standardized survey weights may serve as an organizational reference, but that they cannot replace project-specific input without critical evaluation.
Part II addresses the generative design stage through a single-objective model that maximizes value quantitatively by means of the Net Present Value (NPV). The model was implemented in Python, which combined a differential evolution algorithm with a Monte Carlo simulation of 500 iterations to account for demand uncertainty. Application to case study II yielded a near-optimal configuration of three berths of 360 m and a modal NPV of approximately EUR 303 M. The model identified the Very Large Bulk Carrier (VLBC) as the design vessel class, whereas the real-world quay wall accommodates the Valemax class. This divergence appears to be driven by the locational quay length constraint and by the dominance of cumulative seaport dues over the operational period.
These two parts together suggest that the framework can improve both the transparency and the economic justification of quay wall design decisions. The PFM-based tool provides a traceable and mathematically consistent evaluation process for quay wall projects, while the optimization model reframes the design problem in terms of value generation rather than cost minimization. Both tools were validated through semi-structured interviews with practitioners, who confirmed their added value as decision support instruments rather than as prescriptive design tools. One limitation is that the optimization adopts a single financial objective from the perspective of the PoR Authority, whereas the conventional process also involves other stakeholders. Future research could therefore extend the model towards a multi-objective optimization, for example through the Preferendus methodology by Wolfert (2023), which would broaden its applicability within the port industry. ...
Part I improves the evaluation process through the application of the Preference Function Modelling (PFM) methodology (Barzilai, 2010) within the Tetra software. Three weighting scenarios were constructed for case study I, in which equal weights, standardized survey weights, and project-specific weights were applied to nine decision criteria. The project-specific scenario reproduced the real-world decision, whereas the equal-weight and standardized survey scenarios did not. These results suggest that the standardized survey weights may serve as an organizational reference, but that they cannot replace project-specific input without critical evaluation.
Part II addresses the generative design stage through a single-objective model that maximizes value quantitatively by means of the Net Present Value (NPV). The model was implemented in Python, which combined a differential evolution algorithm with a Monte Carlo simulation of 500 iterations to account for demand uncertainty. Application to case study II yielded a near-optimal configuration of three berths of 360 m and a modal NPV of approximately EUR 303 M. The model identified the Very Large Bulk Carrier (VLBC) as the design vessel class, whereas the real-world quay wall accommodates the Valemax class. This divergence appears to be driven by the locational quay length constraint and by the dominance of cumulative seaport dues over the operational period.
These two parts together suggest that the framework can improve both the transparency and the economic justification of quay wall design decisions. The PFM-based tool provides a traceable and mathematically consistent evaluation process for quay wall projects, while the optimization model reframes the design problem in terms of value generation rather than cost minimization. Both tools were validated through semi-structured interviews with practitioners, who confirmed their added value as decision support instruments rather than as prescriptive design tools. One limitation is that the optimization adopts a single financial objective from the perspective of the PoR Authority, whereas the conventional process also involves other stakeholders. Future research could therefore extend the model towards a multi-objective optimization, for example through the Preferendus methodology by Wolfert (2023), which would broaden its applicability within the port industry. ...
Ports are critical in global supply chains, and quay walls form one of their most expensive and durable assets. The design and renewal of these structures involve complex decisions in which technical, financial, and other considerations must be balanced against one another. In current practice, such decisions are commonly supported by a Multi-Criteria Decision Analysis (MCDA), yet the methodology is often applied in a qualitative and project-specific manner that leaves the derivation of weights and the treatment of soft criteria unstandardized. Moreover, the design process tends to evaluate a limited set of predefined alternatives and to minimize cost and material use, which does not guarantee that a design is either fit-for-purpose or economically optimal. This thesis therefore develops a two-part decision-support framework that is verified and validated through two case studies at the Port of Rotterdam (PoR).
Part I improves the evaluation process through the application of the Preference Function Modelling (PFM) methodology (Barzilai, 2010) within the Tetra software. Three weighting scenarios were constructed for case study I, in which equal weights, standardized survey weights, and project-specific weights were applied to nine decision criteria. The project-specific scenario reproduced the real-world decision, whereas the equal-weight and standardized survey scenarios did not. These results suggest that the standardized survey weights may serve as an organizational reference, but that they cannot replace project-specific input without critical evaluation.
Part II addresses the generative design stage through a single-objective model that maximizes value quantitatively by means of the Net Present Value (NPV). The model was implemented in Python, which combined a differential evolution algorithm with a Monte Carlo simulation of 500 iterations to account for demand uncertainty. Application to case study II yielded a near-optimal configuration of three berths of 360 m and a modal NPV of approximately EUR 303 M. The model identified the Very Large Bulk Carrier (VLBC) as the design vessel class, whereas the real-world quay wall accommodates the Valemax class. This divergence appears to be driven by the locational quay length constraint and by the dominance of cumulative seaport dues over the operational period.
These two parts together suggest that the framework can improve both the transparency and the economic justification of quay wall design decisions. The PFM-based tool provides a traceable and mathematically consistent evaluation process for quay wall projects, while the optimization model reframes the design problem in terms of value generation rather than cost minimization. Both tools were validated through semi-structured interviews with practitioners, who confirmed their added value as decision support instruments rather than as prescriptive design tools. One limitation is that the optimization adopts a single financial objective from the perspective of the PoR Authority, whereas the conventional process also involves other stakeholders. Future research could therefore extend the model towards a multi-objective optimization, for example through the Preferendus methodology by Wolfert (2023), which would broaden its applicability within the port industry.
Part I improves the evaluation process through the application of the Preference Function Modelling (PFM) methodology (Barzilai, 2010) within the Tetra software. Three weighting scenarios were constructed for case study I, in which equal weights, standardized survey weights, and project-specific weights were applied to nine decision criteria. The project-specific scenario reproduced the real-world decision, whereas the equal-weight and standardized survey scenarios did not. These results suggest that the standardized survey weights may serve as an organizational reference, but that they cannot replace project-specific input without critical evaluation.
Part II addresses the generative design stage through a single-objective model that maximizes value quantitatively by means of the Net Present Value (NPV). The model was implemented in Python, which combined a differential evolution algorithm with a Monte Carlo simulation of 500 iterations to account for demand uncertainty. Application to case study II yielded a near-optimal configuration of three berths of 360 m and a modal NPV of approximately EUR 303 M. The model identified the Very Large Bulk Carrier (VLBC) as the design vessel class, whereas the real-world quay wall accommodates the Valemax class. This divergence appears to be driven by the locational quay length constraint and by the dominance of cumulative seaport dues over the operational period.
These two parts together suggest that the framework can improve both the transparency and the economic justification of quay wall design decisions. The PFM-based tool provides a traceable and mathematically consistent evaluation process for quay wall projects, while the optimization model reframes the design problem in terms of value generation rather than cost minimization. Both tools were validated through semi-structured interviews with practitioners, who confirmed their added value as decision support instruments rather than as prescriptive design tools. One limitation is that the optimization adopts a single financial objective from the perspective of the PoR Authority, whereas the conventional process also involves other stakeholders. Future research could therefore extend the model towards a multi-objective optimization, for example through the Preferendus methodology by Wolfert (2023), which would broaden its applicability within the port industry.
Project Scheduling Problem with Mitigation Measures under Renewable Resource Constraints
A Time-Indexed Integer Linear Programming Approach
This thesis studies an extension of the Resource-Constrained Project Scheduling Problem (RCPSP) that incorporates multiple execution modes, time--cost trade-offs, and project tardiness penalties. In contrast to traditional time-indexed formulations that use activity start times as their primary decision reference, this research proposes a finish-time indexed integer linear programming formulation. The proposed model allows project schedules and activity execution modes to be optimized simultaneously while respecting precedence relations and renewable resource constraints.
From a theoretical perspective, the computational complexity of the problem is analysed. It is shown that the proposed formulation is NP-hard through a polynomial-time reduction from the classical RCPSP. Furthermore, even when renewable resource constraints are removed, the resulting problem remains NP-complete through a reduction from the Discrete Time--Cost Trade-Off Problem (DTCTP). These results indicate that the integration of discrete execution modes, precedence constraints, and tardiness penalties leads to a computationally challenging optimization problem.
To enable practical solution of the model, a computational framework was implemented in Python using Pyomo and the Gurobi Optimizer. Several preprocessing techniques were introduced, including sparse variable generation, earliest-time feasibility filtering, and resource activity preprocessing. In addition, a lexicographic optimization procedure was developed to identify the shortest project schedule among solutions with the same optimal objective value. Computational experiments were conducted on 72 benchmark instances derived from DTCTP datasets and extended with renewable resource information.
The results show that the preprocessing procedures substantially reduce the number of binary variables without affecting solution quality. Their impact on runtime depends on the formulation and instance characteristics, but they consistently reduce model size. A comparison with a start-time indexed formulation inspired by Bianco and Caramia demonstrates that both formulations produce identical objective values, makespans, and tardiness values across all benchmark categories. The computational results further show that the proposed finish-time indexed formulation generally achieves shorter solution times and generates fewer constraints than the benchmark formulation, despite not always containing fewer binary variables. These findings indicate that finish-time indexing provides a competitive exact solution approach for project scheduling problems with discrete time--cost trade-offs and renewable resource constraints. ...
From a theoretical perspective, the computational complexity of the problem is analysed. It is shown that the proposed formulation is NP-hard through a polynomial-time reduction from the classical RCPSP. Furthermore, even when renewable resource constraints are removed, the resulting problem remains NP-complete through a reduction from the Discrete Time--Cost Trade-Off Problem (DTCTP). These results indicate that the integration of discrete execution modes, precedence constraints, and tardiness penalties leads to a computationally challenging optimization problem.
To enable practical solution of the model, a computational framework was implemented in Python using Pyomo and the Gurobi Optimizer. Several preprocessing techniques were introduced, including sparse variable generation, earliest-time feasibility filtering, and resource activity preprocessing. In addition, a lexicographic optimization procedure was developed to identify the shortest project schedule among solutions with the same optimal objective value. Computational experiments were conducted on 72 benchmark instances derived from DTCTP datasets and extended with renewable resource information.
The results show that the preprocessing procedures substantially reduce the number of binary variables without affecting solution quality. Their impact on runtime depends on the formulation and instance characteristics, but they consistently reduce model size. A comparison with a start-time indexed formulation inspired by Bianco and Caramia demonstrates that both formulations produce identical objective values, makespans, and tardiness values across all benchmark categories. The computational results further show that the proposed finish-time indexed formulation generally achieves shorter solution times and generates fewer constraints than the benchmark formulation, despite not always containing fewer binary variables. These findings indicate that finish-time indexing provides a competitive exact solution approach for project scheduling problems with discrete time--cost trade-offs and renewable resource constraints. ...
This thesis studies an extension of the Resource-Constrained Project Scheduling Problem (RCPSP) that incorporates multiple execution modes, time--cost trade-offs, and project tardiness penalties. In contrast to traditional time-indexed formulations that use activity start times as their primary decision reference, this research proposes a finish-time indexed integer linear programming formulation. The proposed model allows project schedules and activity execution modes to be optimized simultaneously while respecting precedence relations and renewable resource constraints.
From a theoretical perspective, the computational complexity of the problem is analysed. It is shown that the proposed formulation is NP-hard through a polynomial-time reduction from the classical RCPSP. Furthermore, even when renewable resource constraints are removed, the resulting problem remains NP-complete through a reduction from the Discrete Time--Cost Trade-Off Problem (DTCTP). These results indicate that the integration of discrete execution modes, precedence constraints, and tardiness penalties leads to a computationally challenging optimization problem.
To enable practical solution of the model, a computational framework was implemented in Python using Pyomo and the Gurobi Optimizer. Several preprocessing techniques were introduced, including sparse variable generation, earliest-time feasibility filtering, and resource activity preprocessing. In addition, a lexicographic optimization procedure was developed to identify the shortest project schedule among solutions with the same optimal objective value. Computational experiments were conducted on 72 benchmark instances derived from DTCTP datasets and extended with renewable resource information.
The results show that the preprocessing procedures substantially reduce the number of binary variables without affecting solution quality. Their impact on runtime depends on the formulation and instance characteristics, but they consistently reduce model size. A comparison with a start-time indexed formulation inspired by Bianco and Caramia demonstrates that both formulations produce identical objective values, makespans, and tardiness values across all benchmark categories. The computational results further show that the proposed finish-time indexed formulation generally achieves shorter solution times and generates fewer constraints than the benchmark formulation, despite not always containing fewer binary variables. These findings indicate that finish-time indexing provides a competitive exact solution approach for project scheduling problems with discrete time--cost trade-offs and renewable resource constraints.
From a theoretical perspective, the computational complexity of the problem is analysed. It is shown that the proposed formulation is NP-hard through a polynomial-time reduction from the classical RCPSP. Furthermore, even when renewable resource constraints are removed, the resulting problem remains NP-complete through a reduction from the Discrete Time--Cost Trade-Off Problem (DTCTP). These results indicate that the integration of discrete execution modes, precedence constraints, and tardiness penalties leads to a computationally challenging optimization problem.
To enable practical solution of the model, a computational framework was implemented in Python using Pyomo and the Gurobi Optimizer. Several preprocessing techniques were introduced, including sparse variable generation, earliest-time feasibility filtering, and resource activity preprocessing. In addition, a lexicographic optimization procedure was developed to identify the shortest project schedule among solutions with the same optimal objective value. Computational experiments were conducted on 72 benchmark instances derived from DTCTP datasets and extended with renewable resource information.
The results show that the preprocessing procedures substantially reduce the number of binary variables without affecting solution quality. Their impact on runtime depends on the formulation and instance characteristics, but they consistently reduce model size. A comparison with a start-time indexed formulation inspired by Bianco and Caramia demonstrates that both formulations produce identical objective values, makespans, and tardiness values across all benchmark categories. The computational results further show that the proposed finish-time indexed formulation generally achieves shorter solution times and generates fewer constraints than the benchmark formulation, despite not always containing fewer binary variables. These findings indicate that finish-time indexing provides a competitive exact solution approach for project scheduling problems with discrete time--cost trade-offs and renewable resource constraints.
Delays and cost overruns are common problems in the construction industry. Despite extensive research on their causes and mitigations, these problems persist, suggesting that the challenge is not identifying possible mitigation measures, but rather selecting the optimal combination. Recently, a decision-support tool, Mit-C, was developed to help find the optimal strategy by combining a Monte Carlo simulation with mathematical optimization. However, the tool has a relevant limitation: it does not consider the resources required by the mitigation measures, potentially leading to unrealistic or infeasible solutions.
Consequently, this master thesis addresses this limitation by further developing the project management decision-support tool, Mit-C, through the inclusion of the resources availability and demand required by the mitigation measures. For this purpose, the addition of a significant number of variables and constraints into the original mathematical model was needed, increasing the computational time of the program but improving the realism of the results. The altered model was then validated using a case study: the construction of a warehouse. The tool was used with both simplified and detailed project data to test its performance.
The results demonstrated that including resource constraints has a significant effect on the optimal mitigation strategy and leads to a lower and more realistic probability of finishing the project on time. This difference is more noticeable when using detailed data. It is therefore concluded that while the resource-constrained model produces more pessimistic results, it offers a significantly more realistic, reliable and therefore valuable decision-making tool for project managers. ...
Consequently, this master thesis addresses this limitation by further developing the project management decision-support tool, Mit-C, through the inclusion of the resources availability and demand required by the mitigation measures. For this purpose, the addition of a significant number of variables and constraints into the original mathematical model was needed, increasing the computational time of the program but improving the realism of the results. The altered model was then validated using a case study: the construction of a warehouse. The tool was used with both simplified and detailed project data to test its performance.
The results demonstrated that including resource constraints has a significant effect on the optimal mitigation strategy and leads to a lower and more realistic probability of finishing the project on time. This difference is more noticeable when using detailed data. It is therefore concluded that while the resource-constrained model produces more pessimistic results, it offers a significantly more realistic, reliable and therefore valuable decision-making tool for project managers. ...
Delays and cost overruns are common problems in the construction industry. Despite extensive research on their causes and mitigations, these problems persist, suggesting that the challenge is not identifying possible mitigation measures, but rather selecting the optimal combination. Recently, a decision-support tool, Mit-C, was developed to help find the optimal strategy by combining a Monte Carlo simulation with mathematical optimization. However, the tool has a relevant limitation: it does not consider the resources required by the mitigation measures, potentially leading to unrealistic or infeasible solutions.
Consequently, this master thesis addresses this limitation by further developing the project management decision-support tool, Mit-C, through the inclusion of the resources availability and demand required by the mitigation measures. For this purpose, the addition of a significant number of variables and constraints into the original mathematical model was needed, increasing the computational time of the program but improving the realism of the results. The altered model was then validated using a case study: the construction of a warehouse. The tool was used with both simplified and detailed project data to test its performance.
The results demonstrated that including resource constraints has a significant effect on the optimal mitigation strategy and leads to a lower and more realistic probability of finishing the project on time. This difference is more noticeable when using detailed data. It is therefore concluded that while the resource-constrained model produces more pessimistic results, it offers a significantly more realistic, reliable and therefore valuable decision-making tool for project managers.
Consequently, this master thesis addresses this limitation by further developing the project management decision-support tool, Mit-C, through the inclusion of the resources availability and demand required by the mitigation measures. For this purpose, the addition of a significant number of variables and constraints into the original mathematical model was needed, increasing the computational time of the program but improving the realism of the results. The altered model was then validated using a case study: the construction of a warehouse. The tool was used with both simplified and detailed project data to test its performance.
The results demonstrated that including resource constraints has a significant effect on the optimal mitigation strategy and leads to a lower and more realistic probability of finishing the project on time. This difference is more noticeable when using detailed data. It is therefore concluded that while the resource-constrained model produces more pessimistic results, it offers a significantly more realistic, reliable and therefore valuable decision-making tool for project managers.
The Bin Packing Problem with negative items
Extending Classical Bin Packing with negative items
The standard bin packing problem is about distributing a set of items with positive sizes over bins of certain capacity in such a way that the number of bins used is minimized. In this thesis a relatively undocumented version of bin packing with negative items is discussed. Negative items added to the standard problem can reduce the load in a bin. In context, this means energy is regenerated or recharged. This forces us to take a look at the problem in a different way. The goal of this thesis is to find methods that give solutions with a guaranteed desired quality. For the standard problem, we already have well-working heuristic algorithms such as the First Fit (FF), Best Fit (BF), and their decreasing-order variants (FFD and BFD). These algorithms have nice bounded approximation ratios. However, introducing negative items sabotages these nice approximation ratios. We know negative items can reduce the total number of bins, so naively applying classical algorithms does not perform well, as these methods do not take the potential of negative items to offset large positives and reduce bin usage into account. To try and solve these problems, we introduce the adjusted heuristic algorithms Negative First Fit (NFF), Negative Best Fit (NBF), and their decreasing-order variants, which work by placing all negative items into the first bin before applying the standard algorithm. By placing all negative items in the first bin, we can get a packing that uses 1 bin or more. If the packing uses only 1 bin, the problem is trivial. If it uses more than 1 bin, we know that all negative items in the first bin have been canceled out, so we can retain the logic of the standard problem and thus the approximation ratio. Although the negative adjusted algorithm has a nice approximation ratio, putting all negative items in the first bin does not make sense in a real-life context. That is why we also explore the heuristic method of dividing negative items over large positive ones before applying standard packing algorithms. Here we focus on the notion that fewer big items, where we define big items as items larger than half the capacity, lead to a smaller number of bins for the solution because all big items need to be in a separate bin. First we have Decreasing Division (DD), which pairs the largest big item with the smallest negative items. Unfortunately, this does not guarantees a reduction of big items. To try and improve on this, we also introduce Increasing Division (ID). ID pairs the smallest big item to the smallest negative item. This way, ID can give a bigger guarantee to reduce the number of big items. DD and ID both have the same approximation ratio and both give more logical packing results. However, we proved that for DD there is no better approximation ratio. For ID however, we saw that a better approximation ratio may still be found. This thesis is mostly based on literature research, mathematical analysis and explanatory examples. We show the potential performance and limitations of different heuristic algorithms for bin packing
with negative items. The results achieved give a different perspective on the bin packing problem and leave open future research in optimizing bin packing with negative items. But most importantly, the goal of finding methods that work on the bin packing problem with negative items was achieved. ...
with negative items. The results achieved give a different perspective on the bin packing problem and leave open future research in optimizing bin packing with negative items. But most importantly, the goal of finding methods that work on the bin packing problem with negative items was achieved. ...
The standard bin packing problem is about distributing a set of items with positive sizes over bins of certain capacity in such a way that the number of bins used is minimized. In this thesis a relatively undocumented version of bin packing with negative items is discussed. Negative items added to the standard problem can reduce the load in a bin. In context, this means energy is regenerated or recharged. This forces us to take a look at the problem in a different way. The goal of this thesis is to find methods that give solutions with a guaranteed desired quality. For the standard problem, we already have well-working heuristic algorithms such as the First Fit (FF), Best Fit (BF), and their decreasing-order variants (FFD and BFD). These algorithms have nice bounded approximation ratios. However, introducing negative items sabotages these nice approximation ratios. We know negative items can reduce the total number of bins, so naively applying classical algorithms does not perform well, as these methods do not take the potential of negative items to offset large positives and reduce bin usage into account. To try and solve these problems, we introduce the adjusted heuristic algorithms Negative First Fit (NFF), Negative Best Fit (NBF), and their decreasing-order variants, which work by placing all negative items into the first bin before applying the standard algorithm. By placing all negative items in the first bin, we can get a packing that uses 1 bin or more. If the packing uses only 1 bin, the problem is trivial. If it uses more than 1 bin, we know that all negative items in the first bin have been canceled out, so we can retain the logic of the standard problem and thus the approximation ratio. Although the negative adjusted algorithm has a nice approximation ratio, putting all negative items in the first bin does not make sense in a real-life context. That is why we also explore the heuristic method of dividing negative items over large positive ones before applying standard packing algorithms. Here we focus on the notion that fewer big items, where we define big items as items larger than half the capacity, lead to a smaller number of bins for the solution because all big items need to be in a separate bin. First we have Decreasing Division (DD), which pairs the largest big item with the smallest negative items. Unfortunately, this does not guarantees a reduction of big items. To try and improve on this, we also introduce Increasing Division (ID). ID pairs the smallest big item to the smallest negative item. This way, ID can give a bigger guarantee to reduce the number of big items. DD and ID both have the same approximation ratio and both give more logical packing results. However, we proved that for DD there is no better approximation ratio. For ID however, we saw that a better approximation ratio may still be found. This thesis is mostly based on literature research, mathematical analysis and explanatory examples. We show the potential performance and limitations of different heuristic algorithms for bin packing
with negative items. The results achieved give a different perspective on the bin packing problem and leave open future research in optimizing bin packing with negative items. But most importantly, the goal of finding methods that work on the bin packing problem with negative items was achieved.
with negative items. The results achieved give a different perspective on the bin packing problem and leave open future research in optimizing bin packing with negative items. But most importantly, the goal of finding methods that work on the bin packing problem with negative items was achieved.
This thesis proposes a new solution to minimize the number of batteries needed to schedule ships depending on the presented harbour. The proposed solution is an extension to the bin packing problem. Item Fragmentation (BPP-IF) and Conflicts (BPPC) were added to allow ships to carry more batteries and to prevent batteries from being scheduled for multiple ships, respectively. Negative Items (BPP-NI) were added to allow for the batteries to be charged when they were not scheduled to be used. The combination of the three bin packing extensions (BPPC-IF-NI) formed the basis for the proposed solution. By a polynomial time reduction we showed that BPPC-IF-NI is NP-hard and therefore cannot be analytically solved in polynomial time. The solution can be approximated with an updated version of the heuristic presented by Ekici (2022). The main idea in this heuristic approach is to generate a set of independent sets of the conflict graph and determine the packing of the bins using the independent sets with the help of the integer linear program ISB-IP. An iterative framework is used where 𝐿 sets of 𝑇 independent sets are generated at each iteration and considered together with the independent sets used in the best solution to obtain a better solution. After testing many possible combinations of 𝐿 and 𝑇, it was found that 𝐿 = 50 and 𝑇 = 10 gives the best results, meaning that half of the number of the initial independent sets (𝐿-value) containing a maximum of half the number of items in each set (𝑇-value) where added in each iteration. When using these parameters, it was found that the solution of the heuristic was the same as the true optimal value. This was checked by inserting the power set without conflicts into the ISB-IP. The performance of the proposed solution was tested on generated instances. It was seen that there is no correlation between the computation time and the number of conflicts. It was also found that there was a strong correlation between the number of conflicts and the number of batteries used in the solution, without any clear outliers. The proposed solution is able to very quickly approximate the minimum number of batteries needed to schedule the ships for the given harbour. Since most instances are approximated in a couple of seconds, it can also be used to update schedules when complication arise on a smaller scale. This would allow harbours to switch to electric ships, while reducing the cost by minimizing the number of expensive ship batteries.
...
This thesis proposes a new solution to minimize the number of batteries needed to schedule ships depending on the presented harbour. The proposed solution is an extension to the bin packing problem. Item Fragmentation (BPP-IF) and Conflicts (BPPC) were added to allow ships to carry more batteries and to prevent batteries from being scheduled for multiple ships, respectively. Negative Items (BPP-NI) were added to allow for the batteries to be charged when they were not scheduled to be used. The combination of the three bin packing extensions (BPPC-IF-NI) formed the basis for the proposed solution. By a polynomial time reduction we showed that BPPC-IF-NI is NP-hard and therefore cannot be analytically solved in polynomial time. The solution can be approximated with an updated version of the heuristic presented by Ekici (2022). The main idea in this heuristic approach is to generate a set of independent sets of the conflict graph and determine the packing of the bins using the independent sets with the help of the integer linear program ISB-IP. An iterative framework is used where 𝐿 sets of 𝑇 independent sets are generated at each iteration and considered together with the independent sets used in the best solution to obtain a better solution. After testing many possible combinations of 𝐿 and 𝑇, it was found that 𝐿 = 50 and 𝑇 = 10 gives the best results, meaning that half of the number of the initial independent sets (𝐿-value) containing a maximum of half the number of items in each set (𝑇-value) where added in each iteration. When using these parameters, it was found that the solution of the heuristic was the same as the true optimal value. This was checked by inserting the power set without conflicts into the ISB-IP. The performance of the proposed solution was tested on generated instances. It was seen that there is no correlation between the computation time and the number of conflicts. It was also found that there was a strong correlation between the number of conflicts and the number of batteries used in the solution, without any clear outliers. The proposed solution is able to very quickly approximate the minimum number of batteries needed to schedule the ships for the given harbour. Since most instances are approximated in a couple of seconds, it can also be used to update schedules when complication arise on a smaller scale. This would allow harbours to switch to electric ships, while reducing the cost by minimizing the number of expensive ship batteries.
This thesis introduces a model designed to provide port operators with insights into necessary infrastructure and adequate scheduling approaches when ships use electricity as their main power source. The operator manages a shipping port equipped with charging stations and provides a selection of electricity-powered freight cargo ships with container batteries. The model is designed for an arbitrary single-port waterway system. The focus is directed toward inland waterway systems, a choice influenced by the limited capacity of container batteries. Optional external revenue streams in the form of grid balancing and two core uncertainties of the maritime sector are incorporated into the model, namely energy consumption and arrival time uncertainty.
Optimization approaches are formulated on the model to find the optimal number of batteries, charging stations, and grid balancing stints. The following six approaches are employed: approximation algorithm, MIP formulation, rolling horizon, probabilistic constraint, extreme value analysis, and value at risk. The strategies all produce a schedule that guides the operator in managing the infrastructure optimally in a different context. The approaches are tested on a simulated waterway system. The approximation algorithm is a great first step. The MIP formulation provides a valuable next step in insight into the complexities of the system. However, it scales too poorly to extend to bigger data cases or to integrate uncertainties.
In scenarios involving uncertainty, the rolling horizon approach is recommended due to its adaptability and realistic modeling. Valuable insights about the limits of the system can be obtained by implementing values at risk and extreme value analyses. The probabilistic constraint approach is a suitable alternative if normally distributed uncertainty is inherent to the uncertainty data.
The model with these optimization methods provides port operators with essential insights into the system they are managing.
...
Optimization approaches are formulated on the model to find the optimal number of batteries, charging stations, and grid balancing stints. The following six approaches are employed: approximation algorithm, MIP formulation, rolling horizon, probabilistic constraint, extreme value analysis, and value at risk. The strategies all produce a schedule that guides the operator in managing the infrastructure optimally in a different context. The approaches are tested on a simulated waterway system. The approximation algorithm is a great first step. The MIP formulation provides a valuable next step in insight into the complexities of the system. However, it scales too poorly to extend to bigger data cases or to integrate uncertainties.
In scenarios involving uncertainty, the rolling horizon approach is recommended due to its adaptability and realistic modeling. Valuable insights about the limits of the system can be obtained by implementing values at risk and extreme value analyses. The probabilistic constraint approach is a suitable alternative if normally distributed uncertainty is inherent to the uncertainty data.
The model with these optimization methods provides port operators with essential insights into the system they are managing.
...
This thesis introduces a model designed to provide port operators with insights into necessary infrastructure and adequate scheduling approaches when ships use electricity as their main power source. The operator manages a shipping port equipped with charging stations and provides a selection of electricity-powered freight cargo ships with container batteries. The model is designed for an arbitrary single-port waterway system. The focus is directed toward inland waterway systems, a choice influenced by the limited capacity of container batteries. Optional external revenue streams in the form of grid balancing and two core uncertainties of the maritime sector are incorporated into the model, namely energy consumption and arrival time uncertainty.
Optimization approaches are formulated on the model to find the optimal number of batteries, charging stations, and grid balancing stints. The following six approaches are employed: approximation algorithm, MIP formulation, rolling horizon, probabilistic constraint, extreme value analysis, and value at risk. The strategies all produce a schedule that guides the operator in managing the infrastructure optimally in a different context. The approaches are tested on a simulated waterway system. The approximation algorithm is a great first step. The MIP formulation provides a valuable next step in insight into the complexities of the system. However, it scales too poorly to extend to bigger data cases or to integrate uncertainties.
In scenarios involving uncertainty, the rolling horizon approach is recommended due to its adaptability and realistic modeling. Valuable insights about the limits of the system can be obtained by implementing values at risk and extreme value analyses. The probabilistic constraint approach is a suitable alternative if normally distributed uncertainty is inherent to the uncertainty data.
The model with these optimization methods provides port operators with essential insights into the system they are managing.
Optimization approaches are formulated on the model to find the optimal number of batteries, charging stations, and grid balancing stints. The following six approaches are employed: approximation algorithm, MIP formulation, rolling horizon, probabilistic constraint, extreme value analysis, and value at risk. The strategies all produce a schedule that guides the operator in managing the infrastructure optimally in a different context. The approaches are tested on a simulated waterway system. The approximation algorithm is a great first step. The MIP formulation provides a valuable next step in insight into the complexities of the system. However, it scales too poorly to extend to bigger data cases or to integrate uncertainties.
In scenarios involving uncertainty, the rolling horizon approach is recommended due to its adaptability and realistic modeling. Valuable insights about the limits of the system can be obtained by implementing values at risk and extreme value analyses. The probabilistic constraint approach is a suitable alternative if normally distributed uncertainty is inherent to the uncertainty data.
The model with these optimization methods provides port operators with essential insights into the system they are managing.
Maximum Coverage Problems
Theory and Application in Optimal Sensor Selection
In this thesis we analyse the class of maximum coverage problems. For all discussed problems, linear programs are formulated. Using the notion of submodularity, we prove that for the weighted version of the basic Maximum Coverage problem, where the weights differ per set, a polynomial-time greedy algorithm guarantees a (1 - 1/e)-approximation of the optimal solution. This improves the already known bound of (1 - 1/e - ε), for all ε > 0. We then show that the same result holds true, if we allow elements to be covered by multiple sets. Furthermore, a completely novel extension is introduced, where weights differ per combination of sets. It is proved that, under the assumption that the weights are submodular and increasing, a greedy algorithm still provides a (1 – 1/e)-approximation.
The latter algorithm is tested in the framework of optimal sensor selection. To this end, we consider all official weather stations in the Netherlands as our sensor group. We test the performance of the approximation algorithm, if some of the assumptions do not hold and no theoretical bounds exists. Corresponding weights are calculated, using two approaches: inverse distance weighting and multiple linear regression. For both approaches the in practice performance of the greedy algorithm is shown to be even higher than (1 – 1/e), even though not all assumptions hold. Finally, the corresponding selection of weather stations is shown. ...
The latter algorithm is tested in the framework of optimal sensor selection. To this end, we consider all official weather stations in the Netherlands as our sensor group. We test the performance of the approximation algorithm, if some of the assumptions do not hold and no theoretical bounds exists. Corresponding weights are calculated, using two approaches: inverse distance weighting and multiple linear regression. For both approaches the in practice performance of the greedy algorithm is shown to be even higher than (1 – 1/e), even though not all assumptions hold. Finally, the corresponding selection of weather stations is shown. ...
In this thesis we analyse the class of maximum coverage problems. For all discussed problems, linear programs are formulated. Using the notion of submodularity, we prove that for the weighted version of the basic Maximum Coverage problem, where the weights differ per set, a polynomial-time greedy algorithm guarantees a (1 - 1/e)-approximation of the optimal solution. This improves the already known bound of (1 - 1/e - ε), for all ε > 0. We then show that the same result holds true, if we allow elements to be covered by multiple sets. Furthermore, a completely novel extension is introduced, where weights differ per combination of sets. It is proved that, under the assumption that the weights are submodular and increasing, a greedy algorithm still provides a (1 – 1/e)-approximation.
The latter algorithm is tested in the framework of optimal sensor selection. To this end, we consider all official weather stations in the Netherlands as our sensor group. We test the performance of the approximation algorithm, if some of the assumptions do not hold and no theoretical bounds exists. Corresponding weights are calculated, using two approaches: inverse distance weighting and multiple linear regression. For both approaches the in practice performance of the greedy algorithm is shown to be even higher than (1 – 1/e), even though not all assumptions hold. Finally, the corresponding selection of weather stations is shown.
The latter algorithm is tested in the framework of optimal sensor selection. To this end, we consider all official weather stations in the Netherlands as our sensor group. We test the performance of the approximation algorithm, if some of the assumptions do not hold and no theoretical bounds exists. Corresponding weights are calculated, using two approaches: inverse distance weighting and multiple linear regression. For both approaches the in practice performance of the greedy algorithm is shown to be even higher than (1 – 1/e), even though not all assumptions hold. Finally, the corresponding selection of weather stations is shown.
Background
Scheduling is a form of decision-making that plays a very important role in manufacturing industries. It is the method by which work gets assigned to resources that compute it. In this thesis we want to assign jobs (cycles of a lithography process) to different machines in such a way that the machines are running for as little time as possible. The difficulty lies in the fact that some jobs require the same resource, and thus cannot be processed simultaneously.
Results
It appears that the following scheduling problems are NP-hard:
• P2kCmax and R2kCmax
• P3|res · 11, pj = 1|Cmax and R3|res · 11, pj = 1|Cmax
• P3|res · 11, pj = 1|
P Cj and R3|res · 11, pj = 1|
P Cj
We try to approximate an optimal solution for the scheduling problem Rm|res · 11| P Cj by calculating a ratio with a lower bound, where we ignore resource constraints, and an upper bound, that is found by a Greedy algorithm (w.r.t. resource constraints).
Conclusions
It appears that Greedy is not a very good approximation algorithm for this problem, since the ratio in which the optimal Total Completion Time should lie is about 8,33% of the average calculated Total Completion Time ...
Scheduling is a form of decision-making that plays a very important role in manufacturing industries. It is the method by which work gets assigned to resources that compute it. In this thesis we want to assign jobs (cycles of a lithography process) to different machines in such a way that the machines are running for as little time as possible. The difficulty lies in the fact that some jobs require the same resource, and thus cannot be processed simultaneously.
Results
It appears that the following scheduling problems are NP-hard:
• P2kCmax and R2kCmax
• P3|res · 11, pj = 1|Cmax and R3|res · 11, pj = 1|Cmax
• P3|res · 11, pj = 1|
P Cj and R3|res · 11, pj = 1|
P Cj
We try to approximate an optimal solution for the scheduling problem Rm|res · 11| P Cj by calculating a ratio with a lower bound, where we ignore resource constraints, and an upper bound, that is found by a Greedy algorithm (w.r.t. resource constraints).
Conclusions
It appears that Greedy is not a very good approximation algorithm for this problem, since the ratio in which the optimal Total Completion Time should lie is about 8,33% of the average calculated Total Completion Time ...
Background
Scheduling is a form of decision-making that plays a very important role in manufacturing industries. It is the method by which work gets assigned to resources that compute it. In this thesis we want to assign jobs (cycles of a lithography process) to different machines in such a way that the machines are running for as little time as possible. The difficulty lies in the fact that some jobs require the same resource, and thus cannot be processed simultaneously.
Results
It appears that the following scheduling problems are NP-hard:
• P2kCmax and R2kCmax
• P3|res · 11, pj = 1|Cmax and R3|res · 11, pj = 1|Cmax
• P3|res · 11, pj = 1|
P Cj and R3|res · 11, pj = 1|
P Cj
We try to approximate an optimal solution for the scheduling problem Rm|res · 11| P Cj by calculating a ratio with a lower bound, where we ignore resource constraints, and an upper bound, that is found by a Greedy algorithm (w.r.t. resource constraints).
Conclusions
It appears that Greedy is not a very good approximation algorithm for this problem, since the ratio in which the optimal Total Completion Time should lie is about 8,33% of the average calculated Total Completion Time
Scheduling is a form of decision-making that plays a very important role in manufacturing industries. It is the method by which work gets assigned to resources that compute it. In this thesis we want to assign jobs (cycles of a lithography process) to different machines in such a way that the machines are running for as little time as possible. The difficulty lies in the fact that some jobs require the same resource, and thus cannot be processed simultaneously.
Results
It appears that the following scheduling problems are NP-hard:
• P2kCmax and R2kCmax
• P3|res · 11, pj = 1|Cmax and R3|res · 11, pj = 1|Cmax
• P3|res · 11, pj = 1|
P Cj and R3|res · 11, pj = 1|
P Cj
We try to approximate an optimal solution for the scheduling problem Rm|res · 11| P Cj by calculating a ratio with a lower bound, where we ignore resource constraints, and an upper bound, that is found by a Greedy algorithm (w.r.t. resource constraints).
Conclusions
It appears that Greedy is not a very good approximation algorithm for this problem, since the ratio in which the optimal Total Completion Time should lie is about 8,33% of the average calculated Total Completion Time