License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SEA.2018.5
URN: urn:nbn:de:0030-drops-89402
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/8940/
Go to the corresponding LIPIcs Volume Portal

Matsumoto, Kosuke ; Hatano, Kohei ; Takimoto, Eiji

Decision Diagrams for Solving a Job Scheduling Problem Under Precedence Constraints

pdf-format:
LIPIcs-SEA-2018-5.pdf (0.5 MB)

Abstract

We consider a job scheduling problem under precedence constraints, a classical problem for a single processor and multiple jobs to be done. The goal is, given processing time of n fixed jobs and precedence constraints over jobs, to find a permutation of n jobs that minimizes the total flow time, i.e., the sum of total wait time and processing times of all jobs, while satisfying the precedence constraints. The problem is an integer program and is NP-hard in general. We propose a decision diagram pi-MDD, for solving the scheduling problem exactly. Our diagram is suitable for solving linear optimization over permutations with precedence constraints. We show the effectiveness of our approach on the experiments on large scale artificial scheduling problems.

BibTeX - Entry

@InProceedings{matsumoto_et_al:LIPIcs:2018:8940,
  author =	{Kosuke Matsumoto and Kohei Hatano and Eiji Takimoto},
  title =	{{Decision Diagrams for Solving a Job Scheduling Problem Under Precedence Constraints}},
  booktitle =	{17th International Symposium on Experimental Algorithms  (SEA 2018)},
  pages =	{5:1--5:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-070-5},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{103},
  editor =	{Gianlorenzo D'Angelo},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/8940},
  URN =		{urn:nbn:de:0030-drops-89402},
  doi =		{10.4230/LIPIcs.SEA.2018.5},
  annote =	{Keywords: decision diagram, permutation, scheduling, NP-hardness, precedence constraints, MDD}
}

Keywords: decision diagram, permutation, scheduling, NP-hardness, precedence constraints, MDD
Collection: 17th International Symposium on Experimental Algorithms (SEA 2018)
Issue Date: 2018
Date of publication: 19.06.2018
Supplementary Material: Source codes are available at https://bitbucket.org/kohei_hatano/pimdd/.

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI