An application of combinatorial optimization in the printing industry

Offset printing is a common method to produce large amounts of printed matter. We consider a real-world offset printing process that is used to imprint customer-specific designs on napkin pouches. The print- ing technology used yields a number of specific constraints. The planning problem consists of allocating designs to printing-plate slots such that the given customer demand for each design is fulfilled, all technologi- cal and organizational constraints are met and the total overproduction and setup costs are minimized. We formulate this planning problem as a mixed-binary linear program, and we develop a multi-pass matching-based savings heuristic. We report computational results for a set of problem instances devised from real-world data.

A serial scheme for minimizing the duration of resource-constrained projects within Microsoft Project

Microsoft Project is one of the most-widely used software packages for project management. For the scheduling of resource-constrained projects, the package applies a priority-based procedure using a specific schedule-generation scheme. This procedure performs relatively poorly when compared against other software packages or state-of-the-art methods for resource-constrained project scheduling. In Microsoft Project 2010, it is possible to work with schedules that are infeasible with respect to the precedence or the resource constraints. We propose a novel schedule-generation scheme that makes use of this possibility. Under this scheme, the project tasks are scheduled sequentially while taking into account all temporal and resource constraints that a user can define within Microsoft Project. The scheme can be implemented as a priority-rule based heuristic procedure. Our computational results for two real-world construction projects indicate that this procedure outperforms the built-in procedure of Microsoft Project

Heuristic decomposition and LP-based scheduling in make-and-pack production

In this paper, we are concerned about the short-term scheduling of industrial make-and-pack production processes. The planning problem consists in minimizing the production makespan while meeting given end-product demands. Sequence-dependent changeover times, multi-purpose storage units with finite capacities, quarantine times, batch splitting, partial equipment connectivity, material transfer times, and a large number of operations contribute to the complexity of the problem. Known MILP formulations cover all technological constraints of such production processes, but only small problem instances can be solved in reasonable CPU times. In this paper, we develop a heuristic in order to tackle large instances. Under this heuristic, groups of batches are scheduled iteratively using a novel MILP formulation; the assignment of the batches to the groups and the scheduling sequence of the groups are determined using a priority rule. We demonstrate the applicability by means of a real-world production process.

Scheduling in service systems: an application in the event-tourism industry

This paper deals with an event-bus tour booked by Bollywood film fans. During the tour, the participants visit selected locations of famous Bollywood films at various sites in Switzerland. Moreover, the tour includes stops for lunch and shopping. Each day, up to five buses operate the tour; for organizational reasons, two or more buses cannot stay at the same location simultaneously. The planning problem is how to compute a feasible schedule for each bus such that the total waiting time (primary objective) and the total travel time (secondary objective) are minimized. We formulate this problem as a mixed-integer linear program, and we report on computational results obtained with the Gurobi solver.

Index Tracking Using Data-Mining Techniques and Mixed-Binary Linear Programming

Index tracking has become one of the most common strategies in asset management. The index-tracking problem consists of constructing a portfolio that replicates the future performance of an index by including only a subset of the index constituents in the portfolio. Finding the most representative subset is challenging when the number of stocks in the index is large. We introduce a new three-stage approach that at first identifies promising subsets by employing data-mining techniques, then determines the stock weights in the subsets using mixed-binary linear programming, and finally evaluates the subsets based on cross validation. The best subset is returned as the tracking portfolio. Our approach outperforms state-of-the-art methods in terms of out-of-sample performance and running times.