《1986 A block approach for single-machine scheduling with release dates and due dates》.pdf

278 European Journal of Operational Research 26 (1986) 278-285 North-Holland A block approach for single-machine scheduling with release dates and due dates J. GRABOWSKI, E. NOWICKI and S. ZDRZALKA Institute of Engineering Cybernetics, Technical University of Wroclaw, ul. Janiszewskiego 11/ 17, 50-370 Wroclaw, Poland Abstract: The problem of scheduling jobs on a single machine subject to given release dates and due dates is considered. A new algorithm of the branch-and-bound type for solving this problem is proposed. The approach used in the paper is fully based on the eliminative properties of a block of jobs and in contradiction to the existing algorithms, it does not require any heuristic method to generate a current solution in a search tree. However, a heuristic may be used in order to obtain a good initial solution. Extensive computational experiments show a high efficiency of the algorithm. Keywords: Scheduling, optimization, integer programming, computational analysis 1. Introduction di, K= max ISicndi. The objective is to find a processing order on bottleneck machine M, that A single machine is available to process a set minimizes the time of the last job comple