Exact and heuristic algorithms for order acceptance and scheduling with sequence-dependent setup times. (February 2018)

• Record Type: Journal Article
• Authors: Silva, Yuri Laio T.V.; Subramanian, Anand; Pessoa, Artur Alves
• Is Part Of: Computers & operations research. Volume 90(2018)
• Page Start: 142
• Page End: 160
• Publication Date: 2018-02
• Subjects: Order acceptance and scheduling -- Arc-time-indexed formulation -- Lagrangian relaxation -- Column generation -- Iterated local search; Operations research -- Periodicals; Electronic digital computers -- Periodicals; 004.05
• DOI: 10.1016/j.cor.2017.09.006
• Languages: English
• ISSNs: 0305-0548

Abstract

Highlights: A new arc-time-indexed formulation is proposed for the problem. A Lagrangian relaxation procedure is implemented within a branch-and-bound scheme. We present a branch-and-price algorithm based on an arc-time-indexed formulation. An iterated local search heuristic is proposed to obtain high quality primal bounds. Several improved lower and upper bounds are reported. Abstract: The Order Acceptance and Scheduling (OAS) problem consists of simultaneously deciding which orders (jobs) are going to be accepted for processing as well as their associated schedule. This problem typically arises when a company does not have the capacity to meet the demand, thus being forced to reject some orders. We consider a OAS variant where each job has a processing time, due date, release date, deadline, revenue and penalty weight. In addition, for each pair of jobs i and j, there is a setup time required before starting to process j if this job is scheduled immediately after job i . The objective is to select and schedule a subset of jobs that maximizes the total profit, which is given by the total revenue minus the total weighted tardiness. To solve this NP -hard problem, we propose a new arc-time-indexed mathematical formulation that is capable of solving instances with up to 50 jobs. However, since this formulation relies on a pseudo-polynomial number of variables, larger instances cannot be solved in practice. To overcome this limitation, we developed two exact algorithms over this formulation where the first is based on Lagrangian relaxation and the second is based on column generation. We report tight upper bounds for instances with up to 100 jobs. Moreover, we also implemented a local search based metaheuristic algorithm for obtaining high quality lower bounds. Extensive computational experiments were carried out in 1500 benchmark instances ranging from 10 to 100 jobs and the results obtained suggest that the proposed exact and heuristic methods are capable of finding extremely competitive results when compared to those available in the literature.