We consider a job shop with m machines. There are n jobs and each job has a specified sequence to be processed by the machines. Job j has release date rj, due date dj, weight wj and processing time pij on machine i (1, …, m). The objective is to minimize the total weighted tardiness of the n jobs. We describe and analyse a large step random walk which uses different neighbourhood sizes depending on whether the algorithm performs a small step or a large step. The small step consists of iterative improvement while the large step consists of a metropolis algorithm. Computational testing of the large step random walk on 66 instances with 10 jobs and 10 machines shows that the large step random walk achieves better results for the given problem structure compared to an existing shifting bottleneck algorithm. We further show results for large instances with up to 50 jobs and 15 machines.
