PAPERS IN JOURNALS with M. Mohr

PAPERS IN JOURNALS
How Much is it Worth to Know the Future in Online Conversion
Problems?
with M. Mohr
Discrete Applied Mathematics
Vol. 161, page 1546–1555, 2013
We answer this question using the competitive ratio as an indicator for the
quality of information about the future. Analytical results show that the better
the information the better the worst-case competitive ratios. However,
experimental analysis gives a slightly different view. We calculate the
empirical-case competitive ratios of different variants of a threat-based online
algorithm. The results are based on historical data of the German Dax-30
index. We compare our experimental empirical-case results to the analytical
worst-case results given in the literature. We show that better information
does not always lead to a better performance in real life applications. The
empirical-case competitive ratio is not always better with better information,
and some a-priori information is more valuable than other for practical
settings.
Experimental Analysis of an Online Trading Algorithm
with E. Mohr, M. Kersch
Electronic Notes in Discrete Mathematics
Vol. 36, page 519-526, 2010
Trading decisions in financial markets can be supported by the use of online
algorithms. We evaluate the empirical performance of a threat-based online
algorithm and compare it to a reservation price algorithm, an average price
algorithm and to buy-and-hold. The algorithms are analyzed from a worst
case and an empirical case point of view. The effectiveness of the algorithms
is analyzed with historical DAX-30 prices for the years 1998 to 2007. The
performance of the threat-based algorithm found in the simulation runs
dominates all other investigated algorithms. We also compare its
performance to results from worst case analysis and conduct a t-test.
Polynomial-time approximation schemes for two-machine open
shop scheduling with nonavailability constraints
with V. Strusevich, M. Kubzin, J. Breit
Naval Research Logistics
Vol. 53(1), page 16-23, 2005
This paper addresses a two-machine open shop scheduling problem, in
which the machines are not continuously available for processing. The
processing of an operation affected by a non-availability interval can be
interrupted and resumed later. The objective is to minimize the makespan.
We present two polynomial-time approximation schemes, one of which
handles the problem with one non-availability interval on each machine and
the other for the problem with several non-availability intervals on one of the
machines. Problems with a more general structure of the non-availability
intervals are not approximable in polynomial time within a constant factor
Parallel processor scheduling with limited number of
preemptions
with O. Braun
SIAM Journal on Computing
Vol. 32(3), page 671-680, 2003
In this paper, we compare the makespan of preemptive and i-preemptive
schedules where only a limited number i of preemptions is allowed. The
problem is to schedule n independent jobs on m identical processors that
operate in parallel. The objective is to minimize the makespan, i.e., the
completion time of the last job that finishes. We show that the ratio of the
optimal i-preemptive schedule length ${C_{max}^{ip^*}}$ versus the optimal
preemptive schedule length ${C_{max}^{p^*}}$ is bounded from above by
${C_{max}^{ip^*}} \le {( 2 - 2 / (m/(i+1) + 1) )} {C_{max}^{p^*}}$. Furthermore,
we show that the ratio of the length ${C_{max}^{LPT}}$ of a nonpreemptive
schedule following the {\it longest processing time (LPT)} rule versus the
optimal preemptive schedule length ${C_{max}^{p^*}}$ is bounded from
above by exactly the same bound when i=0.
Non-preemptive two-machine open shop scheduling with nonavailability constraints
with J. Breit, V.A. Strusevich
Mathematical Methods of Operations Research
Vol. 57, page 217-234, 2003
We study a two-machine open shop scheduling problem, in which the
machines are not continuously available for processing. No preemption is
allowed in the processing of any operation. The objective is to minimize the
makespan. We consider approximability issues of the problem with more
than one non-availability intervals and present an approximation algorithm
with a worst-case ratio of 4/3 for the problem with a single non-availability
interval.
Stability of Johnson's schedule with respect to liwithed
machine availability
with O. Braun, T. Lai, Y. Sotskov
International Journal of Production Research
Vol. 40(17), page 4381-4400, 2002
The paper deals with the scheduling problem of minimizing the makespan in
the two -machine n -job flow-shop with w non-availability intervals on each of
the two machines. This problem is binary NP-hard even if there is only one
non-availability interval ( w = 1) either on the first machine or on the second
machine. If there are no non-availability intervals on any machine ( w = 0),
the two-machine flow-shop problem may be easily solved using Johnson's
permutation of n jobs. We derived sufficient conditions for optimality of
Johnson's permutation in the case of the given w S 1 non-availability
intervals. The instrument we use is stability analysis, which answers the
question of how stable an optimal schedule is if there are independent
changes in the processing times of the jobs. The stability analysis is
demonstrated on a huge number of randomly generated two -machine flowshop problems with 5 h n h 10 000 and 1 h w h 1000.
2
A polynomial algorithm for lot-size scheduling of two task types
with M. Kovalyov, M. Pattloch
Information Processing Letters
Vol. 83, page 229-235, 2002
We study the problem of scheduling unit time tasks of two types on m
parallel identical machines. For each type, given numbers of tasks are
required to be completed by the specified deadlines. These tasks leave the
system at the deadlines. The in-process inventory capacities are given. The
objective is to construct a schedule that minimizes the number of
changeovers occurring between the tasks of different types. This problem
arises, for instance, in the production of gear-boxes on transfer lines and in
the tobacco industry. Pattloch and Schmidt [Discrete Appl. Math. 65 (1996)
409–419] give an O(mH) algorithm to solve this problem where H is the latest
deadline. We present here a modification of that algorithm with
O(Kmin{K,m}) time complexity where K is the number of deadlines.
Two-machine flow shops with limited machine availability
with J. Blazewicz, J. Breit, P. Formanowicz, W. Kubiak
European Journal of Operational Research
Vol. 136, page 528-540, 2002
This paper studies a flow shop where machines have some periods of limited
availability. The limited availability may be due to preschedules, preventive
maintenance, or overlap of two consecutive time horizons in the rolling time
horizon planning algorithm. It is shown that the problem of minimizing
makespan in such a flow shop is NP-hard in the strong sense, and that no
polynomial time heuristic with constant relative error exists for the problem
unless P=NP. Some important properties of optimal schedules are proved for
two-machine flow shops. A branch and bound algorithm based on these
properties is proposed, and results of computational experiments with the
algorithm are presented.
Two-machine open shop scheduling with an availability
constraint
with J. Breit, V. Strusevich
Operations Research Letters
Vol. 29, page 65-77, 2001
We study a two-machine open shop scheduling problem, in which one
machine is not available for processing during a given time interval. The
objective is to minimize the makespan. We show that the problem is NP-hard
and present an approximation algorithm with a worst-case ratio of <
Heuristic algorithms for the two-machine flowshop with limited
machine availability
with J. Blazewicz, J. Breit, P. Formanowicz, W. Kubiak
Omega
Vol. 29, page 599-608, 2001
The paper studies a flowshop scheduling problem where machines are not
available in given time intervals. The objective is to minimize the makespan.
The problem is known to be NP-hard for two machines. We analyze
constructive and local search based heuristic algorithms for the two-machine
case. The algorithms are tested on easy and difficult test problems with up to
100 jobs and 10 intervals of non-availability. Computational results show that
the algorithms perform well. For many problems an optimum solution is
found.
3
Heuristic algorithms for a lotsize scheduling with application in
the tobacco industry
with M. Kovalyov, M. Pattloch
Computers & Industrial Engineering
Vol. 39, page 235-253, 2001
We investigate a production planning problem which appears in many
industries. We present an example from the tobacco industry. The basic
question is how tasks of different types can be scheduled on machines in
lots such that the number of changeovers is minimized. These changeovers
occur if two tasks of different types are scheduled in sequence on a
machine. We analyze the problem in detail and present heuristics for the
single and multiple machine case. We evaluate these heuristics and give
recommendations for their application to serial production systems.
Scheduling with unexpected machine breakdowns
with S. Albers
Discrete Applied Mathematics
Vol. 110, page 85-99, 2001
We investigate an online version of a basic scheduling problem where a set
of jobs has to be scheduled on a number of identical machines so as to
minimize the makespan. The job processing times are known in advance and
preemption of jobs is allowed. Machines are non-continuously available, i.e.,
they can break down and recover at arbitrary time instances not known in
advance. New machines may be added as well. Thus machine availabilities
change online. We first show that no online algorithm can construct optimal
schedules. We also show that no online algorithm can achieve a bounded
competitive ratio if there may be time intervals where no machine is
available. Then we present an online algorithm that constructs schedules
with an optimal makespan of CmaxOPT if a lookahead of one is given, i.e.,
the algorithm always knows the next point in time when the set of available
machines changes. Finally, we give an online algorithm without lookahead
that constructs schedules with a nearly optimal makespan of CmaxOPT+ε,
for any ε>0, if at any time at least one machine is available. Our results
demonstrate that not knowing machine availabilities in advance is of little
harm.
Performance Guarantee of Two Simple Priority Rules for
Production Scheduling
International Journal of Production Economics
Vol. 26(2), page 151-159, 2000
The paper presents analytical results concerning algorithms applied to o!-line
and on-line production scheduling problems. A problem is solved o!-line if all
the required information to solve it is known in advance; it is solved on-line if
only incomplete knowledge about the entire problem input is available.
Production planning is related to o!-line scheduling and production control
requires on-line scheduling. We present algorithms for both types of
problems concentrating on machines with limited availability and show how
the solution quality of two simple scheduling rules can be guaranteed in
terms of a worst-case analysis
4
Scheduling preemptable tasks on parallel processors with
limited availability
with J. Blazewicz, M. Drozdowski, P. Formanowicz, W. Kubiak
Parallel Computing
Vol. 26, page 1195-1211, 2000
It is well known that in the majority of cases the problem of preemptive task
scheduling on m parallel identical processors with the objective of minimizing
makespan can be solved in polynomial time. For example, for tree-like
precedence constraints the algorithm of Muntz and Coffman can be applied.
In this paper, this problem is generalized to cover the case of parallel
processors which are available in certain time intervals only. It will be shown
that this problem becomes NP-hard in the strong sense in case of trees and
identical processors. If tasks form chains and are processed by identical
processors with a staircase pattern of availability, the problem can be solved
in low-order polynomial time for Cmax criterion, and a linear programming
approach is required for Lmax criterion. Network flow and linear programming
approaches will be proposed for independent tasks scheduled on,
respectively, uniform and unrelated processors with arbitrary patterns of
availability for schedule length and maximum lateness criteria.
Strategic, tactical and operational decisions in multi-national
logistics networks: a review and discussion of modeling issues
with W.E. Wilhelm
International Journal of Production Research
Vol. 38 (7), page 1501-1523, 2000
The rapidly developing worldwide marketplace is leading to the geographical
dispersion of production, assembly and distribution operations. This paper
deals with three aspects of international logistics networks: strategic, tactical
and operational. The strategic level designs the logistics network, including
prescribing facility locations, production technologies and plant capacities.
The tactical level prescribes material flow management policies, including
production levels at all plants, assembly policy, inventory levels, and lot
sizes. The operational level schedules operations to assure in-time delivery
of final products to customers. This paper reviews the literature that deals
with strategic, tactical and operational levels and discusses relevant
modelling issues.
Invited Review: Scheduling with limithed machine availability
European Journal of Operational Research
Vol. 121, page 1-15, 2000
This paper reviews results related to deterministic scheduling problems
where machines are not continuously available for processing. There might
be incomplete information about the points of time machines change
availability. The complexity of single and multi machine problems is analyzed
considering criteria on completion times and due dates. The review mainly
covers intractability results, polynomial optimization and approximation
algorithms. In some places too results from enumerative algorithms and
heuristics are surveyed.
5
Machine scheduling with availability constraints
with E. Sanlaville
Acta Informatica
Vol. 35, page 795-811, 1998
We will give a survey on results related to scheduling problems where
machines are not continuously available for processing. We will deal with
single and multi machine problems and analyze their complexity. We survey
NP-hardness results. Polynomial optimization and approximation algorithms.
We also distinguish between on-line and off-line formulations of the
problems. Results are concerned with criteria on completions times and due
dates.
Case-based reasoning for production scheduling
International Journal of Production Economics
Vol. 56-57(1-3), page 537-546, 1998
We will present an information system supporting decision making in the
area of production scheduling. The system relies on an interactive approach
of problem solving which is known in the area of Artificial Intelligence under
the name case-based reasoning. It tries to solve new problems using results
from old solved problems. While iterative solution procedures try to tackle
problems from the scratch, case-based reasoning takes advantage from
analogies between cases.
We merge case-based reasoning with the theory of scheduling to solve
production planning and control problems using an interactive problem
solving framework. We demonstrate the implementation of this approach
where open problems are matched with well-tried solution strategies and
their corresponding cases which are stored in a library of cases. We discuss
the pros and cons of the approach.
A framework for decision support systems for scheduling
problems
with K. Ecker, J.N.D. Gupta
European Journal of Operational Research
Vol. 101(3), page452-462, 1997
Considering a decision support system as a tool where executive's judgment
can be included along with the mathematical tool kit of the management
scientist, this paper shows the need to include problem management as an
integral component of the decision support system for scheduling problems.
A methodology based on the resolution of conflicts among various
constraints in scheduling problems is proposed to implement the problem
management system in a decision support system for these problems. The
paper concludes with some guidelines to create a workable framework for
providing effective decision support to solve scheduling problems and the
identification of some fruitful directions for future research.
6
Modelling production scheduling systems
International Journal of Production Economics
Vol. 46-47, page 109-118, 1996
Effective production scheduling plays a vital role in modern production
processes. The complexity of scheduling requires efficient representation
and solution methods for the underlying problems. Analysis and design of
information systems for production scheduling challenges two research
areas which are scheduling theory and software engineering. The
approaches of either disciplines have to be harmonized. With this objective a
model is presented which shows how object-oriented data structures and
efficient problem solving can be combined. The model is generated with
special regard to a restricted set of problems. Nevertheless, it can be easily
customized to broader fields of applications. With this some object-oriented
reference model is given for design and implementation of production
scheduling software.
Lotsize scheduling of two types of jobs on identical machines
with M. Pattloch
Discrete Applied Mathematics
Vol. 65, page 409-419, 1996
The problem of scheduling a collection of different jobs on identical parallel
machines is investigated. For each job a number of unit processing time
tasks, a given deadline and an upper bound on inventory are known. The
optimality criterion is changeover cost which occur if different types of jobs
are processed in sequence. Only unit cost are to be considered. For two job
types, an efficient algorithm is presented considering only tight schedules; if
more job types have to be considered the problem becomes NP-hard.
Scheduling independent multiprocessor tasks on a uniform kprocessor system
with J. Blazewicz, M. Drozdowski, D. de Werra
Parallel Computing
Vol. 20, page 15-28, 1994
The problem to be addressed is one of scheduling multiprocessor tasks,
some of which require more than one processor at a time. We extend this
model by introducing a uniform k-processor system consisting of k-tuples of
processors having the same speeds. A low order polynomial-time preemptive
scheduling algorithms is proposed when schedule length is the performance
measure.
A decision support system for production scheduling
Journal of Decision Systems 1 (2-3)
Vol. 1(2-3), page 243-260, 1992
Production scheduling is part oft the production planning, control and
execution process, which covers everything from designing to manufacturing
a product. From a planning point of view, scheduling is done on an
operational and shop floor level. Most of the existing informations systems
for production planning, and control have great deficiencies in their
scheduling parts. The main reasons for this are the inherent difficulties of the
arising question like combinatorial problem complexity and the difficulty in
responding quickly to a dynamic and unpredictable job shop environment
(machine breakdowns, rush orders, extra work etc.). This shop floor planning
and control must be couplet with intelligent scheduling and brought close to
7
the objects to be scheduled. For this purpose we have designed a Decision
Support System which makes appropriate use of combinatorial optimization,
knowledge-based and simulation techniques to help to solve the production
scheduling problem.
Integration von Expertensystem- und konventioneller Software
am Beispiel der Aktienportfolio-zusammenstellung (Integrating
expert systems and conventional information systems using an
example from portfolio selection)
with B. Lahl
Wirtschaftsinformatik
Vol. 33(2), page 123-130, 1991
Die
Synthese
von
konventionellen
Anwendungssystemen
und
Expertensystemen ist ein Ziel bei der Entwicklung wissensbassierter
Systeme. In diesem Beitrag wird eine entsprechende Kopplung am Beispiel
einer Lösung für die Anlageberatung vorgestellt.
Ein XPS-Prototyp zur Bestimmung optimaler Aktienportfolios (A
XPS-prototype for optimal portfolio selection of shares)
with B. Lahl
Künstliche Intelligenz
Vol. 3, page 64-67, 1990
Scheduling independent two processor tasks on a uniform duoprocessor system
with J. Blacewicz, M. Drozdowski, D. de Werra
Discrete Applied Mathematics
Vol. 28, page 11-20, 1990
The problem to be addressed is one of scheduling multiprocessor tasks,
some of which require more than one processor at a time. We extend this
model by introducing uniform duo-processor systems consisting of pairs of
processors having the same speeds. A low order polynomial-time algorithm
for preemptive scheduling of uni- and two-processor tasks is proposed, when
schedule length is the performance measure.
New trends in machine scheduling
with J. Blazewicz, G. Finke, R. Haupt
European Journal of Operational Research
Vol. 37, page 303-317, 1988
This review is concerned with new directions in deterministic machine
scheduling theory. We study: resource constrained scheduling, scheduling
tasks that require more than one machine at a time, scheduling with
nonlinear speed-resource alloted functions, and scheduling in flexible
manufacturing systems. The two features that distinguish the above
problems are the use of resources in addition to the machines and new
models for the processing of tasks. The study of these models was primarily
motivated by their practical importance. In each case, we overview the
existing results and present solution strategies for particularly chosen
8
problems.
Scheduling independent tasks with deadlines on semi-identical
processors
Journal of the Operational Research Society
Vol. 39, page 271-277, 1988
Given m semi-indentical processors which are parallel processors all working
with the same speed but in different time intervals of availability and n
independent tasks with deadlines, the problem of constructing a feasible preemptive schedule is examines. We show that the number of induced preemptions is proportional to the total number of processing intervals and
deadlines.
A fertilizer transportation problem
Zeitschrift für Operations Research
Vol. 30, page 135-145, 1986
We investigate a multiperiod multicommodity transshipment problem which
arises in the context of fertilizer distribution in the Republic of Indonesia.
Taking the special problem structure into account a model is presented
which considers the dynamic aspect of the pro blem only implicitly and all
commodities can be handled by successive solution where at most two
commodities have to be considered for each subproblem. Hence, the size of
the model makes an implementation on a microcomputer possible.
Netzflußmodelle zur präferenzorientierten dynamischen
Einsatz- und Ablaufplanung (Network flow models for preference
oriented assignment and scheduling)
with G. Kalb, H. Röck
Zeitschrift für Operations Research
Vol. 28, page 283-295, 1984
Eine Gruppe von Personen will in mehreren aufeinander folgenden Perioden
eines längeren Planungszeitraumes verschiedene Tätigkeiten unter
Einhaltung bestimmter Bedingungen durchführen. Zu Beginn jeder aktuellen
Periode geben die Gruppenmitglieder ihre individuellen Wünsche hinsichtlich
Arbeitszeit und Arbeitsinhalt an, indem sie ein Budget von Präferenzpunkten
entsprechend auf die in dieser Periode noch offenen Tätigkeiten und Zeiten
vergeben. Die Budgets werden dynamisch fortgeschrieben. Ziel ist es, so
zuzuordnen, daß, über den Planungszeitraum insgesamt gesehen, ein
qualifizierter Ausgleich der individuellen Wünsche erreicht wird. Das
Zuordnungsproblem der aktuellen Periode wird als Netzflußmodell formuliert.
Mögliche Handhabungsweisen dieses Ansatzes im Sinne fortlaufender
Planung werden diskutiert
9
Scheduling on semi-identical processors
Zeitschrift für Operations Research
Vol. 28, page 153-162, 1984
Given m parallel processors each of them having the same speed but
different intervals of availability, the problem of constructing a preemptive
schedule forn independent tasks which completes each task in the given
intervals is examined. We present an 0 (n+m logm) time algorithm to obtain
such a schedule if there exists one. We show that the number of induced
preemptions is proportional to the total number of processing intervals of all
processors.
10