A Column Generation Algorithm for the Resource-Constrained Order Acceptance and Scheduling on Unrelated Parallel Machines

Yujian Song, Ming Xue, Changhua Hua and Wanli Wang

Mathematical Problems in Engineering, 2021, vol. 2021, 1-17

Abstract:

In this paper, we investigate the resource-constrained order acceptance and scheduling on unrelated parallel machines that arise in make-to-order systems. The objective of this problem is to simultaneously select a subset of orders to be processed and schedule the accepted orders on unrelated machines in such a way that the resources are not overutilized at any time. We first propose two formulations for the problem: mixed integer linear programming formulation and set partitioning. In view of the complexity of the problem, we then develop a column generation approach based on the set partitioning formulation. In the proposed column generation approach, a differential evolution algorithm is designed to solve subproblems efficiently. Extensive numerical experiments on different-sized instances are conducted, and the results demonstrate that the proposed column generation algorithm reports optimal or near-optimal solutions that are evidently better than the solutions obtained by solving the mixed integer linear programming formulation.

Date: 2021
References: Add references at CitEc
Citations:

Downloads: (external link)
http://downloads.hindawi.com/journals/MPE/2021/5566002.pdf (application/pdf)
http://downloads.hindawi.com/journals/MPE/2021/5566002.xml (text/xml)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:hin:jnlmpe:5566002

DOI: 10.1155/2021/5566002

Access Statistics for this article

More articles in Mathematical Problems in Engineering from Hindawi
Bibliographic data for series maintained by Mohamed Abdelhakeem ().