Due window assignment and scheduling on parallel machines: a FPTAS for a bottleneck criterion

• Autorzy: Janiak A. , Janiak W. , Kovalyov M. Y.

Identyfikatory

DOI

10.2478/bpasts-2014-0088

• Języki publikacji: EN

Abstrakty

EN

A fully polynomial time approximation scheme (FPTAS) with run time 0(n^m/ ε^m-1) is developed for a problem which combines common due window assignment and scheduling n jobs on m identical parallel machines. The problem criterion is bottleneck (min-max) such that the maximum cost, which includes job earliness, job tardiness and due window size costs, is minimized.

Słowa kluczowe

EN

fully polynomial time approximation scheme; scheduling; due window assignment

PL

aproksymacja wielomianem; schemat; planowanie; okno przypisania

• Wydawca: Polska Akademia Nauk, Wydział IV Nauk Technicznych
• Czasopismo: Bulletin of the Polish Academy of Sciences. Technical Sciences
• Rocznik: 2014
• Tom: Vol. 62, nr 4
• Strony: 805--808
• Opis fizyczny: Bibliogr. 18

Twórcy

autor

Janiak A.

• Systems Research Institute, Polish Academy of Sciences, 6 Newelska St., 01-447 Warsaw, Poland

autor

Janiak W.

• The International University of Logistics and Transport in Wroclaw, 19B Soltysowicka St., 51-168 Wroclaw, Poland

autor

Kovalyov M. Y.

• United Institute of Informatics Problems, National Academy of Sciences of Belarus, Minsk, Belarus

Bibliografia

• [1] A. Janiak, T. Kwiatkowski, and M. Lichtenstein, “Scheduling problems with a common due window assignment: A survey”, Int. J. Applied Mathematics and Computer Science 23 (1), 231-241 (2013).
• [2] G. Mosheiov, “A due-window determination in minmax scheduling problems”, INFOR 39, 107-123 (2001).
• [3] G. Mosheiov and A. Sarig, “Scheduling with a common duewindow: Polynomially solvable cases”, Information Sciences 180, 1492-1505 (2010).
• [4] A. Janiak, W. Janiak, M.Y. Kovalyov, and F. Werner, “Soft due window assignment and scheduling of unit-time jobs on parallel machines”, 4OR, DOI: 10.1007/s10288-012-0201-4 (2012).
• [5] G. Mosheiov and A. Sarig, “Minmax scheduling problems with a common due-window”, Computers & Operations Research 36, 1886-1892 (2009).
• [6] A. Janiak, M.Y. Kovalyov, and M. Marek, “Soft due window assignment and scheduling on parallel machines”, IEEE Trans. on Systems, Man and Cybernetics. Part A 37, 614-620 (2007).
• [7] M.Y. Kovalyov, “Interval "-approximation algorithms of solving discrete extremum problems”, Candidate of Sciences Dissertation, Institute of Engineering Cybernetics, Academy of Sciences of BSSR, Minsk, 1986, (in Russian).
• [8] M.R. Garey and D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-completeness, W.H. Freeman and Co., San Francisco, 1979.
• [9] S. Martello and P. Toth, “Approximation schemes for the subset-sum problem: survey and experimental analysis”, Eur. J. Operational Research 22, 56-69 (1985).
• [10] M.Y. Kovalyov, M.-C. Portmann, and A. Oulamara, “Optimal testing and repairing a failed series system”, J. Combinatorial Optimization 12 (3), 279-295 (2006).
• [11] D. Depetrini and M. Locatelli, “A FPTAS for a class of linear multiplicative problems”, Computational Optimization and Applications 44 (2), 275-288 (2009).
• [12] C. Bazgan, H. Hugot, and D. Vanderpooten, “Implementing an efficient FPTAS for the 0-1 multi-objective knapsack problem”, Eur. J. Operational Research 198 (1), 47-56 (2009).
• [13] S. Hu, Z. Li, and C.J. Alpert, “A fully polynomial-time approximation scheme for timing-constrained minimum cost layer assignment”, IEEE Trans. on Circuits and Systems II: Express Briefs 56 (7), 580-584 (2009).
• [14] T. Sawik, “A mixed integer program for cyclic scheduling of flexible flow lines”, Bull. Pol. Ac.: Tech. 62 (1), 121-128 (2014).
• [15] M. Klimek and P. Lebkowski, “Robustness of schedules for project scheduling problem with cash flow optimisation”, Bull. Pol. Ac.: Tech. 61 (4), 1005-1015 (2013).
• [16] T. Cichowicz, M. Drozdowski, M. Frankiewicz, G. Pawlak, F. Rytwinski, and J. Wasilewski, “Hyper-heuristics for crossdomain search”, Bull. Pol. Ac.: Tech. 60 (4), 801-808 (2012).
• [17] W. Frohmberg, M. Kierzynka, J. Blazewicz, and P. Wojciechowski, “G-PAS 2.0 an improved version of protein alignment tool with an efficient backtracking routine on multiple GPUs”, Bull. Pol. Ac.: Tech. 60 (3), 491-494 (2012).
• [18] R.L. Graham, “Bounds on multiprocessing timing anomalies”, SIAM J. Applied Mathematics 17, 263-269 (1969).