2026-07-23T19:28:09Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8940 2024-03-06T10:42:54Z ddc:004 open_access

Decision Diagrams for Solving a Job Scheduling Problem Under Precedence Constraints Matsumoto, Kosuke Hatano, Kohei Takimoto, Eiji decision diagram permutation scheduling NP-hardness precedence constraints MDD 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Kosuke Matsumoto and Kohei Hatano and Eiji Takimoto 2018 Is Part Of LIPIcs, Volume 103, 17th International Symposium on Experimental Algorithms (SEA 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SEA.2018.5 urn:nbn:de:0030-drops-89402 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2018.5 eng https://creativecommons.org/licenses/by/3.0/legalcode