A Hybrid Genetic Algorithm for the KBounded SemiOnline Bin Covering Problem in Batching Machines The semionline bin covering problem is a NPhard problem that occurs in a batching processes in a highend poultry processing line. The objective is to form batches of items with minimal giveaway, which is the difference between the target and realized batch weight. The items in this process are allocated in the order of arrival, and the weight of the first set of items is assumed to be known. We develop a novel hybrid genetic algorithm, combining a genetic algorithm and several local search methods. Simulation experiments based on realworld data are performed to gain managerial insights. These simulations suggest that the proposed algorithm produces high quality solutions within a reasonable time limit.

Online Bin Covering with Limited Migration Semionline models where decisions may be revoked in a limited way have been studied extensively in the last years.  :19,is motivated by the fact that the pure online model :19,is often too restrictive to model realworld applications, where some changes might be allowed. A wellstudied measure of the amount of decisions that can be revoked :19,is the migration factor beta: When an object o of size s(o) arrives, the decisions for objects of total size at most betacdot s(o) may be revoked. Usually beta should be a constant. This means that a small object only leads to small changes. This measure has been successfully investigated for different, classic problems such as bin packing or makespan minimization. The dual of makespan minimization  the Santa Claus or machine covering problem  has also been studied, whereas the dual of bin packing  the bin covering problem  has not been looked at from such a perspective.  :156,this work, we extensively study the bin covering problem with migration in different scenarios. We develop algorithms both for the static case  where only insertions are allowed  and for the dynamic case, where items may also depart. We also develop lower bounds for these scenarios both for amortized migration and for worstcase migration showing that our algorithms have nearly optimal migration factor and asymptotic competitive ratio (up to an arbitrary small eps). We therefore resolve the competitiveness of the bin covering problem with migration.