A short note on A note on single-machine scheduling with job-dependent learning effects

Mosheiov & Sidney [5] showed that the single-machine makespan minimization problem with job-dependent learning effects can be formulated as an assignment problem and solved in O(n3) time. Later on, Koulamas [4] showed that the scheduling problem can be solved in O(nlogn) time by sequencing the jobs according to the shortest processing time (SPT) rule if the job-dependent learning rate are correlated with the level of sophistication of the jobs and bounded from below. The optimality of the SPT job sequence still holds when job-dependent learning rate are inversely correlated with the level of sophistication of the jobs and bounded from above. The main results in the paper are correct, however, there is an error in Corollary 1 and the proofs of Proposition 1 and Corollary 1 are not complete. In this note, a counter example for the latter case is given first and then a modified corollary is provided. Next, a lemma is provided to complete the proofs of Proposition 1 and Corollary 1. Finally, a simple algorithm is developed to solve the latter case in O(n2) time.& COPY; 2023 Published by Elsevier B.V.

Automated summary

The research states that the single-machine makespan minimization problem can be solved as an assignment problem in O(n3) time. Subsequent research shows that if the job-dependent learning effects are correlated with the level of sophistication of the jobs and have a lower bound, the scheduling problem can be solved in O(nlogn) time by sequencing the jobs according to the shortest processing time rule. The SPT job sequence remains optimal when the job-dependent learning effects are inversely correlated with the level of sophistication and have an upper bound. The main results of the paper are correct, but there are errors in Corollary 1 and incomplete proofs for Proposition 1 and Corollary 1. This note provides a counter example for the latter case and a modified corollary. A lemma is presented to complete the proofs for Proposition 1 and Corollary 1. Finally, a simple algorithm is developed to solve the latter case in O(n2) time.