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
Top

Introduction And Literature Review

The problem considered here is the scheduling of jaec.2012010102.m03 jobs, products or services on jaec.2012010102.m04 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., jaec.2012010102.m05, where jaec.2012010102.m06 is the system time and jaec.2012010102.m07 is the release time of job jaec.2012010102.m08. A job is considered as being tardy if its completion time jaec.2012010102.m09 is greater than its due date jaec.2012010102.m10; then its tardiness value is given by jaec.2012010102.m11. According to the standard Lawler's representation (Lawler, 1964) called scheduling three-parameter notation, this problem is quoted as jaec.2012010102.m12. In the remainder of the paper the problem will be denoted by jaec.2012010102.m13.

The jobs and the identical machines are indexed respectively from jaec.2012010102.m14 to jaec.2012010102.m15 and jaec.2012010102.m16 to jaec.2012010102.m17. The main characteristics of each job jaec.2012010102.m18jaec.2012010102.m19 are the processing time jaec.2012010102.m20, the release date jaec.2012010102.m21 and the due date jaec.2012010102.m22. A solution or a schedule, which is a unique permutation on the set jaec.2012010102.m23, 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 jaec.2012010102.m24.

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 11: 4 Issues (2020): 2 Released, 2 Forthcoming
Volume 10: 4 Issues (2019)
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