An Algebraic Approach to the Solutions of the Open Shop Scheduling Problem

Abstract

The open shop scheduling problem (OSSP) is one of the standard scheduling problems. It consists of scheduling jobs associated with a finite set of tasks developed by different machines. In this case, each machine processes at most one operation at a time, and the job processing order on the machines does not matter. The goal is to determine the completion times of the operations processed on the machines to minimize the largest job completion time, called Cmax. This paper proves that each OSSP has associated a path algebra called Brauer configuration algebra whose representation theory (particularly its dimension and the dimension of its center) can be given using the corresponding Cmax value. It has also been proved that the dimension of the centers of Brauer configuration algebras associated with OSSPs with minimal Cmax are congruent modulo the number of machines.

Keywords

• Brauer configuration algebra
• open shop scheduling problem
• NP-completeness
• quiver representation