A bi-objective model for the single-machine scheduling problem with rejection cost and total tardiness minimization. (February 2019)

• Record Type: Journal Article
• Authors: Cordone, Roberto; Hosteins, Pierre
• Is Part Of: Computers & operations research. Volume 102(2019)
• Page Start: 130
• Page End: 140
• Publication Date: 2019-02
• Subjects: Scheduling with rejection -- Total tardiness -- Bi-objective optimization -- Dynamic programming -- Branch-and-bound; Operations research -- Periodicals; Electronic digital computers -- Periodicals; 004.05
• DOI: 10.1016/j.cor.2018.10.006
• Languages: English
• ISSNs: 0305-0548

Abstract

Highlights: First bi-objective study of the total tardiness single machine problem with rejection. We provide a Dynamic Program in the case with no hard deadlines. We provide a Branch and Bound algorithm in the case with hard deadlines. We display the efficiency of our B&B on benchmark instances. Abstract: We study the problem of scheduling jobs on a single machine with a rejection possibility, concurrently minimizing the total tardiness of the scheduled jobs and the total cost of the rejected ones. The model we consider is fully bi-objective, i.e. its aim is to enumerate the Pareto front. We tackle the problem both with and without the presence of hard deadlines. For the case without deadlines, we provide a pseudo-polynomial time algorithm, based on the dynamic program of Steiner and Zhang (2011), thereby proving that the problem is weakly NP-hard. For the case with deadlines, we propose a branch-and-bound algorithm and prove its efficiency by comparing it to an ε-constrained approach on benchmark instances based on those proposed in the literature on similar problems.