Order acceptance and scheduling on unrelated parallel machines
DOI:
https://doi.org/10.54097/hbem.v4i.3371Keywords:
Order acceptance, Scheduling, Unrelated parallel machinesAbstract
This paper considers an order acceptance and scheduling problem on unrelated parallel machines. The objective is to select and schedule a subset of accepted orders that maximizes the total profit, which is defined as the sum of revenues of all the accepted orders minus their weighted tardiness penalties. We formulate the problem as a mixed-integer linear programming model. To solve this strongly NP-hard problem, we also propose a heuristic algorithm based on the Lagrangian relaxation technique and some greedy search operations.
Downloads
References
Esmaeilbeigi R, Charkhgard P, Charkhgard H. Order acceptance and scheduling problems in two-machine flow shops: New mixed integer programming formulations[J]. European Journal of Operational Research, 2016. 251(2): 419-431.
Slotnick S A, Morton T E. Order acceptance with weighted tardiness[J]. Computers & Operations Research, 2007, 34(10): 3029-3042.
Nobibon F T, Leus R. Exact algorithms for a generalization of the order acceptance and scheduling problem in a single-machine environment[J]. Computers & Operations Research, 2011, 38(1): 367-378.
Oguz C, Salman F S, Yalcin Z B. Order acceptance and scheduling decisions in make-to-order systems[J]. International Journal of Production Economics, 2010, 125(1): 200-211.
Cesaret B, Oguz C, Salman F S. A tabu search algorithm for order acceptance and scheduling[J]. Computer & Operations Research, 2012, 39(6): 1197-1205.
Lin S W, Ying K. Increasing the total net revenue for single machine order acceptance and scheduling problems using an artificial bee colony algorithm[J]. Journal of the Operational Research Society, 2013, 64: 293-311.
Chaurasia S N, Singh A. Hybrid evolutionary approaches for the single machine order acceptance and scheduling problem[J]. Applied Soft Computing, 2017, 52: 725-747.
Silva Y L T V, Subramanian A, Pessoa A A. Exact and heuristic algorithm for order acceptance and scheduling with sequence-dependent setup times[J]. Computers & Operations Research, 2018, 90: 142-160.
Wang X, Xie X, Cheng T C E. A modified artificial bee colony algorithm for order acceptance in two-machine flow shops [J]. International Journal of Production Economics, 2013, 141(1): 14-23.
Wang X, Xie X, Cheng T C E. Order acceptance and scheduling in a two-machine flowshop[J]. International Journal of Production Economics, 2013, 141(1): 366-376.
Wang X, Huang G, Hu X, et al. Order acceptance and scheduling on two identical parallel machines[J]. Journal of the Operational Research Society, 2015, 66(10): 1755-1767.
Wu G H, Cheng C Y, Yang H I, et al. An improved water flow-like algorithm for order acceptance and scheduling with identical parallel machines[J]. Applied Soft Computing, 2018, 71: 1072-1084.
Wang S, Ye B. Exact methods for order acceptance and scheduling on unrelated parallel machines[J]. Computers & Operations Research, 2019, 104:159-173.
Ou J, Zhong X. Bicriteria order acceptance and scheduling with consideration of fill rate[J]. European Journal of Operational Research, 2017, 262(3): 904-907.
Ou J, Zhong X, Wang G. An improved heuristic for parallel machine scheduling with rejection[J]. European Journal of Operational Research, 2015, 241(3): 653-661.
Ou J, Zhong X, Qi X. Scheduling parallel machines with inclusive processing set restrictions and job rejection[J]. Naval Research Logistics, 2016, 63: 667-681.
Slotnick S A, Order acceptance and scheduling: A taxonomy and review[J]. European Journal of Operational Research, 2011, 212(1): 1-11.
Downloads
Published
Issue
Section
License
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
How to Cite
