Wyniki wyszukiwania - BazTech

Ograniczanie wyników

2 Bulletin of the Polish Academy of Sciences. Technical Sciences

2 2009

Znaleziono wyników: 2

Liczba wyników na stronie

Wyniki wyszukiwania

Sortuj według:

Ogranicz wyniki do:

Single processor scheduling problems with various models of a due window assignment

Janiak A., Janiak W.A., Marek M.

Bulletin of the Polish Academy of Sciences. Technical Sciences

2009

Vol. 57, nr 1

95-101

In the paper we investigate four single processor scheduling problems, which deal with the process of the negotia-tion between a producer and a customer about delivery time of final products. This process is modeled by a due window, which is a generalization of well known classical due date and describes a time interval, in which a job should be finished. Due window assignment is a new approach, which has been investigated in the scientific literature for a few years. In this paper we consider various models of due window assignment. To solve the formu-lated problems we have to find such a schedule of jobs and such an assignment of due windows to each job, which minimizes a given criterion dependent on the maximum or total earliness and tardiness of jobs and due window parameters. One of the main results is the mirror image of the solutions of the considered problems and other problems presented in the scientific literature. The wide survey of the literature is also given.

Algorithms for parallel processor scheduling with distinct due windows and unit-time jobs

Janiak A., Janiak W.A., Januszkiewicz R.

Bulletin of the Polish Academy of Sciences. Technical Sciences

2009

Vol. 57, nr 3

209-215

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.