BULLETIN of the

POLISH ACADEMY of SCIENCES

TECHNICAL SCIENCES

 BULLETIN of the POLISH ACADEMY of SCIENCES: TECHNICAL SCIENCES
Volume 57, Issue 3, September 2009

Modeling and optimization of manufacturing systems
Issue Index Authors Index Scope Index  Web Info
Aims&Scope, Subscription Editors Authors' guide to read PDF files mirror: http://fluid.ippt.gov.pl/~bulletin/
pp 209 - 215

PDF -  128 KB

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

A. JANIAK, W.A. JANIAK, and R. JANUSZKIEWICZ
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 tardy 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.
Key words:

scheduling algorithms, parallel processor, earliness/tardiness, distinct due windows, unit-time jobs, integer release dates.

Issue Index Authors Index Scope Index  Web Info
Aims&Scope, Subscription Editors Authors' guide to read PDF files
Copyright ® Bulletin of the Polish Academy of Sciences: Technical Sciences

October 2009