Benchmarks for scheduling on a single machine against restrictive and unrestrictive common due dates

https://doi.org/10.1016/S0305-0548(00)00008-3Get rights and content

Abstract

We consider the NP-hard problem of scheduling jobs on a single machine against common due dates with respect to earliness and tardiness penalties. The paper covers two aspects: Firstly, we develop a problem generator and solve 280 instances with two new heuristics to obtain upper bounds on the optimal objective function value. Secondly, we demonstrate computationally that our heuristics are efficient in obtaining near-optimal solutions for small problem instances. The generated problem instances in combination with the upper bounds can be used as benchmarks for future approaches in the field of common due-date scheduling.

Scope and purpose

In connection with just-in-time production and delivery, earliness as well as tardiness penalties are of interest. Thus scheduling against common due dates has received growing attention during the last decade. Many algorithms have been developed to solve the different variants of this problem. But whenever a new algorithm for scheduling against common due dates is proposed, its quality is assessed only on a few self-generated examples. Hence it is difficult to evaluate the various approaches, particularly in comparison with each other. Therefore the goal of this paper is to present numerous benchmark problems together with some upper bounds on the optimal objective function value.

Introduction

Common due-date problems have been studied extensively during the last 20 years. In practice, a common due date occurs, for example, if in an assembly schedule a set of jobs is needed simultaneously, see Kanet [1], or if one customer orders a bundle of perishable goods which have to be delivered at a prespecified time.

When scheduling on a single machine against a common due date, one job at most can be completed exactly at the due date. Hence, some of the jobs have to be completed early, that is prior to the due date, while other jobs must be finished late. In both cases certain costs are incurred: early jobs tie up capital and cause holding costs while the effects of tardy jobs are dissatisfied customers and thus — in the long run — the loss of goodwill and reputation. In this context the goal is to find a schedule which jointly minimizes the sum of earliness and tardiness costs.

Generally speaking, there are two classes of common due-date problems which have proven to be NP-hard, namely if a restrictive common due date is given or if different jobs incur different penalties. In this paper we propose benchmarks for both classes of problems. This is done by the generation of restrictive common due-date problems with distinct and job-individual earliness and tardiness penalties, which seem to be the most difficult problems in this area of research.

The following section introduces the problem formulation and gives a short review of the literature on scheduling against common due dates. In the third section the idea and application of a short Pascal code to generate benchmark problems is described, for which we calculate upper bounds from two heuristics presented in the forth section.

Section snippets

Problem formulation

There are n jobs available at time zero, which have to be processed on a single machine. Each of these jobs needs exactly one operation. The processing times pi of the jobs i=1,…,n are deterministic and known, preemption of jobs is not allowed. If the completion time Ci of job i is smaller than or equal to the common due date d, which is assumed as given, the jobs’ earliness is Ei=d−Ci. Accordingly, a job i is tardy with the tardiness Ti=Ci−d, if its completion time is greater than the common

Generating benchmark problems

For the restrictive general problem, i.e. that of the south-east corner of Table 1, we propose benchmark problems with 10,20,50,100,200,500 and 1000 jobs. For each of these problem sizes 10 different instances are generated, hence we obtain 70 problem instances altogether. The instances are generated by using the well-known linear congruential random number generator developed by Lehmer [13].

In the following, we give a brief description of the random number generator used for a computer with a

Heuristical approaches to the restrictive general problem

As mentioned before an optimization algorithm for the restrictive common due-date problem with general penalties has never been proposed. The only researchers who have studied this problem have been Lee and Kim [16] and James [17], in both cases using metaheuristics, namely parallel genetic algorithms and tabu search. We decided not to adopt their approaches for two reasons. Firstly, both limit their search space to schedules in which the first job starts at time zero, although this might

Conclusions

In this paper we presented 280 benchmarks for the restrictive common due-date problem with general earliness and tardiness penalties. We hope that future approaches to tackling this NP-hard problem will use the proposed benchmarks in order to make the results and hence the quality of the algorithms comparable, see Feldmann and Biskup [20].

The authors are gladly willing to distribute a longer and more user-friendly version of the problem generator by email.

Acknowledgments

We wish to thank two anonymous referees for their helpful comments on an earlier version of this paper.

Dirk Biskup obtained a degree in Economics and Business Administration from the University of Hamburg. At the moment he is working as a Research Assistant at the Chair of Production, Operations Management and Managerial Accounting (Professor Jahnke) at the University of Bielefeld, Germany. The theme of his doctorial thesis is scheduling against due dates. His research interests are in single and parallel machine scheduling, lotsizing and cost allocation.

References (20)

There are more references available in the full text version of this article.

Cited by (0)

Dirk Biskup obtained a degree in Economics and Business Administration from the University of Hamburg. At the moment he is working as a Research Assistant at the Chair of Production, Operations Management and Managerial Accounting (Professor Jahnke) at the University of Bielefeld, Germany. The theme of his doctorial thesis is scheduling against due dates. His research interests are in single and parallel machine scheduling, lotsizing and cost allocation.

Martin Feldmann obtained a Ph.D. in Economics and Business Administration from the University of Bielefeld. At the moment he is working as an Assistant Professor at the Chair of Operations Research and Business Administration (Professor Kistner) at the University of Bielefeld, Germany. His research interests are in production and Operations Management, Logistics and Metaheuristics.

View full text
Copyright © 2001 Elsevier Science Ltd. All rights reserved.