Exact methods for order acceptance and scheduling on unrelated parallel machines

作     者：Wang, Shijin Ye, Benyan 

作者机构：Tongji Univ Sch Econ & Management Shanghai 200092 Peoples R China 

出 版 物：《COMPUTERS & OPERATIONS RESEARCH》 (计算机与运筹学研究)

年 卷 期：2019年第104卷

页      面：159-173页

核心收录：

学科分类：1201[管理学-管理科学与工程(可授管理学、工学学位)] 08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：National Science Foundation of China (NSFC) Fundamental Research Funds for the Central Universities 

主　　题：Order acceptance and scheduling Unrelated parallel machines Mixed-integer programming Branch-and-bound 

摘      要：This paper studies an order acceptance and scheduling (OAS) problem on unrelated parallel machines to maximize the total net revenue of accepted orders, which is the difference between sum of revenues and total weighted tardiness. Two mixed-integer programming (MIP) models are formulated, which are further improved with various enhancement techniques. A formulation-based branch-and-bound algorithm is developed in an attempt to handle complicated instances following the principle of divide and conquer. Extensive computational experiments on various instances are conducted, and the results demonstrate the efficiency of the enhancement techniques for the formulations, as well as the effectiveness and efficiency of the formulation-based branch-and-bound algorithm. The proposed branch-and-bound algorithm can optimally solve instances with up to 50 jobs and different number of machines within the time limit of half an hour. (C) 2018 Elsevier Ltd. All rights reserved.