Bounds and Tabu Search for a Cyclic Max-Min Scheduling Problem

被引：0

作者：

Peter Greistorfer

Hans Kellerer

机构：

[1] Karl-Franzens-Universität Graz,Institut für Industrie und Fertigungswirtschaft

[2] Karl-Franzens-Universität Graz,Institut für Statistik und Operations Research

来源：

Journal of Heuristics | 2001年 / 7卷

关键词：

scheduling; bottleneck problem; bounds; heuristics; Tabu Search;

D O I：

暂无

中图分类号：

学科分类号：

摘要：

A cyclic scheduling problem with applications to transport efficiency is considered. Given a set of regular polygons, whose vertices represent regularly occurring events and are lying on a common circle line, the objective is to maximize the distance between the closest vertices of different polygons on the circle line. Lower and upper bounds for the optimal solution of this NP-hard scheduling problem are presented. They are used to improve the quality of a procedure which is applied to solve this problem heuristically. It consists of a greedy starting algorithm and a Tabu Search algorithm. The numerical results show the efficiency of the procedure proposed.

引用

页码：371 / 390

页数：19

共 16 条

[1]

Brucker P.(1990)Cyclic Schedules for J. Comput. Appl. Math. 30 173-189

[2]

Burkard R.E.(1986) Irregularly Occurring Events Discr. Appl. Math. 15 167-180

[3]

Hurink J.(1972)Optimal Schedules for Periodically Recurring Events Matematické obzory 1 51-59

[4]

Burkard R.E.(1989)Problems for Systems of Regular Polygons on a Circumference and their Application in Transport OR Spektrum 11 17-24

[5]

Cerny J.(1986)Schedule Synchronization for Public Transit Networks Computers Oper. Res. 13 533-549

[6]

Domschke W.(1990)Future Paths for Integer Programming and Links to Artificial Intelligence Interfaces 20 74-94

[7]

Glover F.(1980)Tabu Search: A Tutorial Aplikace Matematiky 25 182-195

[8]

Glover F.(1996)Maximization of Distances of Regular Polygons on a Circle Discr. Appl. Math. 70 37-55

[9]

Guldan F.(1993)Polygon Scheduling Management Sci. 39 492-500

[10]

Hurink J.(1993)Bandwith Packing: A Tabu Search Approach Ann. Oper. Res. 41 421-451

← 1 2 →