On Not-First/Not-Last conditions in disjunctive scheduling
| العنوان: | On Not-First/Not-Last conditions in disjunctive scheduling |
|---|---|
| المؤلفون: | Philippe Torres, Pierre Lopez |
| المساهمون: | Laboratoire d'analyse et d'architecture des systèmes (LAAS), Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT)-Université de Toulouse (UT)-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Université de Toulouse (UT)-Institut National des Sciences Appliquées (INSA)-Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université de Toulouse (UT), Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université Fédérale Toulouse Midi-Pyrénées, Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS)-Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées-Institut National des Sciences Appliquées - Toulouse (INSA Toulouse), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Institut National Polytechnique (Toulouse) (Toulouse INP) |
| المصدر: | European Journal of Operational Research European Journal of Operational Research, 2000, 127 (2), pp.332-343. ⟨10.1016/S0377-2217(99)00497-X⟩ European Journal of Operational Research, Elsevier, 2000, 127 (2), pp.332-343. ⟨10.1016/S0377-2217(99)00497-X⟩ |
| بيانات النشر: | Elsevier BV, 2000. |
| سنة النشر: | 2000 |
| مصطلحات موضوعية: | Mathematical optimization, Information Systems and Management, General Computer Science, Job shop, Disjunctive scheduling, 0211 other engineering and technologies, 02 engineering and technology, Management Science and Operations Research, Industrial and Manufacturing Engineering, [INFO.INFO-AI]Computer Science [cs]/Artificial Intelligence [cs.AI], Scheduling (computing), Bounding overwatch, [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], 0202 electrical engineering, electronic engineering, information engineering, Rule of inference, Mathematics, 021103 operations research, Branch and bound, Efficient algorithm, Lower bounds, Constraint propagation, Time-bound adjustments, Edge-finding, Modeling and Simulation, Release date, Local consistency, 020201 artificial intelligence & image processing |
| الوصف: | International audience; This paper is concerned with the development of constraint propagation techniques for the characterization of feasible solutions in disjunctive scheduling. In disjunctive scheduling, a set of uninterruptible tasks is to be performed on a set of resources. Each task has a release date, a deadline, and a fixed processing time; each resource can handle only one task at a time. Some of these propagation techniques are implemented by rules that deduce either mandatory or forbidden sequences between tasks or sets of tasks. For instance, certain rules indicate whether a given task must or cannot be performed before or after a set of other competing tasks. We focus our attention on the latter problem, known as the ``Not-First/Not-Last" problem. The genericity of propagation rules is a question of major importance. It induces that the result of the overall propagation must not depend on the order in which the inference rules are applied. Hence, one must search for completeness in the time-windows narrowing, in order to ensure the convergence of the propagation towards a unique fix-point. An efficient algorithm is proposed. It guarantees the completeness of time-windows narrowing due to not-first/not-last conditions. It has been integrated in a branch and bound procedure to solve job-shop instances. It has also been tested within several lower bounding procedures. Computational results are reported and the power and complementarity of not-first/not-last rules with other classical inference rules is discussed. |
| تدمد: | 0377-2217 1872-6860 |
| URL الوصول: | https://explore.openaire.eu/search/publication?articleId=doi_dedup___::624e5dbccf1d93555363dc369a7444b4 https://doi.org/10.1016/s0377-2217(99)00497-x |
| حقوق: | OPEN |
| رقم الأكسشن: | edsair.doi.dedup.....624e5dbccf1d93555363dc369a7444b4 |
| قاعدة البيانات: | OpenAIRE |
| تدمد: | 03772217 18726860 |
|---|