Scheduling about a common due date with job-dependent asymmetric earliness and tardiness penalties

Scheduling about a common due date with job-dependent asymmetric earliness and tardiness penalties

0.00 Avg rating0 Votes
Article ID: iaor19991204
Country: Netherlands
Volume: 98
Issue: 1
Start Page Number: 154
End Page Number: 168
Publication Date: Apr 1997
Journal: European Journal of Operational Research
Authors: , ,
Keywords: heuristics
Abstract:

This paper is concerned with the problem of scheduling n jobs with a common due date on a single machine so as to minimize the total cost arising from earliness and tardiness. A general model is examined, in which earliness penalty and tardiness penalty are, respectively, arbitrary non-decreasing functions. Moreover, the model includes two important features that commonly appear in practical problems, namely, 1) earliness and tardiness are penalized with different weights which are job-dependent, and 2) the earliness (or tardiness) penalty consists of two parts, one is a variable cost dependent on the length of earliness (or tardiness), while the other is a fixed cost incurred when a job is early (or tardy). This model provides a general and flexible performance measure for earliness/tardiness scheduling, which has not been addressed before. We establish a number of results on the characterizations of optimal and sub-optimal solutions, and propose two algorithms based on these results. The first algorithm can find, under an agreeable weight condition, an optimum in time O(n2Pn), and the second algorithm can generate a sub-optimum in time O(nPn), where Pn is the sum of the processing times. Further, we derive an upper bound on the relative error of the sub-optimal solution and show that, under certain conditions, the error tends to zero as n increases. Computational results are also reported to demonstrate the effectiveness of the algorithms proposed.

Reviews

Required fields are marked *. Your email address will not be published.