Preemptive Hybrid Flowshop Scheduling problem of interval orders |
| |
| Institution: | 1. EuroDecision 9A, rue de la Porte de Buc, 78000 Versailles, France;2. BVASSOCIAT, 18 rue Jean Bart, 78960 Vosins Le Bretonneut, France;1. Graduate Program of Transportation Engineering Military Institute of Engineering, Praça General Tibúrcio 80, Praia Vermelha, Rio de Janeiro, 999074, Brazil;2. Program of Transportation Engineering COPPE/UFRJ. Technology Center, Building H–Room 117, University City–Rio de Janeiro, Rio de Janeiro 999074, Brazil;1. College of Mechanical Science and Engineering, Jilin University, Changchun, China;2. Department of Industrial Management, National Taiwan University of Science and Technology, Taipei, Taiwan;1. RWTH Aachen University, Institute of Transport Science, Mies-van-der-Rohe-Straße 1, 52074, Aachen, Germany;2. RWTH Aachen University, Chair and Institute of Urban and Transport Planning, Mies-van-der-Rohe-Straße 1, 52074, Aachen, Germany;1. Department of Industrial Engineering, Pontifícia Universidade Católica do Rio de Janeiro, 22451-900, Brazil;2. Department of Geography, University of California Santa Barbara, Santa Barbara, CA, 93106-4060, USA;3. Department of Civil Engineering, University of Coimbra, Pólo II, 3030-788 Coimbra, Portugal |
| |
| Abstract: | The Preemptive Hybrid (multi-processor) Flowshop Scheduling (PHFS) problem consists in preemptively scheduling n jobs in a flowshop subject to precedence constraints with the objective of minimizing the makespan. A special case of the general precedence constraints problems is NP-hard in the strong sense, Hoogeveen et al. J.A. Hoogeveen, J.K. Lenstra, B. Veltman, European Journal of Operational Research 89 (1996) 172]. In this paper a class of precedence constraints is proposed for which the problem is polynomially solvable. The reported results demonstrate the feasibility and reliability of the proposed approach. This should open future prospects for developing approximation algorithms for any class of precedence constraints. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
