Universität zu Köln

Karichery, Sureshan (2004). Sequential matching problem. PhD thesis, Universität zu Köln.

Preview

PDF Thesis.pdf Download (1MB)

Abstract

Kurzfassung in englisch We present sequential matching problem (SMP) as the problem of finding maximal matchings in a sequence of bipartite graphs, with a strategy of making maximum number of common edges in two consecutive matchings. One application of SMP is the problem of assigning workers to jobs in different time shifts with a goal of minimizing total number of unnecessary switches between jobs. We analyze various algorithmic techniques for this NP-complete problem. We also analyze the Mixed Integer Programming (MIP)problem formulation with huge number of variables and their solution by branch and price method, a column generation scheme with branch and bound, of implicit pricing of nonbasic variables to generate new columns. We then discuss special branching rules, pricing problems, implementation issues, and computational results. Finally we analyze a simpler version of SMP with only two bipartite graphs which is still NP-complete, and an algorithm to augment the common edges in the maximum matchings.

Item Type:	Thesis (PhD thesis)
Translated abstract:	Abstract Language Kurzfassung in deutsch Wir stellen das Sequential Matching Problem (SMP) vor. Das SMP beschreibt die Suche einer Folge maximaler Matchings zu einer Folge von gegebenen bipartiten Graphen, die die Anzahl der gemeinsamen Kanten aufeinanderfolgender Matchings maximiert. Eine Anwendungsbeispiel ist das Problem, Arbeitern über einen gewissen Zeitraum Jobs zuzuweisen und dabei die Jobwechsel zu minimieren. Wir analysieren verschiedene algorithmische Techniken für dieses NP-vollständige Problem. Dabei betrachten wir eine Formulierung als gemischt ganzzahliges Problem (MIP) mit einer sehr grosser Zahl von Variablen. Diese Problem lösen wir mit einem Branch&Price-Verfahren, d.h einer Kombination eines Branch&Bound Verfahrens mit einem Column-Generation-Ansatz. Hierbei verwenden wir zur Spaltenerzeugung implizites Pricing von Nichtbasisvariablen. Wir erlautern, die aus den verwendeten Branching-Regeln entstehenden Subprobleme, und gehen auf die Implementierung und die numerischen Ergebnisse ein. Schliesslich analysieren wir den Spezialfall des SMP mit zwei bipartiten Graphen. Auch dieses Problem ist NP-vollstandig. Wir stellen eine Heuristik vor, die Anzahl der gemeinsamen Kanten in den Matchings schrittweise vergrössert. German
Creators:	Creators Email ORCID ORCID Put Code Karichery, Sureshan tausch@ub.uni-koeln.de UNSPECIFIED UNSPECIFIED
URN:	urn:nbn:de:hbz:38-12902
Date:	2004
Language:	English
Faculty:	Faculty of Mathematics and Natural Sciences
Divisions:	Ehemalige Fakultäten, Institute, Seminare > Faculty of Mathematics and Natural Sciences > no entry
Subjects:	Data processing Computer science
Uncontrolled Keywords:	Keywords Language Sequential Matching Problem, NP-vollständige Problem, Branch&Price-Verfahren, Heuristik German Sequential Matching Problem, NP-completeness, Branch and price scheme, Heuristic methods English
Date of oral exam:	23 May 2004
Referee:	Name Academic Title Schrader, Rainer Prof. Dr.
Refereed:	Yes
URI:	http://kups.ub.uni-koeln.de/id/eprint/1290