Improving local search heuristics for some scheduling problems. Part II