Lower Bounds for the Head-Body-Tail Problem on Parallel Machines: A Computational Study of the Multiprocessor Flow Shop

References

• Baptiste P., Le Pape C., Nuijten W.Constraint-Based Scheduling: Applying Constraint Programming to Scheduling Problems (2001) (Kluwer, Boston, MA) Crossref, Google Scholar
• Brah S. A., Hunsucker J. L. Branch-and-bound algorithms for the flow shop with multiple processors. Eur. J. Oper. Res. (1991) 51:88–99Crossref, Google Scholar
• Buten R. E., Shen V. Y. A scheduling model for computer systems with two classes of processors. Proc. 1973 Sagamore Computer Conference Parallel Processing (1973) 130–138Google Scholar
• Carlier J. Scheduling jobs with release dates and tails on identical machines to minimize the makespan. Eur. J. Oper. Res. (1987) 29:298–306Crossref, Google Scholar
• Carlier J., Pinson E. Jackson’s pseudo-preemptive schedule for the Pm|ri, qi|Cmax scheduling problem. Ann. Oper. Res. (1998) 83:41–58Crossref, Google Scholar
• Chen B., Du D. Z., Sun J. Scheduling multiprocessor flow shops. New Advances in Optimization and Approximation (1994) (Kluwer, Boston, MA) 1–8Crossref, Google Scholar
• Chen B. Analysis of classes of heuristics for scheduling two-stage flow shops with parallel machines at one stage. J. Oper. Res. Soc. (1995) 46:234–244Crossref, Google Scholar
• Gharbi A., Haouari M. Minimizing makespan on parallel machines subject to release dates and delivery times. J. Scheduling (2002) 5:329–355Crossref, Google Scholar
• Graham R. L., Lawler E. L., Lenstra J. K., Rinnooy Kan A. H. G. Optimization and approximation in deterministic sequencing and scheduling: A survey. Ann. Discrete Math. (1979) 5:287–326Crossref, Google Scholar
• Gupta J. N. D., Hariri A. M. A., Potts C. N. Scheduling a two-stage hybrid flow shop with parallel machines at the first stage. Ann. Oper. Res. (1997) 69:171–191Crossref, Google Scholar
• Haouari M., Gharbi A. An improved max-flow-based lower bound for minimizing maximum lateness on identical parallel machines. Oper. Res. Lett. (2003) 31:49–52Crossref, Google Scholar
• Hoogeveen J. A., Lenstra J. K., Veltman B. Minimizing the makespan in a multiprocessor flow shop is strongly NP-hard. Eur. J. Oper. Res. (1996) 89:172–175Crossref, Google Scholar
• Horn W. A. Some simple scheduling algorithms. Naval Res. Logistics Quart. (1974) 21:177–185Crossref, Google Scholar
• Johnson S. M. Optimal two- and three-stage production schedules with set-up times included. Naval Res. Logistics Quart. (1954) 1:61–68Crossref, Google Scholar
• Jurisch B. Lower bounds for the job-shop scheduling problem on multi-purpose machines. Discrete Appl. Math. (1995) 58:145–156Crossref, Google Scholar
• Labetoulle J., Lawler E. L., Lenstra J. K., Rinnooy Kan A. H. G., Pulleyblank W. R. Preemptive scheduling of uniform machines subject to release dates. Progress in Combinatorial Optimization (1984) (Academic Press, Toronto, Canada) 245–261Crossref, Google Scholar
• Langston M. A. Interstage transportation planning in the deterministic flow-shop environment. Oper. Res. (1987) 35:556–564Link, Google Scholar
• Lee C. Y., Vairaktarakis G. L. Minimizing makespan in hybrid flowshops. Oper. Res. Lett. (1994) 16:149–158Crossref, Google Scholar
• Mastrolilli M., Gambardella L. M. Effective neighborhood functions for the flexible job shop problem. J. Scheduling (2000) 3:3–20Crossref, Google Scholar
• McNaughton R. Scheduling with deadlines and loss functions. Management Sci. (1959) 6:1–12Link, Google Scholar
• Perregaard M. Branch-and-bound methods for the multi-processor job shop and flow shop scheduling problems. (1995) . Master’s thesis, Department of Computer Science, University of Copenhagen, Copenhagen, DenmarkGoogle Scholar
• Portmann M.-C., Vignier A., Dardilhac D., Dezalay D. Branch and bound crossed with GA to solve hybrid flowshops. Eur. J. Oper. Res. (1998) 107:389–400Crossref, Google Scholar
• Sanlaville E. Nearly on line scheduling of preemptive independent tasks. Discrete Appl. Math. (1995) 57:229–241Crossref, Google Scholar
• Santos D. L., Hunsucker J. L., Deal D. E. Global lower bounds for flow shops with multiple processors. Eur. J. Oper. Res. (1995) 80:112–120Crossref, Google Scholar
• Sriskandarajah C., Sethi S. P. Scheduling algorithms for flexible flowshops: Worst and average performance. Eur. J. Oper. Res. (1989) 43:143–160Crossref, Google Scholar
• Vandevelde A. Minimizing the makespan in a multiprocessor flow shop. (1994) . Master’s thesis, Department of Mathematics and Computer Science, Technische Universiteit Eindhoven, Eindhoven, The NetherlandsGoogle Scholar
• Webster S. T. A general lower bound for the makespan problem. Eur. J. Oper. Res. (1996) 89:516–524Crossref, Google Scholar