Single machine scheduling with controllable processing times to minimize total tardiness and earliness

In most deterministic scheduling problems job processing times are considered as invariable and known in advance. Single machine scheduling problem with controllable processing times with no inserted idle time is presented in this study. Job processing times are controllable to some extent that they can be reduced or increased, up to a certain limit, at a cost proportional to the reduction or increase. In this study, our objective is determining a set of compression/expansion of processing times in addition to a sequence of jobs simultaneously, so that total tardiness and earliness are minimized. A mathematical model is proposed firstly and afterward a net benefit compression–net benefit expansion (NBC–NBE) heuristic is presented so as to acquire a set of amounts of compression and expansion of jobs processing times in a given sequence. Three heuristic techniques in small problems and in medium-to-large instances two meta-heuristic approaches, as effective local search methods, as well as these heuristics are employed to solve test examples. The single machine total tardiness problem (SMTTP) is already NP-hard, so the considered problem is NP-hard obviously. The computational experiments demonstrate that our proposed heuristic is efficient approach for such just-in-time (JIT) problem, especially equipped with competent heuristics.

► Minimizing total tardiness and earliness simultaneously on a single machine. ► Determining sequence of jobs plus a set of processing times compression/expansion. ► Apply three heuristics for obtaining initial sequence based on dispatching rules. ► Derive a mathematical model and solve small size instances optimally. ► Employ two meta-heuristics besides three heuristics in large cases.