A bi-objective branch-and-bound algorithm for the unit-time job shop scheduling : A mixed graph coloring approach. (August 2021)

• Record Type: Journal Article
• Authors: KOUIDER, Ahmed; AIT HADDADÈNE, Hacène
• Is Part Of: Computers & operations research. Volume 132(2021)
• Publication Date: 2021-08
• Subjects: Bi-objective branch-and-bound -- ∊-constraint -- Scheduling -- Mixed graph coloring -- Multiobjective optimization; Operations research -- Periodicals; Electronic digital computers -- Periodicals; 004.05
• DOI: 10.1016/j.cor.2021.105319
• Languages: English
• ISSNs: 0305-0548

Abstract

Highlights: A bi-objective unit-time job shop scheduling is modeled as a mixed graph coloring. A new branch-and-bound and an epsilon-constraint algorithms address bi-objective mixed graph coloring. A new lower bound is proposed for the sum of path-endpoints coloring. The lower bound improves considerably upon the known lower bound from the literature. The branch-and-bound method is faster and more efficient than the epsilon-constraint method. Abstract: A bi-objective branch-and-bound and an ∊ -constraint algorithms are proposed for the unit-time job shop scheduling problem. These two objectives are the minimization of the makespan and the total completion time. We model this problem as a bi-objective mixed graph coloring using both the chromatic number and the sum of path-endpoints coloring (i.e. sum of the colors assigned to the endpoints of maximal paths) to determine the optimal set of the non-dominated solutions. A new lower bound is also constructed for the sum of path-endpoints coloring which is used alongside an existing lower bound from the literature on two bounding procedures. Computational experiments on benchmark data sets show that the proposed lower bound improves considerably upon the known lower bound from the literature. Besides, our algorithms are found to find an optimal set of non-dominated solutions for most of the tested benchmarks within a reasonable amount of CPU time. In addition, two interesting performance metrics are introduced to compare and assess the effectiveness and the efficiency of our algorithms.