A single-machine distributed scheduling methodology using cooperative interaction via coupling agents

Abstract

This paper considers a single-machine scheduling problem where the decision authorities and information are distributed in multiple subproduction systems. Subproduction systems share the single machine and must cooperate with one another to achieve a global goal of minimizing a linear function of the completion times of the jobs; e.g., total weighted completion times. It is assumed that neither the subproduction systems nor the shared machine have complete information about the entire system. The associated scheduling problems are formulated as zero-one integer programs. The solution approach is based on Lagrangian relaxation techniques modified to require less global information. Specifically, there is no need for a global upper bound, or a single master problem that has a complete view of all the coupling constraints. The proposed methodology exhibits a promising performance when experimentally compared to the Lagrangian relaxation with a subgradient method with the added benefit that can be applied to situations with more restrictive information sharing.

Acknowledgement

The authors will like to thank Mr. Sun Woo Kim, a PhD student in Industrial Engineering at Texas A&M University for his help in re-running the original experiments and additional runs with larger problems performed after the first version of this paper.

Notes

*Due to excessive run times these results are for 12 replicates only: all other cases use 60 replicates.

*Due to excessive run times these results are for 12 replicates only: all other cases use 60 replicates.