A Lagrangian relaxation algorithm for order acceptance and scheduling problem: a globalised robust optimisation approach
In this paper, a simultaneous order acceptance and scheduling problem in a non-identical parallel machines environment is considered. The order is defined by their due date, revenue, tardiness penalty, different processing times on the machines, and sequence-dependent set-up times.
A mixed-integer linear programming (MILP) formulation is presented to maximise profit. Furthermore, it is assumed that the revenue from an accepted order and the processing times are uncertain; the globalized robust counterpart (GRC) of the proposed MILP model is presented such that the normal
range of the perturbation is the intersection of a box and a polyhedral. The problem is computationally intractable. Therefore, the Lagrangian relaxation algorithm is developed to solve it. A cutting plane method is used to update the Lagrangian multipliers and a heuristic method is presented
to obtain feasible solutions. Through numerical experiments on randomly generated large instances with up to 40 orders and six machines, the authors demonstrate that the proposed Lagrangian algorithm outperforms the monolithic MILP model. Furthermore, a simulation study demonstrates that,
on average, the GRC of the MILP model provides slightly better results in comparison with its conventional robust counterpart.
Keywords: Lagrangian relaxation algorithm; globalised robust counterpart; non-identical parallel machines; order acceptance and scheduling
Document Type: Research Article
Affiliations: Department of Industrial & Systems Engineering, Isfahan University of Technology, Isfahan, Iran
Publication date: 03 May 2016
- Editorial Board
- Information for Authors
- Subscribe to this Title
- Ingenta Connect is not responsible for the content or availability of external websites
- Access Key
- Free content
- Partial Free content
- New content
- Open access content
- Partial Open access content
- Subscribed content
- Partial Subscribed content
- Free trial content