Order acceptance and scheduling with delivery under generalized parameters
定义了机器调度中的四种广义参数（释放时间、加工时间、拒绝成本、配送时间），研究在配送约束下如何选择订单并安排生产，以最小化最大配送完成时间与拒绝惩罚成本之和，给出了多项式时间可解和NP难问题的算法。
Abstract Inspired by the concept of generalized due dates introduced by Hall ( IIE Transactions , 18(2), 220–222), in this article we first define four new generalized parameters in machine scheduling: the generalized release dates (GRD), generalized processing times (GPT), generalized rejection costs (GRC), and generalized delivery times (GDT). We then study order acceptance and scheduling problems with delivery consideration under the generalized parameters of GRD, GPT, GRC, and GDT, respectively. The objective of each scheduling problem in consideration is to minimize the maximum delivery completion time of the accepted jobs plus the total rejection penalty cost of the rejected jobs. We show that two of the six problems studied in this article are weakly NP‐hard while the other four ones can be solved in polynomial time. For each NP‐hard problem, we provide a pseudo‐polynomial time algorithm, a 2‐approximation algorithm and a fully polynomial‐time approximation scheme.