Abstract: In operational systems of firms, scheduling significantly influences the performance. At the same time, with the application of just-in-time concept, due-date assignment also plays an important role in operational systems, which requires customer orders should be finished at a assigned time. In brief, through delicate scheduling rule and appropriate due-date assignment, firm’s limited production resource can be utilized more efficiently, and at the same time they can be better matched with varied customer demands. Thus, the decisions of scheduling and due-date assignment are usually decided simultaneously. However, for many practical application scenarios, it is allowable to complete customer orders within a period. Under these cases, decision makers need to determine due windows for customer orders instead of due dates. A due window for a job consists of three parts: the starting time of due window, the finishing time of due window and the due window size. In literature on due-window assignment scheduling problems, decision makers often assign the same due window for all customers to maintain a unified customer service policy. But the size of due window can be fixed directly by decision makers or can be negotiated with customers. In addition, the existing researches always assume jobs to be finished before the starting time of due window or after the finishing time of due window would incur cost due to earliness or tardiness, but jobs to be completed within due window would not result in any cost. Besides the influence of due window assignment method on formulating and solving due-window assignment scheduling problems, other interference factors existing in operational systems also exert an influence. Among these factors, jobs deterioration would change their actual processing times, and further influences the way the due-window assignment scheduling problem is solved. In the field of studies on due-window assignment scheduling problems with deterioration jobs, it is often assumed that the actual processing time of a job is a linear function of its starting processing time and deterioration rate.
This paper studies the due-window assignment scheduling problem with deteriorating jobs in a single machine environment. The common due-window assignment method is applied to assign a due window for all jobs, and the beginning time of due window and the size of due window are decision variable. The actual processing time of a job is a linear function of its starting processing time and deterioration rate, and jobs have various deterioration rates. The objective of the problem is to simultaneously determine the scheduling policy and the common due window for all jobs, so as to minimize the total costs associated with earliness, tardiness and due-window assignment. To deal with the problem that we consider, we first introduce some notations and formally describe the problem with classical scheduling language. On the basis, we analyze the property of optimal due-window assignment and propose the optimal rule to assign due windows for all jobs. Then, we analyze the property of optimal schedule and propose the specific rule to schedule early jobs, tardy jobs and jobs to be completed within due window, respectively. Based on this, we point out the way jobs are scheduled in different sets, which are the set of early jobs, the set of tardy jobs and the set of jobs to be finished within due window. With those conclusions about optimal schedule and due-window assignment, we derive the way the studied problem is solved and propose the solution algorithm formally. For the proposed algorithm, we finallyanalyze the computational complexity by computing the computational time for each step in the algorithm. By careful analysis, we conclude that the proposed optimal algorithm is polynomial.

Key words: single machine scheduling, common due window, deteriorating jobs, polynomial algorithm

摘要： 为了研究考虑公共交货期窗口问询的退化工件排序问题,构建了极小化因提前时间、延误时间以及交货期窗口问询产生的总成本的单机排序调度决策模型。模型假定所有工件的交货期窗口一致,且窗口的开始时间、窗口大小为决策变量;工件具有差异化的退化因子;工件的实际加工时间与其开始加工时间、退化因子呈线性关系。分析了交货期窗口决策和工件排序具有的最优性质,以及最优的工件排序与工件退化因子之间的关系,并提出了最优算法。研究表明:可基于工件的退化因子确定最优工件加工顺序,最优交货期窗口的开始时间和结束时间分别对应于最优序中某个工件的完工时间,研究问题可在多项式时间内进行求解。

关键词: 单机排序, 公共交货期窗口, 退化因子, 多项式时间算法