Powiadomienia systemowe
- Sesja wygasła!
- Sesja wygasła!
- Sesja wygasła!
Tytuł artykułu
Autorzy
Wybrane pełne teksty z tego czasopisma
Identyfikatory
Warianty tytułu
Języki publikacji
Abstrakty
We have studied problems of scheduling n unit-time jobs on m identical parallel processors, in which for each job a distinct due window is given in advance. If a job is completed within its due window, then it incurs no penalty. Otherwise, it incurs a job-dependent earliness or tardiness cost. The objective is to find a job schedule such that the total weighted earliness and tardiness, maximum weighted earliness and tardiness or total weighted number of early and lardy jobs is minimized. Properties of optimal solutions of these problems are established. We proved that optimal solutions for these problems can be found in O(n5) time in case of minimization of the total weighted earliness and tardiness and the total weighted number of early and tardy jobs and in O (n4 n log n) time in case of minimization of the maximum weighted earliness and tardiness. The established solution methods are extended to solve the problems with arbitrary integer release dates. A dedicated algorithm with time complexity O(n3) is provided for the special case of the problem of minimizing total weighted number of early and tardy jobs with agreeable earliness-tardiness weights.
Rocznik
Tom
Strony
209--215
Opis fizyczny
Bibliogr. 12 poz.
Twórcy
autor
autor
autor
- Institute of Computer Engineering, Control and Robotics, Wroclaw University of Technology, 11/17 Janiszewskiego St., 50-372 Wroclaw, Poland, adam.janiak@pwr.wroc.pl
Bibliografia
- [1] J. Sidney, "Optimal single-machine scheduling with earliness and tardiness penalties", Operation Research 25 (1), 62--69 (1977).
- [2] E.L. Lawler, "A pseudopolynomial algorithm for sequence jobs to minimizing total tardiness", Annals of Discrete Mathematics 1, 331--342 (1977).
- [3] C. Koulamas, "Single-machine scheduling with time windows and earliness/tardiness penalties", Eur. J. Operational Research 96, 190-202 (1996).
- [4] G. Wan and B.P.-C. Yen, "Tabu-search for single machine scheduling with distinct due windows and weighted earliness/tardiness penalties", Eur. J. Operational Research 142, 271-281 (2002).
- [5] C. Koulamas, "Maximizing the weighted number of on-time jobs in single machine scheduling with time windows", Mathematical and Computer Modeling 25 (10), 57-62 (1997).
- [6] W.-S. Yoo and L.A. Martin-Vega, "Scheduling single-machines problems for on-time delivery", Computers & Industrial Engineering 39, 371-392 (2001).
- [7] A. Janiak, W.A. Janiak, and M. Marek, "Single processor scheduling problems with various models of a due window", Bull. Pol. Ac.: Tech. 57 (1), 95-101 (2009).
- [8] J. Blazewicz, K.H. Ecker, E. Pesch, G. Schmidt, and J. Węglarz, Handbook on Scheduling. From Theory to Applications, Springer, Berlin, 2007.
- [9] Peter Brucker, Scheduling Algorithms, Springer, Berlin, 2007.
- [10] P. Baptiste, P. Brucker, S. Knust, and V. Timkovsky, "Ten notes on equal-execution-time scheduling", 4OR 2, 111-127 (2004).
- [11] M.L. Fredman, R.E. Tarjan, "Fibonacci heaps and their uses in improved network optimization algorithms", J. ACM 34 (3), 596-615 (1987).
- [12] A.P. Punnen and R. Zhang, "Bottleneck Mows in unit capacity networks". Information Processing Letters 109, 334-338 (2009).
Typ dokumentu
Bibliografia
Identyfikator YADDA
bwmeta1.element.baztech-article-BPG5-0040-0021