Single machine scheduling problems with generalised due-dates and job-rejection
Authors:
- 20 December 2016
- journal article
- research article
- Published by Taylor & Francis in International Journal of Production Research
- Vol. 55 (11) , 3164-3172
Abstract
We study single machine scheduling problems. Generalised due dates are assumed, i.e. job due dates are specified according to the positions of the jobs in the sequence, rather than their identity. Thus, assuming that due dates are numbered in a non-decreasing order, the jth due date refers to the job assigned to the jth position. In addition, we allow the option of job rejection, i.e. not all jobs must be processed. In this case, the scheduler is penalised for each rejected job, and the total rejection cost becomes part of the objective function. Two objective functions are considered: maximum tardiness plus rejection cost, and total tardiness plus rejection cost. Both problems are proved to be NP-hard. Pseudo-polynomial dynamic programmes and efficient heuristics are introduced and tested numerically.Keywords
Funding Information
- Israel Science Foundation (1286/14)
- Hebrew University
This publication has 18 references indexed in Scilit:
- Minimizing maximum cost on a single machine with two competing agents and job rejectionJournal of the Operational Research Society, 2016
- Scheduling with job-rejection and position-dependent processing times on proportionate flowshopsOptimization Letters, 2016
- Scheduling a single machine with parallel batching to minimize makespan and total rejection costDiscrete Applied Mathematics, 2016
- A tabu search algorithm for order acceptance and schedulingComputers & Operations Research, 2012
- A note on the SPT heuristic for solving scheduling problems with generalized due datesComputers & Operations Research, 2004
- A survey of the state-of-the-art of common due date assignment and scheduling researchEuropean Journal of Operational Research, 2002
- On the complexity of generalized due date scheduling problemsEuropean Journal of Operational Research, 1991
- Minimizing Total Tardiness on One Machine is NP-HardMathematics of Operations Research, 1990
- Scheduling Problems With Generalized Due DatesIIE Transactions, 1986
- Optimal Sequencing of a Single Machine Subject to Precedence ConstraintsManagement Science, 1973