An improved precedence rule for single machine sequencing problems with quadratic penalty

This article introduces a new heuristic for the single machine job sequencing problem where the objective is to minimize the weighted sum of quadratic completion times of jobs. An improved precedence constraint among non-adjacent jobs has been conjectured. The conjecture appears to be difficult to prove though extensive empirical runs failed to generate even a single counter example. This leads to an interesting observation: if the conjecture is used to develop a heuristic, it will yield optimal solutions in all instances of the extensive empirical runs performed by us. We expect that the heuristic would produce optimal solutions for other instances too. The conjecture, therefore, raises an open problem for further research in this domain.