出版社：Academy & Industry Research Collaboration Center (AIRCC)
摘要：This paper studies the job-scheduling problem on m ≥ 2 parallel/identical machines.There are n
jobs, denoted by Ji
,,1 ≤ i ≤ n. Each job Ji
, has a due date di
. A job has one or more tasks, each
with a specific processing time. The tasks can’t be preempted, i.e., once scheduled, a task
cannot be interrupted and resumed later. Different tasks of the same job can be scheduled
concurrently on different machines. A job is on time if all of its tasks finish before its due date;
otherwise, it is tardy. A schedule of the jobs specifies which task is scheduled on which machine
at what time. The problem is to find a schedule of these jobs so that the number of on time jobs
is maximized; or equivalently, the number of tardy jobs is minimized. We consider two cases:
the case when each job has only a single task and the case where a job can have one or more
tasks. For the first case, if all jobs have common due date we design a simple algorithm and
show that the algorithm can generate a schedule whose number of on time jobs is at most (m-1)
less than that of the optimal schedule. We also show that the modified algorithm works for the
second case with common due date and has same performance. Finally, we design an algorithm
when jobs have different due dates for the second case. We conduct computation experiment and
show that the algorithm has very good performance.
关键词：On time job; identical machines; order scheduling
