《2016 A fluid approach to large volume job shop scheduling》.pdf

J Sched (2010) 13: 509–529 DOI 10.1007/s10951-010-0174-0 A fluid approach to large volume job shop scheduling Yoni Nazarathy · Gideon Weiss Published online: 15 April 2010 © Springer Science+Business Media, LLC 2010 Abstract We consider large volume job shop scheduling 1 Introduction problems, in which there is a fixed number of machines, a bounded number of activities per job, and a large num- Job shop scheduling has always been one of the most im- ber of jobs. In large volume job shops it makes sense to portant and most difficult problems in scheduling theory. solve a fluid problem and to schedule the jobs in such a way The formulation, which is well known (Lawler et al. 1993), as to track the fluid solution. There have been several pa- is: jobs n = 1, . . . , N have to be scheduled on machines pers which used this idea to propose approximate solutions i = 1, . . . , I . Job n requires rn processing activities, moving which are asymptotically optimal as the volume increases. through machines σ (n, 1), . . . , σ (n, rn ) in that order, with We survey some of these results here. In most of these pa- processing times x(n, 1), . . . , x(n, rn ). A schedule for such pers it is assumed that the problem consists of many iden- a problem is best described by a Gantt chart (Gantt 1910), as tical copies of a fixed set of jobs. Our contribution in this in Fig. 1. This includes in particular the completion times of paper is to extend the results to the far more general situ- the jobs, Cn , n = 1, . . . , N . The utility of a schedule may be ation in which the many jobs are all different. We propose measured in many ways. The simplest and most common are the makespan, ma