Minimizing the makespan with late start penalties added to processing times in a single facility scheduling problem (Q2638921)

The authors consider single machine sequencing problems in which processing time of a job is assumed to be split in a fixed and a variable part. For each job j, the variable part is sequence dependent in the sense that it is given by \(\max \{0,v_ j(S_ j-d_ j)\}\) where \(v_ j\) and \(d_ j\) are given and \(S_ j\) is the starting time of job j in the sequence under consideration. The objective is to minimize makespan. A dynamic programming, a branch-and-bound and five heuristic algorithms are proposed. Computational experience with solving randomly generated problems with up to 15 jobs is reported. The paper suffers from such annoying phenomena as unstated assumptions and ambiguous formulations.