Universität zu Köln

Sequential matching problem

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

[img]
Preview
PDF
Download (1217Kb) | Preview

    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:
    AbstractLanguage
    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:
    CreatorsEmail
    Karichery, Sureshantausch@ub.uni-koeln.de
    URN: urn:nbn:de:hbz:38-12902
    Subjects: Data processing Computer science
    Uncontrolled Keywords:
    KeywordsLanguage
    Sequential Matching Problem, NP-vollständige Problem, Branch&Price-Verfahren, HeuristikGerman
    Sequential Matching Problem, NP-completeness, Branch and price scheme, Heuristic methodsEnglish
    Faculty: Mathematisch-Naturwissenschaftliche Fakultät
    Divisions: Mathematisch-Naturwissenschaftliche Fakultät > Keine Angabe
    Language: English
    Date: 2004
    Date Type: Completion
    Date of oral exam: 23 May 2004
    Full Text Status: Public
    Date Deposited: 25 Oct 2004 11:01:46
    Referee
    NameAcademic Title
    Schrader, RainerProf. Dr.
    URI: http://kups.ub.uni-koeln.de/id/eprint/1290

    Actions (login required)

    View Item