Scheduling jobshops with some identical or similar jobs

We consider the following job-shop scheduling problem: N jobs move through I machines, along R routes, with given processing times, and one seeks a sc hedule to minimize the latest job completion time. This problem is NP-hard. We are interested in the case where the number of routes and the number of machines are fixed, while the number of jobs varies and is large. We disti nguish two cases: If jobs on the same route are identical we provide an app roximation algorithm which is within constant of the optimum, no matter how many jobs there are. If jobs on the same route have different processing t imes, the job-shop scheduling problem can be crudely approximated by a cont inuous deterministic fluid scheduling problem, with buffers of fluid repres enting the jobs waiting for each operation. The fluid makespan problem is e asily solved using constant flow rates out of each buffer for the entire sc hedule, and the optimal fluid makespan is a lower bound on the discrete opt imal makespan. We describe two heuristics which imitate the fluid solution. We present some preliminary numerical results. Copyright (C) 2001 John Wil ey & Sons, Ltd.