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.

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.

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