Groupe d’études et de recherche en analyse des décisions

# Coordination in a Two-Stage Production System: Complexity, Conflict and Cooperation

## Manoj Vanajakumari, Chelliah Sriskandarajah et Edouard Wagneur

We study conflict and cooperation issues in a two-stage production system. The objective of the first stage is to minimize the sum of the completion times of all n jobs, denoted by $\sum_{j=1}^n{C_j(\sigma_1)}$. The second stage's objective is to minimize the number of tardy jobs, denoted by $N(\sigma_2)$; $\sigma_1$ and $\sigma_2$ are, respectively, the preferred schedules - that minimize the corresponding objective functions - for the first and the second stage. There is an intermediate buffer connecting the first and the second stage. If required, jobs are re-sequenced at this buffer to enhance the performance of the system. There is a cost, $F(\sigma_1,\sigma_2)$ associated with the re-sequencing of jobs at this buffer. The performance of the system is measured by a convex combination of the costs at each stage, and the cost of re-sequencing of the jobs at the intermediate buffer. Each production stage has an ideal schedule determined by its cost considerations. We show that when a stage solves its scheduling problem under the constraints imposed on it by the other stage, the resulting system will be suboptimal. We also develop mechanisms that coordinate the scheduling problems of the two stages and enhance the overall system performance. We also show that the coordination problem is NP-hard in the strong sense (reduction from 3-PARTITION).

, 27 pages