Fast algorithms for scheduling with learning effects and time‐dependent processing times on a single machine

We consider scheduling problems with learning/deterioration effects and time‐dependent processing times on a single machine, with or without due date assignment considerations. By reducing them to a special assignment problem on product matrices, we solve all these problems in near‐linear time. This improves the time complexity of previous algorithms for some scheduling problems and establishes the fast polynomial solvability for several other problems.