۱- Introduction

۲- Literature review

۳- Mathematical description of OAS problem

۴- Enhancement of proposed MIP formulations

۵- A formulation-based branch-and-bound algorithm

۶- Computational experiments

۷- Conclusions

References

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.

Introduction

To maintain operational agility and flexibility, many companies from different industries, such as engineering tooling, industrial boilers, construction and contracting, adopt the make-to-order (MTO) operational philosophy, thereby laying more focus on customer satisfaction (Mestry et al., 2011). Additionally, there exists an increase in popularity of the MTO philosophy in the service industry, particularly with regard to E-commerce and O2O takeout & catering services offered within restaurants. For example, the ele.me online platform for O2O takeout & catering service covered more than 200 cities in China and had served more than 260 million customers by June 2017 (source from www.ele.me). In this context, how to coordinate operations and sales for effective use of available resource (or limited capacity) is a big challenge for improving customer satisfaction meanwhile obtaining high profit margins. The order acceptance and scheduling (OAS) problem arises in different MTO production and/or service systems, wherein limited production and/or service capacity and order-delivery requirements necessitate the use of selective order acceptance to satisfy distinct requirements of customers whilst also maximizing total revenue (profit) (Cesaret et al., 2012; Rom and Slotnick, 2009; Silva et al., 2018; Slotnick and Morton, 2007; Wang et al., 2015).