CONFLICT RESOLUTION IN A SUPPLY LINE : COMPLEXITY ANALYSIS
Conference Paper
Overview
Identity
Additional Document Info
Other
View All
Overview
abstract
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. The second stage's objective is to minimize the number of tardy jobs; 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 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 prove that the coordination problem is NP-hard in the strong sense. 2009 IFAC.