Heuristic algorithms for preemptive scheduling in a Two-stage flowshop with unrelated parallel machines and 0-1 resource requirements

• Autorzy: Figielska E.
• Języki publikacji: EN

Abstrakty

EN

The paper considers the problem of preemptive scheduling in a two-stage flowshop with parallel unrelated machines at the first stage and a single machine at the second stage. At the first stage, jobs use some additional renewable resources which are available in limited quantities. The resource requirements are of 0-1 type. The objective is minimization of the makespan. The problem is NP-hard. We develop heuristic algorithms which first solve the problem occurring at stage 1, and then find a final schedule in the flowshop. An extensive computational experiment shows that the proposed heuristic algorithms can be an efficient tool capable of finding good quality solutions.

Słowa kluczowe

EN

preemptive scheduling; flowshop; parallel unrelated machines; resource constraints; heuristics

• Wydawca: Systems Research Institute, Polish Academy of Sciences
• Czasopismo: Control and Cybernetics
• Rocznik: 2009
• Tom: Vol. 38, no 3
• Strony: 723--743
• Opis fizyczny: Bibliogr. 31 poz.

Twórcy

autor

Figielska E.

• Warsaw School of Information Technology, ul. Newelska 6, 01-447 Warsaw, Poland,

Bibliografia

• BRAH, S.A. (1988) Scheduling in a flow shop with multiple processors. Unpublished Ph.D. Dissertation, University of Houston, Houston, TX.
• BRAH, S.A. and LOO, L.L. (1999) Heuristics for scheduling in a flow shop with multiple processors. EJOR 113, 113-112.
• CHEN, B. (1995) Analysis of classes of heuristics for scheduling a two-stage flow shop with parallel machines at one stage. Journal of Operational Research Society 46, 234-244.
• DE WERRA, D. (1984) Preemptive scheduling, linear programming and network flows. SI AM Journal on Algebraic and Discrete Methods 5, 11-20.
• FIGIELSKA, E. (1999) Preemptive scheduling with changeovers: using column generation technique and genetic algorithm. Computers and Industrial Engineering 37, 63-66.
• FIGIELSKA, E. (2005) A simulated annealing based approach to the parallel machine scheduling problem with jobs and setups using additional renewable resources. Proc. 11th IEEE Int. Conf. Methods and Models in Automation and Robotics, 1061-1066.
• FIGIELSKA, E. (2006A) A genetic algorithm based heuristic for the parallel machine scheduling problem with setups and additional renewable resources. In: A. Cader et al., eds., Artificial Intelligence and Soft Computing. Academic Publishing House EXIT, Warszawa, 189-195.
• FIGIELSKA, E. (2006B) A heuristic algorithm for scheduling in a two-stage multiprocessor flowshop with 0-1 resource requirements. Proc. of the 12th IEEE International Conference on Methods and Models in Automation and Robotics, Międzyzdroje.
• FIGIELSKA, E. (2006C) Solving a flowshop scheduling problem with additional resource constraints. Prace naukowe PW, Elektronika 156, 139-146.
• GRABOWSKI, J. and JANIAK, A. (1984) Sequencing problem with resource constraints. In: R. Trappl, ed., Cybernetics and System Research 2, Elsevier Science Publishers, Amsterdam, 329-333.
• GUPTA, J.N.D. (1988) Two stage hybrid flowshop scheduling problem. Journal of Operational Research Society 39, 359-364.
• HAOUARI, M. and M’HALLAH, R. (1997) Heuristic algorithms for the two-stage hybrid flowshop problem. Operations Research Letters 21, 43-53.
• HOOGEVEEN, J.A., LENSTRA, J.K. and VELTMAN, B. (1996) Preemptive scheduling in a two-stage multiprocessor flow shop is NP-hard. EJOR 89, 172-175.
• JANIAK, A. (1986) Flow-shop scheduling with controllable operation processing times. In: Large Scale Systems: Theory and Applications. Pergamon Press, Oxford, 602-605.
• JANIAK, A. (1988A) General flow-shop scheduling with resource constraints. International Journal of Production Research 26, 1089-1103.
• JANIAK, A. (1988B) Minimization of the total resource consumption in permutation flow-shop sequencing subject to a given makespan. Modelling, Measurement and Control (AMSE Press) 13, 1-11.
• JANIAK, A. (1989) Minimization of the total resource consumption under a given deadline in two processor flow-shop scheduling problem. Information Processing Letters 32, 101-112.
• JANIAK, A. (1991) Scheduling and resource allocation problems in some flow type manufacturing process. In: G. Fandel and G. Zaepfel, eds., Modern Production Concepts. Springer-Verlag, Berlin, 404-415.
• JANIAK, A. and PORTMANN, M.C. (1998) Genetic algorithm for the permutation flow-shop scheduling problem with linear model of operations. Annals of Operations Research 83, 95-114.
• JANIAK, A. (1998) Minimization of the makespan in a two-machine problem under given resource constraints. EJOR 107, 325-337.
• JOHNSON, S.M. (1954) Optimal two- and three-stage production schedules with setup times included. Naval Research Logistics Quarterly 1, 61-68.
• KELLERER, H. and STRUSEVICH, V.A. (2002) Scheduling parallel dedicated machines under a single non-shared resource. EJOR 147, 345-364.
• LAWLER, E.L. and LABETOULLE, J. (1978) On preemptive scheduling on unrelated parallel processors by linear programming. J. Assoc. Comput. Mach. 25, 612-619.
• LINN, R. and ZHANG, W. (1999) Hybrid flow shop scheduling: a survey. Computers and Industrial Engineering 37, 57-61.
• RUIZ, R. and MAROTO, C. (2006) A genetic algorithm for hybrid flowshops with sequence dependent setup times and machine eligibility. EJOR 169, 781-800.
• SALVADOR, M.S. (1973) A solution of a special class of flowshop scheduling problems. In: S.E. Elmaghraby, ed., Symposium of the Theory of Scheduling and Its Application. Springer-Verlag, New York, 83-91.
• SERAFINI, P. (1996) Scheduling jobs on several machines with the job splitting property. Operations Research 44, 617-628.
• SŁOWIŃSKI, R. (1980) Two approaches to problems of resource allocation among project activities - A comparative study. Journal of Operational Research Society 31, 711-723.
• SŁOWIŃSKI, R. (1981) L’ordonnancement des taches preemptives sur les processeurs independants en presence de ressources supplementaires. RAIRO Inform./Comp. Science, 15, 155-166.
• SŁOWIŃSKI, R. and WĘGLARZ, J. (1977) Time-minimal network model with various activity performing modes (in Polish). Przegląd Statystyczny 24, 409-416.
• SURESH, V. (1997) A note on scheduling of two-stage flow shop with multiple processors. International Journal of Production Economics 49, 77-82.