Single machine scheduling problems have received significant attention in the relevant literature. For most practical industrial situations, explicit “consideration of sequence-dependent setup times” is extremely important. Another interesting variation in this setting is the quadratic penalty problem. It is believed that the “quadratic penalty problem becomes extremely difficult to solve” when sequence-dependent setup times are considered. In this paper, the authors have made an attempt to solve the single machine scheduling problem in this difficult setting. In particular, they study “the single machine scheduling problem with quadratic penalties and sequence-dependent (QPSD) setup times.”

The authors first argue that because of sequence-dependent setup times, the dynamic programming techniques and conventional graph search algorithms are unable to solve QPSD. Then, they describe a QPSD_MDFBB algorithm that uses the memory-based depth-first branch-and-bound (MDFBB) approach suggested by Mondal and Sen [1], which “optimally solves QPSD instances up to 30 jobs.”

The authors also explore the avenue of heuristic and metaheuristic techniques to solve QPSD. In particular, they first present QPSD_GSA, a greedy stochastic algorithm. The authors show QPSD_GSA to be able to “generate moderately good solutions rapidly even for large instances.” But the more interesting and useful contribution of QPSD_GSA lies in seeding the initial population of a genetic algorithm presented by the authors named QPSD_GEN. It is reported by the authors “that QPSD_GEN can be used to generate solutions within 2.2 percent of the optimal solutions for 100-job problem instances.” However, this claim is based on a regression analysis rather than actual experiments because the actual optimal solution for 100-job problem instances is not available. The authors do run QPSD_GEN on instances having up to 100 jobs to show the effectiveness of the seeding of the population using QPSD_GSA (reported in Table 6 of the paper). However, one missing element in Table 6 is the timing information. It would clearly be very interesting to know the timing information of QPSD_GEN on these and even larger instances.