A problem-independent search heuristic for single machine scheduling with release dates and deadlines

This paper presents a new search heuristic F that determines the feasibility of scheduling a set of jobs on a single machine where each job is characterized by its release date, processing time, and deadline. F alternates between (i) a construction phase that builds a partial feasible solution by assigning positions to on-time jobs and (ii) a backtracking phase that removes on-time jobs that are causing the tardiness of the current job. F chooses jobs according to a new dynamic priority rule. It stops when it successfully schedules all jobs or when it reaches a threshold runtime. F is unique in two ways. It does not guide its search via a problem-dependent heuristic. In addition, its parameters are problem-independent; thus, require no tuning. Experimental results provide computational evidence that F is superior to existing heuristics such as NEH and Profile Fitting.