Exact methods for order acceptance and scheduling on unrelated parallel machines. (April 2019)

• Record Type: Journal Article
• Authors: Wang, Shijin; Ye, Benyan
• Is Part Of: Computers & operations research. Volume 104(2019)
• Page Start: 159
• Page End: 173
• Publication Date: 2019-04
• Subjects: Order acceptance and scheduling -- Unrelated parallel machines -- Mixed-integer programming -- Branch-and-bound; Operations research -- Periodicals; Electronic digital computers -- Periodicals; 004.05
• DOI: 10.1016/j.cor.2018.12.016
• Languages: English
• ISSNs: 0305-0548

Abstract

Highlights: The order acceptance and scheduling (OAS) problem on unrelated parallel machines has been studied from the viewpoint of exact solutions. Two MIP formulations have been proposed. One is based on a dummy job while the second is based on linear ordering variables. Formulation tightening and valid inequalities have been proposed to improve the efficiency of the two proposed MIP formulations. A formulation-based branch-and-bound algorithm has been developed based on the concept of "divide and conquer". Computational results for various instances demonstrate the effective- ness of the proposed branch-and-bound algorithm. Abstract: 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.