Precedence theorems and dynamic programming for the single-machine weighted tardiness problem
| Autor: | Stefan Creemers, Salim Rostami, Roel Leus |
|---|---|
| Přispěvatelé: | Lille économie management - UMR 9221 (LEM), Université d'Artois (UA)-Université catholique de Lille (UCL)-Université de Lille-Centre National de la Recherche Scientifique (CNRS), Operations Research and Business Statistics (ORSTAT), Catholic University of Leuven - Katholieke Universiteit Leuven (KU Leuven) |
| Jazyk: | angličtina |
| Rok vydání: | 2019 |
| Předmět: |
Mathematical optimization
Information Systems and Management General Computer Science Relation (database) Tardiness 0211 other engineering and technologies 02 engineering and technology Management Science and Operations Research Space (commercial competition) Dynamic programming Industrial and Manufacturing Engineering Scheduling (computing) [SHS]Humanities and Social Sciences 0502 economics and business Precedence constraints Weighted tardiness Mathematics 050210 logistics & transportation 021103 operations research Scheduling 05 social sciences Network density Memory management Modeling and Simulation [SHS.GESTION]Humanities and Social Sciences/Business administration Single machine |
| Zdroj: | European Journal of Operational Research European Journal of Operational Research, 2019, 272 (1), pp.43-49. ⟨10.1016/j.ejor.2018.06.004⟩ European Journal of Operational Research, Elsevier, 2019, 272 (1), pp.43-49. ⟨10.1016/j.ejor.2018.06.004⟩ |
| ISSN: | 0377-2217 1872-6860 |
| Popis: | © 2018 Elsevier B.V. We tackle precedence-constrained sequencing on a single machine in order to minimize total weighted tardiness. Classic dynamic programming (DP) methods for this problem are limited in performance due to excessive memory requirements, particularly when the precedence network is not sufficiently dense. Over the last decades, a number of precedence theorems have been proposed, which distinguish dominant precedence constraints for a job pool that is initially without precedence relation. In this paper, we connect and extend the findings of the foregoing two strands of literature. We develop a framework for applying the precedence theorems to the precedence-constrained problem to tighten the search space, and we propose an exact DP algorithm that utilizes a new efficient memory management technique. Our procedure outperforms the state-of-the-art algorithm for instances with medium to high network density. We also empirically verify the computational gain of using different sets of precedence theorems. ispartof: EUROPEAN JOURNAL OF OPERATIONAL RESEARCH vol:272 issue:1 pages:43-49 status: published |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect