Minimizing total tardiness and earliness problem with controllable processing times using an effective heuristic

This research addresses the single machine scheduling problems with controllable processing times. In this area, it is often assumed that the possible processing time of a job can be continuously controlled, i.e. it can be any number in a given interval. When the processing times of jobs are controllable, selected processing times affect both the manufacturing cost and the scheduling performance. In this study, our objective is determining a set of compression/expansion of processing times as well as a sequence of jobs simultaneously, so that total tardiness and earliness on a single machine are minimized. In this way, we first propose a mathematical model for the considered problem and then a net benefit compression-net benefit expansion (NBC-NBE) heuristic is presented for obtaining a set of amounts of compression and expansion of jobs processing times in a given sequence. Also, a simulated annealing approach is used to solve medium to large size problems as an effective local search method. The addressed problem is NP-hard since the single machine total tardiness problem (SMTTP) is already NP-hard. The computational results show that our proposed heuristic is an efficient solution method for such Just-In-Time (JIT) problem.