Zu einigen Nachbarschaftsgraphen für die Entwicklung geeigneter Iterationsverfahren zur näherungsweisen Lösung eines speziellen Permutationsproblems. (On some neighborhood graphs for the development of suitable iteration methods to approximately solve a special permutation problem). (German) Zbl 0627.90050

Werner, Frank

Wiss. Z. Tech. Univ. Otto von Guericke 31, No. 5, 48-54 (1987).

Verschiedenartige Maschinenbelegungsprobleme führen auf Optimierungsaufgaben über der Menge aller Permutationen der Zahlen von 1 bis m. Ein großer Teil dieser Probleme gehört zur Klasse NP-hard, so daß verstärkt Näherungsverfahren entwickelt werden. In der vorliegenden Arbeit werden spezielle Nachbarschaften zu dem betrachteten Permutationsproblem eingeführt und die zuhörigen Strukturgraphen auf ihre Eigenschaften untersucht.

MSC:

90B35	Deterministic scheduling theory in operations research
90C35	Programming involving graphs or networks

Keywords:

approximate solution; neighborhood graphs; permutation problem