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. (C) 2011 Elsevier Ltd. All rights reserved.