In a single-machine problem with time-lags a set of jobs hasto be processed on a single machine in such a way that certain timing restrictions between the finishing and starting times of the jobsare satisfied and a given objective function is minimized. We consider the case of positive finish-start time-lags lij which mean that between the finishing time of job i and the starting time of job jthe minimal distance lij has to be respected. New complexity resuits are derived for single-machine problems with constant positive time-lags lij=l which also leadtonew resuits for flow-shop problems with unit processing times and job precedences.
展开▼
