Minimizing maximum delivery completion time for order scheduling with rejection
- PDF / 408,666 Bytes
- 21 Pages / 439.37 x 666.142 pts Page_size
- 29 Downloads / 201 Views
Minimizing maximum delivery completion time for order scheduling with rejection Ren-Xia Chen1 · Shi-Sheng Li2
© Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract We study an order scheduling problem with rejection, in which each order consists of multiple product types and each product type should be manufactured on a dedicated machine. The aim is to find a solution to minimize a linear sum of the maximum delivery completion time of the accepted orders and the total penalty of the rejected orders. Even if the delivery times of all orders are zero, the problem is shown to be binary N P-hard in the two-machine case and it is shown to be unary N P-hard when the number of machines is arbitrary. Three approximation algorithms are proposed and their worst-case performance ratios are analyzed. For the scenario where the number of machines is fixed, a pseudo-polynomial dynamic programming algorithm and a fully polynomial time approximation scheme are devised for it. Keywords Order scheduling · Maximum delivery completion time · Rejection · Approximation algorithm
1 Introduction Due to its wide application in manufacturing and service operations management, the topic of customer order scheduling (COS) has attracted much attention. Unlike classical job scheduling problems, in many situations, each customer order is composed of multiple components and each component has to be manufactured on a dedicated machine. An order is completed only when all its components are all finished. COS models arises in many application environments, such as, the production of components for subsequent assembly in an electronics manufacturing facility (Yang 2005),
B
Shi-Sheng Li [email protected]
1
Department of Applied Mathematics, Zhongyuan University of Technology, Zhengzhou 450007, People’s Republic of China
2
Department of Information and Computation Science, Zhongyuan University of Technology, Zhengzhou 450007, People’s Republic of China
123
Journal of Combinatorial Optimization
the converting operation in the paper converting facility (Leung et al. 2006b), the sintering operation of the production process in electric-ceramic industry (Shi et al. 2018), etc. At the same time, in those highly loaded make-to-order manufacturing environments in which the production capacity is limited and the delivery requirements are tight, accepting all orders may result in overloads in some periods, and this in turn incurs tardiness and customer dissatisfaction. Therefore, for the purpose of retaining acceptable quality of service and maintaining customer satisfaction, the decisionmaker may desire to reject the processing of some orders by either outsourcing them to the third party or rejecting them altogether (Cesaret et al. 2012; Shabtay et al. 2013). Given the above, the focus of this paper is to investigate a COS model with rejection, in which the aim is to find a solution to minimize the total integrated cost that includes the maximum delivery completion time of the accepted orders and the total penalty of the
Data Loading...
