Lower bounds and an enhanced greedy heuristic for the single processor scheduling with release dates

International audienceIn this study, we consider the single machine scheduling problem with release dates to minimize total weighted completion time. This problem is known to be strongly NP-hard. First, we present five different formulations based on mixed integer linear programming different definitions of decision variables. Second, new recursive weights decomposition-based lower bounds are proposed, then we generalize an improved split-based lower bound from literature. A constructive greedy heuristic is proposed based on evaluation function with partially lower bound assessment. A first improvement procedure using Hill Climbing search is presented. Experimental study shows promising results