Scheduling jobshops with some identical or similar jobs

Scheduling jobshops with some identical or similar jobs

0.00 Avg rating0 Votes
Article ID: iaor2003958
Country: United Kingdom
Volume: 4
Issue: 4
Start Page Number: 177
End Page Number: 199
Publication Date: Jul 2001
Journal: Journal of Scheduling
Authors: , ,
Abstract:

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 schedule 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 distinguish two cases: If jobs on the same route are identical we provide an approximation algorithm which is within constant of the optimum, no matter how many jobs there are. If jobs on the same route have different processing times, the job-shop scheduling problem can be crudely approximated by a continuous deterministic fluid scheduling problem, with buffers of fluid representing the jobs waiting for each operation. The fluid makespan problem is easily solved using constant flow rates out of each buffer for the entire schedule, and the optimal fluid makespan is a lower bound on the discrete optimal makespan. We describe two heuristics which imitate the fluid solution. We present some preliminary numerical results.

Reviews

Required fields are marked *. Your email address will not be published.