An exact block algorithm for no-idle RPQ problem

• Autorzy: Pempera J.

Identyfikatory

DOI

10.1515/acsc-2017-0021

• Języki publikacji: EN

Abstrakty

EN

In the work a single-machine scheduling problem is being considered, in which all tasks have a fixed availability (release) and delivery time. In the analyzed variant no-idle time is allowed on a machine. The purpose of optimization is to determine such order of tasks that minimizes the makespan, i.e. the time of execution of all the tasks. There is also a number of properties of the problem presented, in particular there are formulated block eliminating properties for no-idle constraint. There was an exact B&B algorithm based on the block properties proposed.

Słowa kluczowe

EN

scheduling; single machine; no-idle; B&B algorithm

• Wydawca: Polish Academy of Sciences, Committee of Automatic Control and Robotics
• Czasopismo: Archives of Control Sciences
• Rocznik: 2017
• Tom: Vol. 27, no. 2
• Strony: 323--330
• Opis fizyczny: Bibliogr. 13, rys., schem., tab., wzory

Twórcy

autor

Pempera J.

• Department of Automatics, Mechatronics and Control Systems, Faculty of Electronics, Wrocław, University of Technology, Janiszewskiego str. 11-17, 50-372 Wrocław, Poland

Bibliografia

• [1] J. Carlier: The one-machine sequencing problem. European J. of Operational Research, 11(1), (1982), 42-47.
• [2] O. Cepek, M. Okada and M. Vlach: Note: On the two-machine no-idle flowshop problem. Naval Research Logistics, 47(4), (2000), 353-358.
• [3] J. Grabowski and J. Pempera: New block properties for the permutation flow shop problem with application in tabu search. The Journal of the Operational Research Society, 52(2), (2001), 210-220.
• [4] J. Grabowski, E. Nowicki and S. Zdrzaşka: A block approach for single-machine scheduling with release dates and due dates. European J. of Operational Research, 26 (1986), 278-285.
• [5] P. J. Kalczynski and J. Kamburowski: A heuristic for minimizing the makespan in no-idle permutation flow shops. Computers & Industrial Engineering, 45 (2005), 146-154.
• [6] B. Liu, L. Wang and Y. Jin: An effective hybrid PSO-based algorithm for flow shop scheduling with limited buffers. e, Computers & Operations Research, 35(9), (2008), 2791-2806.
• [7] E. Nowicki and C. Smutnicki: A fast taboo search algorithm for the job shop problem. Management Science, 24(5), (1996), 530-534.
• [8] E. Nowicki and C. Smutnicki: A fast tabu search algorithm for the permutation flow-shop problem. European J. of Operational Research, 91(1), (1996), 160-175.
• [9] Q.-K. Pan and L. Wang: No-idle permutation flow shop scheduling based on a hybrid discrete particle swarm optimization algorithm. In press at Int. J. of Advanced Manufacturing Technology.
• [10] L. Schrage: Obtaining optimal solution to resource constrained network scheduling problem. Unpublished manuscript, 1971.
• [11] P. Vachajitpan: Job sequencing with continuous machine operation. Computers & Industrial Engineering, 6(3), (1982), 255-259.
• [12] R. E. Kalman: Mathematical description of linear dynamical system. SIAM J. Control, 1(2), (1963), 152-192.
• [13] F. C. Shweppe: Uncertain Dynamic Systems. Prentice-Hall, Englewood Cliffs, N. J., 1970.

Uwagi

PL

Opracowanie ze środków MNiSW w ramach umowy 812/P-DUN/2016 na działalność upowszechniającą naukę (zadania 2017).