Soft due window assignment and scheduling of unit-time jobs on parallel machines |
| |
Authors: | Adam Janiak Wladyslaw Janiak Mikhail Y. Kovalyov Frank Werner |
| |
Affiliation: | 1. Institute of Computer Engineering, Control and Robotics, Wroc?aw University of Technology, Janiszewskiego 11/17, 50-372, Wroc?aw, Poland 2. Faculty of Computer Science and Management, Wroc?aw University of Technology, ?ukasiewicza 5, 50-371, Wroc?aw, Poland 3. United Institute of Informatics Problems, National Academy of Sciences of Belarus, Surganova 6, 220012, Minsk, Belarus 4. Faculty of Mathematics, Otto-von-Guericke-University Magdeburg, PSF 4120, 39016, Magdeburg, Germany
|
| |
Abstract: | We study problems of scheduling n unit-time jobs on m identical parallel machines, in which a common due window has to be assigned to all jobs. If a job is completed within the due window, then no scheduling cost incurs. Otherwise, a job-dependent earliness or tardiness cost incurs. The job completion times, the due window location and the size are integer valued decision variables. The objective is to find a job schedule as well as the location and the size of the due window such that a weighted sum or maximum of costs associated with job earliness, job tardiness and due window location and size is minimized. We establish properties of optimal solutions of these min-sum and min-max problems and reduce them to min-sum (traditional) or min-max (bottleneck) assignment problems solvable in O(n 5/m 2) and O(n 4.5log0.5 n/m 2) time, respectively. More efficient solution procedures are given for the case in which the due window size cost does not exceed the due window start time cost, the single machine case, the case of proportional earliness and tardiness costs and the case of equal earliness and tardiness costs. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|