Article Preview
TopIntroduction And Literature Review
The problem considered here is the scheduling of 
jobs, products or services on 
identical parallel machines in order to minimize the total tardiness over all the considered load. The jobs are scheduled without any preemption or splitting. Each job has its own processing time, release date and due date. All the machines are identical (with same speed) and always available during all the scheduling horizon. Each machine can process at most one job at a time. A job can be processed from the time it is available, i.e., 
, where 
is the system time and 
is the release time of job 
. A job is considered as being tardy if its completion time 
is greater than its due date 
; then its tardiness value is given by 
. According to the standard Lawler's representation (Lawler, 1964) called scheduling three-parameter notation, this problem is quoted as 
. In the remainder of the paper the problem will be denoted by 
.
The jobs and the identical machines are indexed respectively from 
to 
and 
to 
. The main characteristics of each job 
are the processing time 
, the release date 
and the due date 
. A solution or a schedule, which is a unique permutation on the set 
, can be constructed by assigning the next unscheduled job in the list to the earliest available machine, ties broken by selecting the least indexed machine. A partial schedule is a permutation of a subset of 
.
The interest for tardiness criterion is due to its practical effect in the real life. This criterion is among the most interesting criteria for production systems, especially in the current situation where competitiveness is becoming more and more intensive. Suppliers do ensure their markets and customers. For that, they must have a high service quality while focusing on delivery dates.