Decision Making in Manufacturing and Services
Loading...
ISSN 1896-8325
e-ISSN: 2300-7087
Issue Date
2009
Volume
Vol. 3
Number
No. 1/2
Description
Journal Volume
Decision Making in Manufacturing and Services
Vol. 3 (2009)
Projects
Pages
Articles
On efficient coloring of chordless graphs
(Wydawnictwa AGH, 2009) Janczewski, Robert; Małafiejski, Michał
We are given a simple graph $G=(V,E)$. Any edge $e \in E$ is a chord in a path $P \subseteq G$ (cycle $C \subseteq G$) iff 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 <i>pathchordless</i> (<i>cycle-chordless</i>). We will prove that recognizing and coloring of these graphs can be done in $O(n^{2})$ 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
(Wydawnictwa AGH, 2009) Kaczmarczyk, Waldemar
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 modelling lot-sizing and scheduling problems
(Wydawnictwa AGH, 2009) Kaczmarczyk, Waldemar
This paper presents some important alternatives for modelling Lot-Sizing and Scheduling Problems. First, the accuracy of models can improved by using short time buckets, which allow more detailed planning but lead to higher computational effort. Next, valid inequalities make the models tighter but increase their size. Sometimes it is possible to find a good balance between the size and tightness of a model by limiting a priori the number of valid inequalities. Finally, a special normalization of the variables simplifies the presentation of results and validation of models.
Robust buffer allocation for scheduling of a project with predefined milestones
(Wydawnictwa AGH, 2009) Klimek, Marcin; Łebkowski, Piotr
The paper discusses the problem of robust buffer allocation for Resource-Constrained Project Scheduling Problem (RCPSP) with predefined milestones1 , 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 tasks2 included in the Project Scheduling Problem Library (PSPLIB) with additionally specified project milestones.
A reference point approach to bi-objective dynamic portfolio optimization
(Wydawnictwa AGH, 2009) Sawik, Bartosz
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.