1 Search Results for "Takimoto, Eiji"


Document
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-dev.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}
}
  • Refine by Author
  • 1 Hatano, Kohei
  • 1 Matsumoto, Kosuke
  • 1 Takimoto, Eiji

  • Refine by Classification
  • 1 Theory of computation → Data structures design and analysis

  • Refine by Keyword
  • 1 MDD
  • 1 NP-hardness
  • 1 decision diagram
  • 1 permutation
  • 1 precedence constraints
  • Show More...

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2018

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail