Empirical Transformation of Job Shop Scheduling Problem to the Hydraulic Networks Problem in a Water Distribution System

Author

Cruz-Chávez, Marco Antonio ; Avila-Melgar, Erika Yesenia ; Pérez, Fredy Juárez ; Torres-Sánchez, Wiston G.

Author_Institution

CIICAp, Univ. Autonoma del Estado de Morelos, Cuernavaca, Mexico

fYear

2009

fDate

22-25 Sept. 2009

Firstpage

76

Lastpage

81

Abstract

In this paper an analogy of the job shop scheduling problem to the hydraulic networks problem is presented by mapping this model of scheduling, using as a base the disjunctive graph model. The mapping carried out allows visualization of the hydraulic networks problem as an NP-complete model with constraints defined in the job shop scheduling problem. The mapping presented indicates that the hydraulic networks problem is a difficult problem to solve by using an approach with the constraints of an NP-complete problem.

Keywords

computational complexity; graph theory; job shop scheduling; water supply; NP-complete model; disjunctive graph model; hydraulic network problem; job shop scheduling problem; water distribution system; Automotive engineering; Costs; Job shop scheduling; Mesh networks; NP-complete problem; NP-hard problem; Polynomials; Quality of service; Robots; Visualization;

fLanguage

English

Publisher

ieee

Conference_Titel

Electronics, Robotics and Automotive Mechanics Conference, 2009. CERMA '09.

Conference_Location

Cuernavaca, Morelos

Print_ISBN

978-0-7695-3799-3

Type

conf

DOI

10.1109/CERMA.2009.33

Filename

5342010