Minimizing Total Tardiness in Parallel-Machine Scheduling with Release Dates

Minimizing Total Tardiness in Parallel-Machine Scheduling with Release Dates

Farouk Yalaoui (University of Technology of Troyes, France)
Copyright: © 2012 |Pages: 26
DOI: 10.4018/jaec.2012010102

Abstract

The considered problem is the scheduling of a set of jobs on identical parallel machines in order to minimize the total tardiness without any preemption or splitting. Each job has its own processing time, release date and due date. All the machines are considered identical (with same speed) and available during all the scheduling period. This problem is NP-hard. An exact resolution, an Ant Colony Algorithm (ACO), a Tabu Search (TS) method, a set of Heuristics based on priority rules and an adapted Biskup Hermann Gupta (BHG) method are proposed to solve the problem. The obtained results are discussed and analyzed.
Article Preview

Introduction 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.

Complete Article List

Search this Journal:
Reset
Open Access Articles: Forthcoming
Volume 10: 4 Issues (2019): Forthcoming, Available for Pre-Order
Volume 9: 4 Issues (2018)
Volume 8: 4 Issues (2017)
Volume 7: 4 Issues (2016)
Volume 6: 4 Issues (2015)
Volume 5: 4 Issues (2014)
Volume 4: 4 Issues (2013)
Volume 3: 4 Issues (2012)
Volume 2: 4 Issues (2011)
Volume 1: 4 Issues (2010)
View Complete Journal Contents Listing