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.

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