DROPS

Document

DOI: 10.4230/LIPIcs.SEA.2018.5

Decision Diagrams for Solving a Job Scheduling Problem Under Precedence Constraints

Authors: Kosuke Matsumoto, Kohei Hatano, and Eiji Takimoto

Published in: LIPIcs, Volume 103, 17th International Symposium on Experimental Algorithms (SEA 2018)

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.

Cite as

Kosuke Matsumoto, Kohei Hatano, and Eiji Takimoto. Decision Diagrams for Solving a Job Scheduling Problem Under Precedence Constraints. In 17th International Symposium on Experimental Algorithms (SEA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 103, pp. 5:1-5:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{matsumoto_et_al:LIPIcs.SEA.2018.5,
  author =	{Matsumoto, Kosuke and Hatano, Kohei and Takimoto, Eiji},
  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 =	{D'Angelo, Gianlorenzo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2018.5},
  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}
}

Search Results

Documents authored by Hatano, Kohei

Decision Diagrams for Solving a Job Scheduling Problem Under Precedence Constraints

Abstract

Cite as

Thanks for your feedback!

Could not send message