The single-machine earliness-tardiness scheduling problem with due date assignment and resource-dependent processing times

We study the earliness-tardiness scheduling problem on a single machine with due date assignment and controllable processing times. We analyze the problem with three different due date assignment methods and two different processing time functions. For each combination of these, we provide a polynomial-time algorithm to find the optimal job sequence, due date values and resource allocation minimizing an objective function which includes earliness, tardiness, due date assignment, makespan and total resource consumption costs.     

具有CON/SLK交货期指派的一类单机排序问题

研究工件的实际加工时间既具有指数学习效应,又依赖所消耗资源的准时制排序问题.在模型中,探讨了共同交货期(CON)和松弛交货期(SLK)两种情形.管理者的目标是确定最优序、最优资源分配方案和最佳工期(共同交货期或松弛交货期)以便极小化工件的总延误、总提前、总工期和资源消耗费用的总和.对于工件的实际加工时间是资源消耗量的线性函数的排序问题,通过将其转化为指派模型,给出了时间复杂性为O(n~3)的算法,从而证明该类排序问题是多项式时间可求解的.针对工件的实际加工时间是资源消耗量的凸函数的排序问题,也给出了多项式算法.     

Single machine scheduling problems with general position-dependent processing times and past-sequence-dependent delivery times

This paper considers single machine scheduling with past-sequence-dependent (psd) delivery times, in which the processing time of a job depends on its position in a sequence. We provide a unified model for solving single machine scheduling problems with psd delivery times. We first show how this unified model can be useful in solving scheduling problems with due date assignment considerations. We analyze the problem with four different due date assignment methods, the objective function includes costs for earliness, tardiness and due date assignment. We then consider scheduling problems which do not involve due date assignment decisions. The objective function is to minimize makespan, total completion time and total absolute variation in completion times. We show that each of the problems can be reduced to a special case of our unified model and solved in O(n ³) time. In addition, we also show that each of the problems can be solved in O(nlogn) time for the spacial case with job-independent positional function.     

具有老化效应的单机共同工期安排和工件可拒绝排序问题

研究共同工期安排和具有老化效应的单机排序问题。在整个加工过程中,工件的实际加工时间是与其所在位置和工件本身老化率相关的函数,生产商可以通过支付一定的处罚费用而拒绝加工某些工件。鉴于生产过程中出现老化效应,通过采取维修活动来提高生产率。目标是划分接受工件集和拒绝工件集,确定接受工件集中工件的加工次序和维修活动安排的位置,以极小化接受工件的提前、延误、工期与拒绝工件的总处罚费用的加权和。对这一问题,首先将其转化为指派问题并构造了最优多项式时间算法;其次,证明了目标函数满足一定条件下的问题的更一般形式能够在多项式时间内得到最优解;最后,对本文问题的一个特殊情况,设计了具有更低时间复杂度的多项式动态规划算法。     

带学习效应和资源依赖的单机排序模型

在工业生产中,随着员工操作技能的熟练程度的增加,对于相同的任务越往后加工,所花的时间将会减少。 同时,为了尽早完工,管理者也会考虑给加工工件分配一定量的额外资源来缩短工件加工时间。 本文基于以上实例,讨论了工件的实际加工时间既具有学习效应又依赖所分配资源的单机排序问题。 在问题中,假设工件的学习效应是之前已加工工件正常加工时间和的指数函数。 同时随着分配给工件资源量的增加,工件的实际加工时间呈线性减少,所需费用呈线性增加。对这一排序模型,主要探讨以下五个目标函数:最小化最大完工时间与资源消耗量总费用的和;最小化总完工时间与资源消耗量总费用的和;最小化加权总完工时间与资源消耗量总费用的和;最小化总提前、总延误、总共同交货期与资源消耗量总费用的和以及最小化总提前、总延误、总松弛交货期与资源消耗量总费用的和。 本文对前三个目标函数相应的排序问题给出了多项式时间可求解的算法。 对后两个目标函数所涉及的排序问题借助于指派问题分别给出了时间复杂性为O(n³)的算法。     

Single machine scheduling and due date assignment with positionally dependent processing times

We consider single machine scheduling and due date assignment problems in which the processing time of a job depends on its position in a processing sequence. The objective functions include the cost of changing the due dates, the total cost of discarded jobs that cannot be completed by their due dates and, possibly, the total earliness of the scheduled jobs. We present polynomial-time dynamic programming algorithms in the case of two popular due date assignment methods: CON and SLK. The considered problems are related to mathematical models of cooperation between the manufacturer and the customer in supply chain scheduling.     

Single machine common flow allowance scheduling with controllable processing times

In this paper, we consider single machine SLK due date assignment scheduling problem in which job processing times are controllable variables with linear costs. The objective is to determine the optimal sequence, the optimal common flow allowance and the optimal processing time compressions to minimize a total penalty function based on earliness, tardiness, common flow allowance and compressions. We solve the problem by formulating it as an assignment problem which is polynomially solvable. For some special cases, we present an O(n logn) algorithm to obtain the optimal solution respectively.     

带凸资源和恶化效应的单机松弛窗口排序

研究带凸资源和恶化效应的单机窗口指派排序问题,其中窗口指的是松弛窗口,凸资源和恶化效应指的是工件的实际加工时间是其开始加工时间的线性函数,是其资源消耗量的凸函数。目标是确定工件的加工顺序,资源分配量以及窗口的开始加工时间和长度使其在总资源消耗费用(与窗口有关的排序费用)有上界限制的条件下,极小化与窗口有关的排序费用(总资源消耗费用)。获得了求解上述问题的最优算法,证明了该问题是多项式时间可解的。     

Single-machine due window assignment and scheduling with a common flow allowance and controllable job processing time

In this paper, we consider single-machine due window assignment and scheduling with a common flow allowance and controllable job processing times, subject to unlimited or limited resource availability. Due window assignment with a common flow allowance means that each job has a job-dependent due window, the starting time and completion time of which are equal to its actual processing time plus the job-independent parameters q₁ and q₂, respectively, which are common to all the jobs. The processing time of each job is either a linear or a convex function of the amount of a common continuously divisible resource allocated to the job. We study five versions of the problem that differ in terms of the objective function and processing time function being used. We provide structural properties of the optimal schedules and polynomial-time solution algorithms for the considered problems.     

Job sequencing and due date assignment in a single machine shop with uncertain processing times

This paper considers due date assignment and sequencing for multiple jobs in a single machine shop. The processing time of each job is assumed to be uncertain and is characterized by a mean and a variance with no knowledge of the entire distribution. A heuristic procedure is developed to find job sequence and due date assignment to minimize a linear combination of three penalties: penalty on job earliness, penalty on job tardiness, and penalty associated with long due date assignment. Numerical experiments indicate that the performance of the procedure is stable and robust to job processing time distributions. In addition, the performance improves when the means and variances of job processing times are uncorrelated or negatively correlated or when the penalty of a long due date assignment is significant.     

Single machine common flow allowance scheduling with deteriorating jobs and a rate-modifying activity

We study a single machine slack due date assignment (usually referred to as SLK) scheduling problem with deteriorating jobs and a rate-modifying activity. The deterioration effect manifest such that the job processing time is a function of its starting time in a sequence. The rate-modifying activity is an activity that changes the processing rate of machine, i.e., the machine performs a rate-modifying activity. Hence the actual processing time of a job is a variable, which depends not only on its starting time in a sequence but also on whether it is scheduled before or after a rate-modifying activity. The goal is to schedule the rate-modifying activity, the optimal common flow allowance and the sequence of jobs to minimize the total earliness, the total tardiness and the common flow allowance cost. We show that the problem remains polynomially solvable under the proposed model.     

A faster algorithm for a due date assignment problem with tardy jobs

The single-machine due date assignment problem with the weighted number of tardy jobs objective, (the TWNTD problem), and its generalization with resource allocation decisions and controllable job processing times have been solved in O(n⁴) time by formulating and solving a series of assignment problems. In this note, a faster O(n²) dynamic programming algorithm is proposed for the TWNTD problem and for its controllable processing times generalization in the case of a convex resource consumption function.     

Single machine SLK/DIF due window assignment problem with learning effect and deteriorating jobs

We study a single-machine scheduling and due window assignment problem, in which job processing times are defined by functions of their starting times (deteriorating effect) and positions in the sequence (learning effect). The problem is to determine the optimal due windows and the processing sequence simultaneously to minimize costs for earliness, tardiness, the window location, window size and makespan. We show that the problem remains polynomially solvable under the proposed model for two popular due window assignment methods: The slack due date assignment method (usually referred to as SLK) and the unrestricted due date assignment method (usually referred to as DIF).     

A unified approach for scheduling with convex resource consumption functions using positional penalties

We provide a unified model for solving single machine scheduling problems with controllable processing times in polynomial time using positional penalties. We show how this unified model can be useful in solving three different groups of scheduling problems. The first group includes four different due date assignment problems to minimize an objective function which includes costs for earliness, tardiness, due date assignment, makespan and total resource consumption. The second group includes three different due date assignment problems to minimize an objective function which includes the weighted number of tardy jobs, due date assignment costs, makespan and total resource consumption costs. The third group includes various scheduling problems which do not involve due date assignment decisions. We show that each of the problems from the first and the third groups can be reduced to a special case of our unified model and thus can be solved in O(n³)$O(n^3)$ time. Furthermore, we show how the unified model can be used repeatedly as a subroutine to solve all problems from the second group in O(n⁴)$O(n^4)$ time. In addition, we also show that faster algorithms exist for several special cases.     

不确定条件下双目标组批生产的交货期设置研究

交货期是调度方法的函数,因而具有不确定性.研究变批量、变批次、变生产能力下,单阶段、双目标有条件相容组批的交货期设置问题,将它转化为订单投放策略和调度模式研究.建立了一个基于目标的双目标订单投放策略数学模型.采用目标序列优先方法进行双目标求解,用两种调度模式求出区间值,进行最优交货期逼近.模式1:松弛掉产品加工约束条件,基于负荷考虑、给出离散生产模式下订单完工率最大的订单排序算法,算法综合考虑了任务紧急程度、可调度性、重要度和流程时间最短四个方面,得到区间的一个端点.模式2是有条件相容的启发式组批调度算法,即通过聚类计算将订单安排问题转化为多队列调度问题,将新来订单的投放转化为某个队列的插单和批量分割问题,不同队列中批的投产顺序由批中优先级最高的订单决定,并在能力约束下进行批量分割计算,得到区间的另一个端点,结合流程可靠性求出区间.实例证明,模式2的交货期设置小,订单完工率和生产率高.     

Processing-plus-wait due dates in single-machine scheduling

We study the problem of schedulingn jobs on a single machine. Each job is assigned a processing-plus-wait due date, which is an affine-linear function of its processing time. The objective is to minimize the symmetric earliness and tardiness costs. We analyze a combined decision model which includes computing both the optimal job sequence and optimal due date parameters. For the quadratic objective function, we propose a heuristic solution based on a bicriterion approach. Additionally, we provide computational results to compare this model with two simpler models. For the maximum objective function, we show that it is efficiently solved by the shortest processing time sequence.Part of this research was undertaken during a visit of the first author at the University of Manitobe, Canada in 1991. This visit was supported in part by the Natural Sciences and Engineering Research Council of Canada under Grant OPG0036424. The numerical results were obtained with the assistance of T. P. Lindenthal. The authors are thankful for his help.     

Single-machine scheduling with convex resource dependent processing times and deteriorating jobs

In this study, we consider scheduling problems with convex resource dependent processing times and deteriorating jobs, in which the processing time of a job is a function of its starting time and its convex resource allocation. The objective is to find the optimal sequence of jobs and the optimal convex resource allocation separately. This paper focus on the single-machine problems with objectives of minimizing a cost function containing makespan, total completion time, total absolute differences in completion times and total resource cost, and a cost function containing makespan, total waiting time, total absolute differences in waiting times and total resource cost. It shows that the problems remain polynomially solvable under the proposed model.     

Bi-criterion single-machine scheduling and due-window assignment with common flow allowances and resource-dependent processing times

This paper addresses single-machine scheduling and due-window assignment with common flow allowances and resource-dependent processing times. Due-window assignment with common flow allowances means that each job has a job-dependent due window, the start time and finish time of which are equal to its actual processing time plus individual job-independent parameters shared by all the jobs, respectively. The processing time of each job can be controlled by extra resource allocation as a linear function of the amount of a common continuously divisible resource allocated to the job. Two criteria are considered, where one criterion is an integrated cost consisting of job earliness, weighted number of tardy jobs, and due-window assignment cost, while the other criterion is the resource consumption cost. Four different models are considered for treating the two criteria. It is shown that the problem under the model where the two criteria are integrated into a single criterion is polynomially solvable, while the problems under the other three models are all NP-hard and an optimal solution procedure is developed for them. Two polynomially solvable cases are also identified and investigated. Finally, numerical studies with randomly generated instances are conducted to assess the performance of the proposed algorithms.     

Single machine scheduling problem with multiple due windows assignment in a group technology

We consider group scheduling problem on a single machine with multiple due windows assignment. Jobs are divided into groups in advance according to their processing similarities, and all jobs of the same group are required to be processed contiguously on the machine in order to achieve production efficiency and save time/money resource. A sequence-independent setup time precedes the processing of each group. The goal is to determine the optimal sequence for both groups and jobs, together with an optimal combination of the due windows assignment strategy so as to minimize the total of earliness, tardiness and due windows related costs. We give an \(O(n\log n)\) time algorithm for the problem.     

Fast algorithms for scheduling with learning effects and time-dependent processing times on a single machine

We consider scheduling problems with learning/deterioration effects and time-dependent processing times on a single machine, with or without due date assignment considerations. By reducing them to a special assignment problem on product matrices, we solve all these problems in near-linear time. This improves the time complexity of previous algorithms for some scheduling problems and establishes the fast polynomial solvability for several other problems.