Wyniki wyszukiwania - BazTech

1

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

Janiak A., Janiak W., Kovalyov M. Y.

Bulletin of the Polish Academy of Sciences. Technical Sciences

|

2014

|

Vol. 62, nr 4

805--808

EN

A fully polynomial time approximation scheme (FPTAS) with run time 0(nm/ ε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.

2

Scheduling problems with a common due window assignment: a survey

Janiak A., Kwiatkowski T., Lichtenstein M.

International Journal of Applied Mathematics and Computer Science

|

2013

|

Vol. 23, no. 1

231--241

EN

In this article a survey of studies on scheduling problems with a common due window assignment and earliness/tardiness penalty functions is presented. A due window is a generalization of the classical due date and describes a time interval in which a job should be finished. If a job is completed before or after the due window, it incurs an earliness or a tardiness penalty, respectively. In this survey we separately analyse the classical models with job-independent and job-dependent earliness/tardiness penalty functions and some other more complicated models. We describe the computational complexity of the problems and the main features of the approaches developed to solve them. Particular attention is paid to practical applications of the analysed models. As turns out, some complicated models combining classical scheduling problems with, e.g., learning and aging effects have no reasonable practical justification in the literature.

3

Job-Dependent Due-Window Assignment Based On A Common Flow Allowance

Mosheiov G., Oron D.

Foundations of Computing and Decision Sciences

|

2010

|

Vol. 35, No. 3

185-195

EN

A due-window assignment model is an extension of the classical due-date assignment, where a time interval (rather than a time point) is determined, such that jobs completed within this time interval are not penalized. Jobs completed outside the due-window are penalized according to their earliness/tardiness values. In this paper we solve a job-dependent due-window assignment problem, assuming a common flow allowance. We introduce an efficient 0(n log n) solution algorithm (where n is the number of jobs). We then consider the case of position-dependent processing times, showing that the problem remains solvable in polynomial time.

4

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

EN

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.