Heuristic scheduling of parallel machines with sequence-dependent set-up times

References

• BABEL , L. , KELLERER , H. and KOTOV , V. 1998 . The k-partitioning problem . Mathematical Methods of Operations Research , 47 : 59 – 82 .
   Web of Science ®Google Scholar
• BAKER , K. 1974 . Introduction to Sequencing and Scheduling , New York : Wiley .
   Google Scholar
• BARTAL , Y. , FIAT , A. , KARLOFF , H. and VOHRA , R. 1995 . New algorithms for an ancient scheduling problem . Journal of Computer and System Sciences , 51 : 359 – 366 .
   Web of Science ®Google Scholar
• BEAN , J. C. 1994 . Genetic algorithms and random keys for sequencing and optimization . ORSA Journal on Computing , 6 : 154 – 160 .
   Google Scholar
• BITRAN , G. R. and GILBERT , S. M. 1990 . Sequencing production on parallel machines with two magnitudes of sequence dependent set-up cost . Journal of Manufacturing and Operations Management , 3 : 24 – 52 .
   Google Scholar
• BLOCHER , J. D. and CHAND , S. 1991 . Scheduling of parallel processors: a posterior bound on LPT sequencing and a two-step algorithm . Naval Research Logistics , 38 : 273 – 287 .
   Web of Science ®Google Scholar
• COFFMAN , E. G. JR. and SETHI , R. 1976 . A generalized bound on LPT sequencing . RAIROInformatique , 10 : 17 – 25 .
   Google Scholar
• COFFMAN , E. G. JR. , GAREY , M. R. and JOHNSON , D. S. 1978 . An application of bin-packing to multiprocessor scheduling . SIAM Journal on Computing , 7 : 1 – 17 .
   Web of Science ®Google Scholar
• CORREA , R. C. , FERREIRA , A. and REBREYEND , P. 1999 . Scheduling multiprocessor tasks with genetic algorithms . IEEE Transactions on Parallel and Distributed Systems , 10 : 825 – 837 .
   Web of Science ®Google Scholar
• DAVIS , L. and STREENSTRUP , M. 1987 . “ Genetic algorithms and simulated annealing: an over-view ” . In Genetic Algorithms and Simulated Annealing , Edited by: Davis , L. 1 – 11 . London : Pitman .
   Google Scholar
• FRIESEN , D. K. 1984 . Tighter bounds for the MULTIFIT processor scheduling algorithm . SIAM Journal on Computing , 13 : 170 – 181 .
   Web of Science ®Google Scholar
• GRAHAM , R. L. 1969 . Bounds on multiprocessing timing anomalies . SIAM Journal on Applied Mathematics , 17 : 416 – 429 .
   Web of Science ®Google Scholar
• GU , Y. and CHUNG , C. A. 1999 . Genetic algorithm approach to aircraft gate reassignment problem . Journal of Transportation Engineering , 125 : 384 – 389 .
   Web of Science ®Google Scholar
• GUIGNARD , M. 1993 . Solving makespan minimization problems with Lagrangean decompo-sition . Discrete Applied Mathematics , 42 : 17 – 29 .
   Web of Science ®Google Scholar
• HOLLAND , J. H. 1975 . Adaptation in Natural and Artificial Systems , Ann Arbor , MI : The University of Michigan Press .
   Google Scholar
• HOU , E. , ANSARI , N. and REN , H. 1994 . A genetic algorithm for multiprocessor scheduling . IEEE Transactions on Parallel and Distributed Systems , 5 : 113 – 120 .
   Web of Science ®Google Scholar
• HU , T. C. 1961 . Parallel sequencing and assembly line problems . Operations Research , 9 : 841 – 848 .
   Web of Science ®Google Scholar
• JOHNSON , D. S. and PAPADIMITRIOU , C. H. 1985 . “ Computational complexity ” . In The Traveling Salesman Problem , Edited by: Lawler , E. L. , Lenstra , J. K. , Rinnooy , A. H. G. and Shmoys , D. B. 37 – 85 . Chichester , , UK : Wiley .
   Google Scholar
• LEE , C.-Y. and MASSEY , J. D. 1988 . Multiprocessor scheduling: combining LPT and MULTIFIT . Discrete Applied Mathematics , 20 : 233 – 242 .
   Web of Science ®Google Scholar
• MCNAUGHTON , R. 1959 . Scheduling with deadlines and loss functions . Management Science , 6 : 1 – 12 .
   Web of Science ®Google Scholar
• MIN , L. and CHENG , W. 1998 . Identical parallel machine scheduling problem for minimizing the makespan using genetic algorithm combined by simulated annealing . Chinese Journal of Electronics , 7 : 317 – 321 .
   Google Scholar
• MONMA , C. L. and POTTS , C. N. 1989 . On the complexity of scheduling with batch setup times . Operations Research , 37 : 798 – 814 .
   Web of Science ®Google Scholar
• MONMA , C. L. and POTTS , C. N. 1993 . Analysis of heuristics for preemptive parallel machine scheduling with batch setup times . Operations Research , 41 : 981 – 993 .
   Web of Science ®Google Scholar
• MORRIS , J. S. and TERSINE , R. J. 1990 . A simulation analysis of factors influencing the attractiveness of group technology cellular layouts . Management Science , 36 : 1567 – 1578 .
   Web of Science ®Google Scholar
• MUNTZ , R. R. and COFFMAN , E. G. 1969 . Optimal preemptive scheduling on two-processor systems . IEEE Transactions on Computers , 18 : 1014 – 1020 .
   Web of Science ®Google Scholar
• MUNTZ , R. R. and COFFMAN , E. G. 1970 . Preemptive scheduling of real-time tasks on multi-processor systems . Journal of the ACM , 17 : 324 – 338 .
   Web of Science ®Google Scholar
• OVACIK , I. M. and UZSOY , R. 1993 . Worst-case error bounds for parallel machine scheduling problems with bounded sequence-dependent setup times . Operations Research Letters , 14 : 251 – 256 .
   Web of Science ®Google Scholar
• PAPADIMITRIOU , C. H. and STEIGLITZ , K. 1998 . Combinatorial Optimization: Algorithms and Complexity , Mineola, New York : Dover .
   Google Scholar
• PARKER , R. G. , DEANE , R. H. and HOLMES , R. A. 1976 . On the use of a vehicle routing algorithm for the parallel processor problem with sequence dependent changeover costs . AIIE Transactions , 9 : 155 – 160 .
   Google Scholar
• PUNNEN , A. P. and ANEJA , Y. P. 1995 . Minmax combinatorial optimization . European Journal of Operational Research , 81 : 634 – 643 .
   Web of Science ®Google Scholar
• RAJGOPAL , J. and BIDANDA , B. 1991 . On scheduling parallel machines with two setup classes . International Journal of Production Research , 29 : 2443 – 2458 .
   Web of Science ®Google Scholar
• REINELT , G. 1994 . The Traveling Salesman: Combinatorial Solutions for TSP Applications. , Berlin : Springer-Verlag .
   Google Scholar
• SAHNI , S. K. 1976 . Algorithms for scheduling independent tasks . Journal of the ACM , 23 : 116 – 127 .
   Web of Science ®Google Scholar
• SIVRIKAYA-SERIFOGLU , F. and ULUSOY , G. 1999 . Parallel machine scheduling with earliness and tardiness penalties . Computers and Operations Research , 26 : 773 – 787 .
   Web of Science ®Google Scholar
• TANG , C. S. 1990 . Scheduling batches on parallel machines with major and minor set-ups . European Journal of Operational Research , 46 : 28 – 37 .
   Web of Science ®Google Scholar
• ZHANG , G. 1997 . A simple semi on-line algorithm for P2\\Cmax with a buffer . Information Processing Letters , 61 : 145 – 148 .
   Web of Science ®Google Scholar