A new characterization of atomic stable parts for a partial order relation applied to the one-machine scheduling problem

Authors

  • E. M. Amamou CREHEIO, Centre de Recherche de l’Ecole des Hautes Etudes d’Ingénierie OUJDA, Morocco
  • S. Khoukhi CREHEIO, Centre de Recherche de l’Ecole des Hautes Etudes d’Ingénierie OUJDA, Morocco
  • A. Benbouazza CREHEIO, Centre de Recherche de l’Ecole des Hautes Etudes d’Ingénierie OUJDA, Morocco

Keywords:

Order relation, stable parts, bipartite graph, canonical components, irreducible sub graphs, rank matrix, scheduling.

Abstract

A set E endowed with a partial order relation Ɍ can be decomposed into subsets called “atomic stable parts” for Ɍ, totally ordered. These atomic stable parts are the equivalence classes of an equivalence relation T (®) [1]. In fact if S(x) is the atom containing x (x Є E) and E endowed with the partial order relation Ɍ), then Cl(x) is the equivalence class of x for the equivalence relation T (®) defined by: x,y)Є E 2 , x® y <==> not (x Ɍ y or y Ɍ x); (® is a symmetric relation by construction. Its transitive closure T (®) is an equivalence relation [2]. In this article we propose a new characterization of the atomic stable parts for Ɍ. The approach consists in defining a square matrix B called matrix of “Ranks” from the relation Ɍ whose coefficients are Boolean (bij = 0 or 1) [3] , [4], [5]. This matrix B represents a bipartite graph G. An interpretation of the canonical components of the bipartite graph will allow us to characterize the atomic stable parts of the set E endowed with Ɍ. We indeed show that in the irreducible sub graphs Gi of G (Gi (Si,Ti ;A(Gi)), the subsets Si of E (i=1,….,k) are the atomic stable parts for the partial order relation Ɍ An application is proposed for the temporal decomposition of the one-machine scheduling problem.

Downloads

Issue

Section

Articles