Decision Making in Manufacturing and Services

Vol. 3, 2009, No. 1–2

Contents

On Efficient Coloring of Chordless Graphs
Robert Janczewski, Michał Małafiejski

Abstract: We are given a simple graph G = (V, E). Any edge e ∈ E is a chord  in a path P ⊆ G (cycle C ⊆ G) if a graph obtained by joining e to path P  (cycle C) has exactly two vertices of degree 3. A class of graphs without any chord in paths (cycles) we call path-chordless (cycle-chordless). We will prove that recognizing and coloring of these graphs can be done in O(n²) and O(n) time, respectively. Our study was motivated by a wide range of applications of the graph coloring problem in coding theory, time tabling and scheduling, frequency assignment, register allocation and many other areas.. 

Modelling Multi-Period Set-up Times in the Proportional Lot-Sizing Problem
Waldemar Kaczmarczyk

Abstract: This paper presents new mixed integer programming models for the Proportional Lot-Sizing Problem (PLSP) with set-up times longer than a period. Proposed models explicitly calculate the distribution of times amongst products in periods with a changeover and determine a final period for every set-up operation. Presented results prove that the proposed models are easier to solve using standard MIP methods than already known models. 

Practical Tips for Modeling Lot-Sizing and Scheduling Problems
Waldemar Kaczmarczyk

Abstract: This paper presents some important alternatives of modeling Lot-Sizing and Scheduling Problems. Firstly, one can achieve similar modeling accuracy using complex models with long time buckets and simple models with short time buckets. Using short periods leads to two possible settings of the inventory holding costs, one appropriate for fictitious another for real planning periods. Next, valid inequalities make the models tighter but increase their size. In some data settings it is possible to find a good balance between the size and tightness of a model by appropriate limitation of the number of valid inequalities. Finally, special normalization of variables simplifies presentation of results and may speed up computation of solutions. Some of the presented results have been achieved with advanced commercial solvers and some with simple open source solvers.

Robust Buffer Allocation for Scheduling of a Project with Predefined Milestones
Marcin Klimek, Piotr Łebkowski

Abstract: The paper discusses the problem of robust buffer allocation for Resource-Constrained Project Scheduling Problem (RCPSP) with predefined milestones , for which execution deadlines have been established. To solve the problem, an algorithm is proposed supporting insertion of unit time buffers, with the simultaneous maximisation of new metrics of arrangement robustness. The presented results of experimental research speak for usability of the solutions proposed. The effectiveness is studied with use of test tasks  included in the Project Scheduling Problem Library (PSPLIB) with additionally specified project milestones.

A Reference Point Approach to Bi-Objective Dynamic Portfolio Optimization
Bartosz Sawik

Abstract: The portfolio selection problem presented in this paper is formulated as a bi-objective mixed integer program. The portfolio selection problem considered is based on a dynamic model of investment, in which the investor buys and sells securities in successive investment periods. The problem objective is to dynamically allocate the wealth on different securities to optimize by reference point method the portfolio expected return and the probability that the return is not less than a required level. In computational experiments the dataset of daily quotations from the Warsaw Stock Exchange were used.

Sequential Simulated Annealing for the Vehicle Routing Problem with Time Windows
Marcin Woch, Piotr Łebkowski

Abstract: This article presents a new simulated annealing algorithm that provides very high quality solutions to the vehicle routing problem. The aim of described algorithm is to solve the vehicle routing problem with time windows. The tests were carried out with use of some well known instances of the problem defined by M. Solomon. The empirical evidence indicates that simulated annealing can be successfully applied to bi-criterion optimization problems.