G-2007-91
Coordination in a Two-Stage Production System: Complexity, Conflict and Cooperation
, et référence BibTeX
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 . The second stage's
objective is to minimize the number of tardy jobs, denoted by
;
and
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,
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).
Paru en novembre 2007 , 27 pages