Dissertation: Selected Scheduling Applications

Selected Scheduling Applications

– in englischer Sprache –

QM – Quantitative Methoden in Forschung und Praxis, Band 38

Hamburg 2015, 176 Seiten
ISBN 978-3-8300-8239-2 (Print), ISBN 978-3-339-08239-8 (eBook)

Ablaufplanung, Betriebswirtschaftslehre, Computational Complexity, Machine Scheduling, Mixed-Integer Programming, Movie Scheduling, Operations Research, Rostering, Scheduling, Students Scheduling, Timetabling, Yard-Crime Scheduling and Routing

Zum Inhalt

The first chapter is dedicated to a general introduction into scheduling. Among the basic concepts in scheduling, machine scheduling, general methodologies for solving scheduling problems, scheduling formulations and definitions in computational complexity are illustrated. The first chapter ends with a brief synopsis.

In chapter 2, the yard crane scheduling and routing problem is addressed. More precisely, it is focussed on the job scheduling and crane routing of automated rail-mounted-gantry cranes of storage yards on seaport container terminals. The chapter starts with a brief introduction on seaport container terminals, container flows, terminal operations and the central container storage as well as the regarded twin, double and triple rail-mounted-gantrycrane systems. This is followed by a specification of the yard-crane scheduling and routing problem with respect to the problem decisions which are to be made. Afterwards, a survey of the relevant literature is given. Then mixed-integer programmes, which are based on time-indexed variables, are formulated for the yard-crane scheduling and routing problem for each system. To handle large scale scheduling and routing problem instances, a solution method is developed which is based on a problem decomposition.

Therefore, the whole problem is divided into the scheduling and routing problem which are solved consecutively such that the result of the scheduling problemthe job assignment and sequencing?are used for the calculation of the routing problem. Both methods, the mixed-integer programme and the solution method are analysed numerically on typical problem instances for each crane system. It is found that solving the mixed-integer programmes by commercial solvers are outperformed by the solution method. But even solving the routing problems may lead to long solution times.

In chapter 3, the crane-routing problems for the twin and double railmounted- gantry-crane systems are addressed. At first, a survey of the relevant literature on crane-routing is given. Afterwards, the problem statement is briefly discussed and, in addition, mixed-integer programmes are described for both systems on the basis of the formulations in chapter 2. This is followed by a formulation of a mixed-integer programme with completion time variables for a special single-machine scheduling problem. The programme forms the basis for the reformulation of the crane-routing problem to the machine-scheduling problem. Furthermore, a recursive algorithm for the crane-routing problem is introduced for both systems. The algorithm is formulated using equally long time units with the length of each time unit being equal to the time needed for a crane to move along a single bay.

In addition, a routing problem is split up into new routing (sub-)problems when a crane routing conflict exists and the solved routing subproblems are then combined to the overall optimal solution of the original problem. The mixed-integer programme and the recursive algorithm are analysed numerically based on typical problem instances for each crane system. It is found that both methods can readily be used as a solution method to solve typical instances of the crane-routing problem.

Chapter 4 is dedicated to the movie-scheduling problem. The problem is described first, before the movie exhibitor CinemaxX is introduced as the cooperation partner of the empirical study where at present the preparation of the weekly movie schedules are mostly done manually by staff members. Afterwards, the literature with focus on the movie exhibition business is presented. On the basis of predetermined requirements for the movie scheduling, a mixed-integer programme is formulated with the objective to maximise the total of contribution margins of presented movies together with incomes from concession sales. The application is empirically analysed on real-life scheduling problem instances. Therefore, movie schedules for three consecutive cinema weeks are prepared by solving the mixed-inter programme.

The resulting schedules are compared to the manually generated schedules by CinemaxX. In conclusion, the calculated schedules each have exhibit a better performance than the manually generated schedules and may be used for the preparation of a movie schedule. Moreover, the mixed-integer programme is compared to an existing column-generation approach. It is found that the schedules resulting from the mixed-integer programme lead to better objective values than the schedules which are calculated by the column-generation approach.

In chapter 5, a successful approach for the students-scheduling problem is illustrated and analysed for the School of Business, Economics and Social Sciences of Universitat Hamburg. The general students-scheduling problem is introduced first, before a literature review is presented. Afterwards, the students scheduling problem is formulated as an assignment problem.

Based on predetermined assumptions, a basic mixed-integer programme is modelled and extended with further scheduling requirements in order to take students’ and university staff members’ preferences into account. Then, the implementation and the integration of the operational optimisation progress into the timing of a semester is described for the Business programme at Universitat Hamburg. Finally, computational tests for the basic model as well as for the extensions are carried out with the same real-life timetabling and registration data while preference data, i. e. students’ preferences for the scheduling, are generated artificially. All problem instances are solved easily with a proprietary solver within only a few of seconds.

In general, it should be noted that, because of the remarkable development of hard- and software in computer techniques in the last decade, nowadays it is possible to solve large units of optimisation problems within a few seconds, which could not be solved a few years ago.



Informationen über das Veröffentlichen wissenschaftlicher Arbeiten.

nach oben