| Autor: |
Chu, Chengbin, Proth, Jean-Marie |
| Přispěvatelé: |
Simulation, analyse et gestion des systèmes de production (SAGEP), INRIA Lorraine, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), INRIA |
| Jazyk: |
angličtina |
| Rok vydání: |
1994 |
| Předmět: |
|
| Zdroj: |
[Research Report] RR-2268, INRIA. 1994, pp.16 |
| Popis: |
We consider a single machine scheduling problem. This problem has been solved for a medical laboratory. It comprises not only chain-structured precedence constraints, but also minimal and maximal times separating successive jobs in the same chain. The criterion to be minimized is the makespan. This problem arises particularly in systems where chemical processes are involved. Consider a chemical plant in which every chemical process is a sequence of chemical reactions the duration of which is upper and lower bounded. Between two successive chemical reactions which are performed in different locations, a transportation system such as robot is used to carry the product from place to place. In this kind of plant, jobs are transportation operations and production processes can be modeled as chains. Therefore the problem studied in this paper is of practical importance. We first prove that the problem is NP-complete. As a consequence, we propose heuristics for large size problems and a branch and bound based algorithm for small size problems. Computational results are reported. |
| Databáze: |
OpenAIRE |
| Externí odkaz: |
|
