Local search algorithms for a single-machine scheduling problem with positive and negative time-lags (Q5946822)

The authors consider the following scheduling problem. Let \(J=\{1,2,...,n\}\) be a set of \(n\) jobs with processing times \(p_1, p_2, ..., p_n\) to be scheduled without preemption on a single machine. There is a set of relations called time-laggs of the form \(S_i+d_{ij}\leq S_j\) for all \((i,j)\in R\), where \(R\subseteq J\times J\) and \(S_i\) denotes the starting time of job \(i\), \(i=1,2,...,n\). If \(d_{ij}\geq 0\), then job \(j\) cannot be started earlier than \(d_{ij}\) time units after the starting time of job \(i\) (minimal time-lag). If \(d_{ij}<0\), then job \(j\) cannot be started earlier than \(|d_{ij}|\) time units before the starting time of job \(i\) (maximal time-lag). A vector \(S=(S_1, S_2,...,S_n)\) of starting times of jobs determines a schedule. Such a schedule \(S\) is feasible if the intervals of processing of different jobs don't overlap and the time-lags are satisfied. The goal is to find a feasible schedule which minimizes the makespan \(C_{\max}=\max_{1\leq i\leq n}\{S_i+p_i\}\) if such a schedule exists. It should be mentioned that for this problem the question of whether or not a feasible solution exists, is already NP-complete [\textit{M. Bartusch, H. Möhring} and \textit{F. J. Rademacher}, Ann. Oper. Res. 16, 201-240 (1988; Zbl 0693.90047), \textit{P. Bruckner, Th. Hilbig} and \textit{J. Hurink}, Discrete Appl. Math. 94, 77-99 (1999; Zbl 0932.68006)]. In this paper a local search approach for the problem under consideration is presented. A main obstacle for developing local search heuristics for this problem is the fact that the determination of an initial feasible solution is already a hard problem. In the paper this obstacle has been overcome by incorporating infeasible solutions in the search process. At first the authors give a network representation for the instances, formulate the problem of finding the best schedule for a given sequence of jobs (if such a schedule exists) as a longest path problem and develop an efficient method to determine such a schedule. Then local search methods are described. A basic method is a tabu search approach which starts with an ''infeasible'' sequence of jobs and which tries to guide the search to a feasible sequence. This basic routine is packed in an outer method where some diversification of the search is realized. Computational results based on instances resulting from shop problems are reported.