TABLE OF CONTENTS The scheduling problem to be solved in this paper is considered as a combination of two classical scheduling problems with complex assembly sequence: two-machine flow shop scheduling problem and parallel machine scheduling problem. The two-machine flow shop scheduling problem can be solved by Johnson's algorithm [JOH 54]. Parallel machine scheduling problem ( P C max) has been proved by [GAR 78] as NP hard in the strong sense when the number of machines is unlimited. However, the problem is solvable in pseudo-polynomial time when the number of machines is fixed and thus NP hard only in the ordinary sense. Most of the algorithms developed for solving P C max are heuristics (e.g., [GRA 69], [COF 78], [FRI 86]). There are some problem characteristics that complicate solving scheduling problem: ( i) precedence constraints between operations (machining/assembly); ( ii) assignment of operations to machines; and ( iii) sequence of unrelated (independent) operations (machining/assembly).
Scheduling problems have attracted various efforts in multi agent approaches (see for example [SOU 97], [RAB 94], etc.). The notion of agent was found in the wide range of research in computer science (CS), distributed artificial intelligence (DAI), etc. The multi agent systems paradigm represents one of the most promising approaches to the development of agile scheduling systems in manufacturing [RAB 99]. In fact, distributed systems have the following advantages [DEC 87]: ( i) can simplify problem solving by splitting the problem into simple tasks; (
