Attending the International Conference of the German Operations Research Society (OR2016, Hamburg)

At this year´s annual International Conference on Operations Research (30.08.-02.09.2016, Hamburg)  Franz Ehm, Martin Scheffler and Sven Schulz were speaking in the streams "Project Management and Scheduling" and "Logistics, Routing and Location Planning". The event took place at the " Helmut-Schmidt-Universität" in Hamburg.

Machine scheduling for multi-product disassembly

Franz Ehm

In recent years, manufacturers of consumer goods have been faced with a substantial reflow of end-of-life products mainly due to increased ecological thinking among customers or legal directives. There are several strategies which have emerged under the topic of remanufacturing in order to exploit the remaining economic value from these products. The efficient disassembly plays a key role in enabling these potentials or limit the losses resulting from the duty of disposal. This study represents a novel approach to combine the problems of disassembly sequence planning and machine scheduling. In this context, we assume a shop of several non-identical stations which are available for the complete disassembly of a given set of heterogeneous products. The problem is to simultaneously determine the sequence of disassembly operations for each product and the order of products at the stations with the objective of minimizing makespan. The approach taken in this study presents some similarities to existing formulations in the field of job shop scheduling with alternative process plans. However, the proposed model explicitly considers divergence of the product structure as inherent feature of disassembly. That is, separate sub-assemblies of the same product may be disassembled at the same time meaning operations of the same job can possibly overlap in the schedule. Therefore, we derive a graph-based representation which incorporates both alternative and parallel operations for each product. A mixed-integer-program is then deployed to solve the combined problem using commercial optimization software. Finally, we provide a numerical study to analyze the effects on solution time and quality under varying problem configurations.

Splitting procedure of genetic algorithm for column generation to solve a Vehicle Routing Problem

Martin Scheffler, Christina Hermann, Mathias Kasper

This paper considers a Vehicle Routing Problem with Simultaneous Pickup and Delivery and Time Windows (VRPSPDTW) extended by two kinds of demands assigned to specific nodes, introduced by Liu et al. (2013). As a practical application home health care logistics can be mentioned. The first demand concerns delivery from specific node one, e.g. a drugstore to customers and the second concerns pickup from customers to specific node two, e.g. a lab. Given the difficulty of this problem as NP-hard the use of metaheuristics for its solution is recommended. There is an abundance of studies about tuning common heuristics and using them for similar problems without a detailed view on the utilization of the generated informations. Therefore, this paper describes a relatively simple but effective extension of a genetic algorithm (GA) based on permutation chromosome and a splitting procedure. Using the splitting procedure to create a complete memory of all valid trips as feasible columns enables us to solve the master problem of a set partitioning formulation. The memory contains all feasible columns generated by the splitting procedure regardless of the offspring admissibility and the iteration productivity. The result is a hybrid metaheuristic with parallel search for a feasible solution (trip schedule for each vehicle) and integrated column generation. In a first step, a suitable frequency of solving the master problem is determined. Since it still is a heuristic the quality is evaluated in comparison to the optimal solution identified by CPLEX for small instances. For large instances it is obvious to use the original GA as benchmark. Theseapproaches are tested on test instances for the considered problem and by adjusted input data on classic VRPTW instances.

A multi-criteria MILP formulation for energy aware hybrid flow shop scheduling

Sven Schulz

The present paper introduces a multi-criteria parallel flow shop problem considering variable discrete production speeds. Managing energy consumption more sustainably and efficiently is one of the most significant challenges for a growing society in the twenty-first century. In recent years, consequently, the consideration of energy consumption has been gaining increasing importance in all industrial planning processes. Logically, there is also a limited set of papers dealing with different aspects of energy consumption as well as energy costs in scheduling. Overall, three different approaches can be identified. In detail, the energy consumption can be reduced by specific planning, time-dependent electricity cost might be exploited or the peak power may be decreased. In contrast to the majority of energy aware scheduling models these ideas are adopted simultaneously in the proposed new extensive MILP formulation. In order to affect peak load and energy consumption variable discrete production rates as well as heterogeneous parallel machines with different levels of efficiency are considered. As a result, the interdependencies of different energy aware scheduling approaches can be shown. Furthermore, a multi-criteria objective function is proposed. Besides total completion time, time depending energy costs and the peak power are minimized. It can be shown that there is a dilemma between peak power minimization and demand charge reduction. A compromise proposal is given for this contrary effect. Since this problem is NP-hard, the numeric example is not only solved by classical solver software but also by using a heuristic approach. The results of the numeric example illustrate how the model operates.