In this paper, we study a class of simple and easy-to-construct shop schedules, known as dense schedules. We present tight bounds on the maximum deviation in makespan of dense flow-shop and job-shop schedules from the...In this paper, we study a class of simple and easy-to-construct shop schedules, known as dense schedules. We present tight bounds on the maximum deviation in makespan of dense flow-shop and job-shop schedules from their optimal ones. For dense open-shop schedules, we do the same for the special case of four machines and thus add a stronger supporting case for proving a standing conjecture.展开更多
基金Support for the research by the first author is provided by the Management Research Fellowship of the ESRC (Economic & Social R
文摘In this paper, we study a class of simple and easy-to-construct shop schedules, known as dense schedules. We present tight bounds on the maximum deviation in makespan of dense flow-shop and job-shop schedules from their optimal ones. For dense open-shop schedules, we do the same for the special case of four machines and thus add a stronger supporting case for proving a standing conjecture.
