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.     

Optimal due-date assignment problem with learning effect and resource-dependent processing times

In this paper, we consider a single-machine earliness-tardiness scheduling problem with due-date assignment, in which the processing time of a job is a function of its position in a sequence and its resource allocation. The due date assignment methods studied include the common due date, and the slack due date, which reflects equal waiting time allowance for the jobs. For each combination of due date assignment method and processing time function, we provide a polynomial-time algorithm to find the optimal job sequence, due date values, and resource allocations that minimize an integrated objective function, which includes earliness, tardiness, due date assignment, and total resource consumption costs.     

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

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

Scheduling in a two-machine flowshop with batch processing machine(s) for earliness/tardiness measure under a common due date

This paper considers a scheduling problem for a two-machine flowshop with batch processing machine(s) (BPMs) incorporated where the earliness/tardiness (E/T) measure and a common due date are considered. It assumes that each batch has the same processing time and that the common due date is not set earlier than the total job processing time on the first machine. Under these assumptions, some solution properties are characterized for three different problem cases to derive their associated solution algorithms. For the first two cases concerned with two different machine sequences such as batch-to-discrete and batch-to-batch machine sequences, a polynomial time algorithm is derived based on some of the solution properties. For the last case concerned with discrete-to-batch machine sequence, a pseudopolynomial algorithm is exploited.     

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.     

Minimizing due date related performance measures on two batch processing machines

This paper considers a scheduling problem in a two-machine flowshop of two batch processing machines. On each batch processing machine, jobs are processed in a batch, and each batch is allowed to contain jobs up to the maximum capacity of the associated machine. The scheduling problem is analyzed with respect to three due date related objectives including maximum tardiness, number of tardy jobs and total tardiness. In the analysis, several solution properties are characterized and based upon these properties, three efficient polynomial time algorithms are developed for minimizing the due date related measures.     

Scheduling with batch setup times and earliness-tardiness penalties

We consider a scheduling model in which several batches of jobs need to be processed by a single machine. During processing, a setup time is incurred whenever there is a switch from processing a job in one batch to a job in another batch. All the jobs in the same batch have a common due date that is either externally given as an input data or internally determined as a decision variable. Two problems are investigated. One problem is to minimize the total earliness and tardiness penalties provided that each due date is externally given. We show that this problem is NP-hard even when there are only two batches of jobs and the two due dates are unrestrictively large. The other problem is to minimize the total earliness and tardiness penalties plus the total due date penalty provided that each due date is a decision variable. We give some optimality properties for this problem with the general case and propose a polynomial dynamic programming algorithm for solving this problem with two batches of jobs. We also consider a special case for both of the problems when the common due dates for different batches are all equal. Under this special case, we give a dynamic programming algorithm for solving the first problem with an unrestrictively large due date and for solving the second problem. This algorithm has a running time polynomial in the number of jobs but exponential in the number of batches.     

加工时间是开工时间线性分段函数的单机总误工问题

研究工件加工时间是开工时间的线性分段函数的单机排序问题,其中工件的加工时间是开工时间的线性增加函数,但是有一个上界,在时刻T(T是已知常数)以后开始加工的工件,其加工时间不再因开工时间的推迟而增大,优化的目标是极小化总误工工件数.当工件的工期与加工时间满足某种一致性关系的时候,不管工件的加工时间是开工时间的简单线性分段函数,还是其基本加工时间是与恶化率有关的分段线性函数,证明这两种情况都是多项式时间可解的.     

Optimization of setup times in the furniture industry

The aim of this paper is to develop a scheduling policy oriented towards minimizing setup times in the made-to-order furniture industry. The task is treated as a dynamic job shop scheduling problem, with the exception that customers?? orders collected over a?specified period of time are combined into a?production plan and released together. A?simulation of a production flow based on technological routes of real subassemblies was performed. The proposed method of calculating a setup time eliminates the need to determine machine setup time matrices. Among the tested priority rules the best performance was observed in the case of the hierarchical rule that combines similar setup, the earliest due date and the shortest processing time. This rule allowed the setup time per operation to be reduced by 58?% compared to a combination of the earliest due date with the shortest setup and processing time rule and by over 70?% compared to the single shortest processing time rule.     

单机最优交货期决策及工件排序

本文考虑n个独立工件在一台机器上加工的排序问题,每个工件J_i的交货期设置为d_i=kP_i~α(α≥1),目标是寻找工件最优加工时间乘子及工件最优排序S(?),使工件完工时间与交货期的最大偏差最小。给出寻找最优加工时间乘子k(?)及工件最优排序S(?)的方法。     

Scheduling unit processing time jobs on an <Emphasis Type="Italic">m</Emphasis>-machine flow-shop

The sequential production of identical jobs and the flow-shop machine setting are extremely common in real-life applications. We study a scheduling problem that combines these two elements: jobs of identical processing time, with job-dependent weights, and a given common due date processed on an m-machine flow-shop. The (just-in-time) objective is to minimize the maximum earliness/tardiness cost. We introduce a polynomial time solution in both cases of (i) a non-restrictive (ie, sufficiently large) due date, and (ii) a restrictive due date (which restricts the number of early jobs).     

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 Scheduling with Exponential Processing Times and General Stochastic Cost Functions

We study a single-machine stochastic scheduling problem with n jobs, in which each job has a random processing time and a general stochastic cost function which may include a random due date and weight. The processing times are exponentially distributed, whereas the stochastic cost functions and the due dates may follow any distributions. The objective is to minimize the expected sum of the cost functions. We prove that a sequence in an order based on the product of the rate of processing time with the expected cost function is optimal, and under certain conditions, a sequence with the weighted shortest expected processing time first (WSEPT) structure is optimal. We show that this generalizes previous known results to more general situations. Examples of applications to practical problems are also discussed.This work was partially supported by the Research Grants Council of Hong Kong under Earmarked Grants No. CUHK4418/99E and No. PolyU 5081/00E.     

Minimizing the weighted number of tardy jobs and maximum tardiness in relocation problem with due date constraints

The relocation problem addressed in this paper is to determine a reconstruction sequence for a set of old buildings, under a limited budget, such that there is adequate temporary space to house the residents decanted during rehabilitation. It can be regarded as a resource-constrained scheduling problem where there is a set of jobs to be processed on a single machine. Each job demands a number of resources for processing and returns probably a different number of resources on its completion. Given a number of initial resources, the problem seeks to determine if there is a feasible sequence for the successful processing of all the jobs. Two generalizations of the relocation problem in the context of single machine scheduling with due date constraints are studied in this paper. The first problem is to minimize the weighted number of tardy jobs under a common due date. We show that it is NP-hard even when all the jobs have the same tardy weight and the same resource requirement. A dynamic programming algorithm with pseudo-polynomial computational time is proposed for the general case. In the second problem, the objective is to minimize the maximum tardiness when each job is associated with an individual due date. We prove that it is strongly NP-hard. We also propose a pseudo-polynomial time dynamic programming algorithm for the case where the number of possible due dates is predetermined.     

An O(n) algorithm for the variable common due date,minimal tardy jobs bicriteria two-machine flow shop problem with ordered machines

We consider the ordinary NP- hard two-machine flow shop problem with the objective of determining simultaneously a minimal common due date and the minimal number of tardy jobs. We present an O(n²) algorithm for the problem when the machines are ordered, that is, when each job has its smaller processing time on the first (second) machine. We also discuss the applicability of the proposed algorithm to the corresponding single-objective problem in which the common due date is given.     

交货期可以指派的供应链排序问题

考虑了由一个制造商和多个客户组成的供应链系统.每个客户有多个订单交给制造商加工,且每个客户有一个可以接受的完工订单到达时间.制造商可以与客户进行协商来选定合适的交货期.完工的订单是采用直接运输方式分批配送的,每一批配送需要花费一定的时间和费用.目标是对每个订单指派合适的交货期,并且进行生产和配送的排序,以极小化总的交货期指派费用,订单误工费用与配送费用的和.考虑了多种情况,分别给出了相应的算法.     

Meta-heuristic approaches for minimizing total earliness and tardiness penalties of single-machine scheduling with a common due date

This study addresses a class of single-machine scheduling problems involving a common due date where the objective is to minimize the total job earliness and tardiness penalties. A genetic algorithm (GA) approach and a simulated annealing (SA) approach utilizing a greedy local search and three well-known properties in the area of common due date scheduling are developed. The developed algorithms enable the starting time of the first job not at zero and were tested using a set of benchmark problems. From the viewpoints of solution quality and computational expenses, the proposed approaches are efficient and effective for problems involving different numbers of jobs, as well as different processing time, and earliness and tardiness penalties.     

Dynamic Programming State-Space Relaxation for Single-Machine Scheduling

The problem of sequencing jobs on a single machine to minimize total cost is considered. Machine capacity constraints require that, at any time, at most one job is processed. Also, no machine idle-time between processing jobs is allowed. In contrast to most research, it is not assumed that the cost is a non-decreasing function of completion time. A dynamic programming formulation of the problem is presented. Since the number of states required by this formulation is prohibitively large, the possibilities for branch and bound algorithms are explored. It is shown that the dynamic programming formulation can be relaxed by mapping the state-space onto a smaller state-space and performing the recursion on this smaller state-space, thereby giving a lower bound. Techniques for improving this lower bound through the use of penalties and through the use of state-space modifiers are discussed. Computational results are presented for the problem in which each job has a due date, and the objective is to minimize the sum of holding costs for jobs completed before their due date and tardiness costs for jobs completed after their due date.     

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

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

极大化提前完工总量平行机排序问题的LPT算法

研究带有共同交货期的三台平行机排序问题。工件在加工过程中不允许中断, 目标是极大化所有工件的提前完工量, 即在交货期前所加工工件(或部分) 的总加工时长。由于该问题是NP-难问题, 本文应用经典LPT算法来解决该问题。我们证明了LPT算法求解该问题的最坏情况界至多为$\frac{15}{13}$, 并给出实例说明最坏情况界的下界为$\frac{27}{25}$。