A Column Generation Algorithm for the Resource-Constrained Order Acceptance and Scheduling on Unrelated Parallel Machines. (20th October 2021)

• Record Type: Journal Article
• Authors: Song, Yujian; Xue, Ming; Hua, Changhua; Wang, Wanli
• Other Names: Neagu Adrian Academic Editor.
• Is Part Of: Mathematical problems in engineering. Volume 2021(2021)
• Publication Date: 2021-10-20
• Subjects: Engineering mathematics -- Periodicals; 510.2462
• DOI: 10.1155/2021/5566002
• Languages: English
• ISSNs: 1024-123X

Abstract

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.