Document Open Access Logo

Decision Diagrams for Solving a Job Scheduling Problem Under Precedence Constraints

Authors Kosuke Matsumoto, Kohei Hatano , Eiji Takimoto

PDF
Thumbnail PDF

File

LIPIcs.SEA.2018.5.pdf
  • Filesize: 478 kB
  • 12 pages

Document Identifiers

Author Details

Kosuke Matsumoto
  • Kyushu University
Kohei Hatano
  • Kyushu University / RIKEN AIP
Eiji Takimoto
  • Kyushu University

Funding

This work is supported in part by JSPS KAKENHI Grant Number JP16K00305 and JSPS KAKENHI Grant Number JP15H02667, respectively.

Cite As Get BibTex

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) https://doi.org/10.4230/LIPIcs.SEA.2018.5

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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Data structures design and analysis
Keywords
  • decision diagram
  • permutation
  • scheduling
  • NP-hardness
  • precedence constraints
  • MDD

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Supplementary Materials

References

  1. Sheldon B. Akers. Binary Decision Diagrams. IEEE Transactions on Computers, C-27(6):509-516, 1978. Google Scholar
  2. Christoph Ambühl, Monaldo Mastrolilli, Nikolaus Mutsanas, and Ola Svensson. On the Approximability of Single-Machine Scheduling with Precedence Constraints Christoph Ambühl. Mathematics of Operations Research, 36(4):653-669, 2011. Google Scholar
  3. Randal E. Bryant. Graph-Based Algorithms for Boolean Function Manipulation. IEEE Transactions on Computers, C-35(8):677-691, aug 1986. Google Scholar
  4. Chandra Chekuri and Rajeev Motwani. Precedence constrained scheduling to minimize sum of weighted completion times on a single machine. Discrete Applied Mathematics, 98(1-2):29-38, 1999. Google Scholar
  5. Fabian A. Chudak and Dorit. S. Hochbaum. A half-integral linear programming relaxation for scheduling precedence-constrained jobs on a single machine. Operations Research Letters, 25:199-204, 1999. Google Scholar
  6. André A Ciré and Willem Jan van Hoeve. MDD Propagation for Disjunctive Scheduling. In Proceedings of the 22nd International Conference on Automated Planning and Scheduling (ICAPS'12), 2012. Google Scholar
  7. André A Ciré and Willem-Jan van Hoeve. Multivalued Decision Diagrams for Sequencing Problems. Operations Research, 61(6):1411-1428, 2013. Google Scholar
  8. José R. Correa and Andreas S. Schulz. Single-Machine Scheduling with Precedence Constraints. Mathematics of Operations Research, 30(4):1005-1021, 2005. Google Scholar
  9. Takahiro Fujita, Kohei Hatano, Shuji Kijima, and Eiji Takimoto. Online Linear Optimization for Job Scheduling under Precedence Concstraints. In Proceedings of 26th International Conference on Algorithmic Learning Theory(ALT 2015), volume 6331 of LNCS, pages 345-359, 2015. Google Scholar
  10. Tarik Hadzic, John N Hooker, Barry O'Sullivan, and Peter Tiedemann. Approximate Compilation of Constraints into Multivalued Decision Diagrams. In Proceedings of the 14th International Conference on Principles and Practice of Constraint Programming (CP 2008 ), LNCS 5202, pages 448-462, 2008. Google Scholar
  11. Leslie A. Hall, Andreas S. Schulz, David B. Shmoys, and Joel Wein. Scheduling to Minimize Average Completion Time: Off-Line and On-Line Approximation Algorithms. Mathematics of Operations Research, 22(3):513-544, 1997. Google Scholar
  12. Takeru Inoue, Keiji Takano, Takayuki Watanabe, Jun Kawahara, Ryo Yoshinaka, Akihiro Kishimoto, Koji Tsuda, Shin-ichi Minato, and Yasuhiro Hayashi. Distribution Loss Minimization With Guaranteed Error Bound. IEEE Transactions on Smart Grid, 5(1):102-111, 2014. Google Scholar
  13. Yuma Inoue and Shin-ichi Minato. An Efficient Method for Indexing All Topological Orders of a Directed Graph. In Proceedings of the 25th international Symposium on Algorithms and Computation (ISAAC'14), pages 103-114, 2014. Google Scholar
  14. Donald E. Knuth. The Art of Computer Programming, Volume 4A, Combinatorial Algorithms,Part 1. Addison-Wesley Professional, 2011. Google Scholar
  15. Eugene L. Lawler. On Sequencing jobs to minimize weighted completion time subject to precedence constraints. Annals of Discrete Mathematics 2, 2:75-90, 1978. Google Scholar
  16. Jan K. Lenstra and Alexander H. G. Rinnooy Kan. Complexity of scheduling under precedence constraints. Operations Research, 26:22-35, 1978. Google Scholar
  17. François Margot, Maurice Queyranne, and Yaoguang Wang. Decompositions, Network Flows, and a Precedence Constrained Single-Machine Scheduling ProblemDecompositions, Network Flows, and a Precedence Constrained Single-Machine Scheduling Problem. Operations Research, 51(6):981-992, 2003. Google Scholar
  18. Michael D. Miller. Multiple-Valued Logic Design Tools. In Proceedings of the23rd IEEE International Symposium on Multiple-Valued Logic (ISMVL'93), pages 2-11, 1993. Google Scholar
  19. Michael D. Miller and Rolf Drechsler. Implementing a Multiple-Valued Decision Diagram Package. In Proceedings of the 28th IEEE International Symposium on Multiple-Valued Logic (ISMVL'98), pages 52-57, 1998. Google Scholar
  20. Shin-ichi Minato. Zero-Suppressed BDDs for Set Manipulation in Combinatorial Problems. In Proceedings of the 30th international Design Automation Conference (DAC'93), pages 272-277, 1993. Google Scholar
  21. Shin-ichi Minato. Zero-suppressed BDDs and their applications. International Journal on Software Tools for Technology Transfer, 3(2):156-170, 2001. Google Scholar
  22. Shin-ichi Minato. Efficient Database Analysis Using VSOP Calculator Based on Zero-Suppressed BDDs. In New Frontiers in Artificial Intelligence, Joint JSAI 2005 Workshop Post-Proceedings, pages 169-181, 2005. Google Scholar
  23. Shin-ichi Minato. πDD: A New Decision Diagram for Efficient Problem Solving in Permutation Space. In Proceedings of the 14th International Conference on Theory and Applications of Satisfiability Testing (SAT'11), pages 90-104, 2011. Google Scholar
  24. Andreas S. Schulz. Scheduling to Minimize Total Weighted Completion Time: Performance Guarantees of LP-Based Heuristics and Lower Bounds. In Proceedings of the 5th Conference on Integer Programming and Combinatorial Optimization (IPCO1996), pages 301-315, 1996. Google Scholar
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
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact