工件具有子工件工期的排序问题

研究了工件具有子工件工期的排序问题.需要在一台单机上加工若干个给定的工件.每个工件由若干个子工件组成,每个子工件都有各自的工期.只有当工件的每个子工件都按时完成,才能称该工件是按时完工工件,否则,称该工件产生延误.目标是最大化按时完工的工件个数.证明当每个工件都被分成两个子工件时,该问题是NP-难的,而且不存在完全多项式时间近似方案(fully polynomial time approximation scheme,简记为FPTAS).提出两个启发式算法,利用数值模拟比较它们的性能,并且将这两个启发式算法的解与最优解的上界进行比较.     

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.     

Asymmetric Earliness and Tardiness Scheduling with Exponential Processing Times on an Unreliable Machine

We address the problem of processing a set of jobs on a single machine under random due dates with a common distribution. The processing times of the jobs are exponentially distributed random variables with means _i , and the machine is subject to stochastic breakdowns governed by a Poisson process. Each job i is associated with a job-dependent weight w _i . The objective is to schedule the jobs so as to minimize the expected sum of the weighted earliness and tardiness costs of all jobs, which are quadratic functions of the deviations of job completion times from the due dates. We show that the problem is NP-complete. Nevertheless, important optimality properties exist, which can be utilized to develop effective algorithms to solve the problem. Specifically, we prove that, in the case where the weights assigned to both the earliness and tardiness are symmetric, an optimal sequence for the problem must be V-shaped with respect to { _i /w _i }, in the sense that the sequence will first process jobs in a nonincreasing order of { _i /w _i } and then in a nondecreasing order of { _i /w _i }. In the case where asymmetric weights are assigned to the earliness and tardiness costs, the optimal sequence must also be V-shaped with respect to { _i /w _i }, if the due dates are exponentially distributed. Dynamic programming algorithms are proposed which can find the best V-shaped sequences.     

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.     

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.     

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.     

Single Machine Scheduling of Unit-time Jobs with Controllable Release Dates

The paper presents a bicriterion approach to solve the single-machine scheduling problem in which the job release dates can be compressed while incurring additional costs. The two criteria are the makespan and the compression cost. For the case of equal job processing times, an O(n⁴) algorithm is developed to construct integer Pareto optimal points. We discuss how the algorithm developed can be modified to construct an -approximation of noninteger Pareto optimal points. The complexity status of the problem with total weighted completion time criterion is also established.     

Single-machine scheduling with waiting-time-dependent due dates

We consider a single-machine scheduling problem in which due dates are linear functions of the job waiting-times and the objective is to minimize the maximum lateness. An optimal sequence is constructed by implementing an index-based priority rule for a fixed value of the due date normalizing constant k. We determine in polynomial time all the k value ranges so that the optimal sequence remains the same within each range. The optimal due dates are computed as linear functions of the global optimal value of k. The overall procedure is illustrated in a numerical example.     

单机排序中带可分配工期的总误工问题的应急管理

对于机器排序的应急管理问题,Qi Xiang-tong等人进行了系统分析,得出了较好的结果.此文则考虑带可分配工期的总误工问题的应急管理问题.对于不同模型,或给出其最优序,或给出其近似解.     

Single-machine scheduling against due dates with past-sequence-dependent setup times

Recently Koulamas and Kyparisis [Koulamas, C., Kyparisis, G.J., in press. Single-machine scheduling with past-sequence-dependent setup times. European Journal of Operational Research] introduced past-sequence-dependent setup times to scheduling problems. This means that the setup time of a job is proportionate to the sum of processing times of the jobs already scheduled. Koulamas and Kyparisis [Koulamas, C., Kyparisis, G.J., in press. Single-machine scheduling with past-sequence-dependent setup times. European Journal of Operational Research] were able to show for a number of single-machine scheduling problems with completion time goals that they remain polynomially solvable. In this paper we extend the analysis to problems with due dates. We demonstrated that some problems remain polynomially solvable. However, for some other problems well-known polynomially solution approaches do not guarantee optimality any longer. Consequently we concentrated on finding polynomially solvable special cases.     

Single-machine scheduling with linear decreasing deterioration to minimize earliness penalties

We consider a single-machine scheduling problem with linear decreasing deterioration in which the due dates are determined by the equal slack (SLK) method. By the linear decreasing deterioration, we mean that the job’s processing time is a decreasing function of its starting time. The objective is to minimize the total weighted earliness penalty subject to no tardy jobs. We prove that two special cases of the problem remain polynomially solvable. The first case is the problem with equally weighted monotonous penalty objective function and the other case is the problem with weighted linear penalty objective function.     

优化交货期窗口的两阶段供应链排序问题

研究一类优化交货期窗口的两阶段供应链排序问题. 优化交货期窗口是指交货期窗口的开始与结束时刻是决策变量, 不是输入常量. 两阶段是指工件先加工, 后运输: 加工阶段是一台加工机器逐个加工工件;运输阶段是无限台车辆分批运输完工的工件. 工件的开始运输时刻与完工时刻之差定义为工件的储存时间, 且有相应的储存费用. 若工件的运输完成时刻早于(晚于)交货期窗口的开始(结束)时刻, 则有相应的提前(延误)惩罚费用. 目标是极小化总提前惩罚费用、总延误惩罚费用、总储存费用、总运输费用以及与交货期窗口有关的费用之和. 针对单位时间的延误惩罚费用不超过单位时间的储存费用、单位时间的储存费用不超过单位时间的提前惩罚费用的情形, 给出了时间复杂性为O(n^{8})的动态规划算法.     

Heuristic Approaches for a Scheduling Problem in the Plastic Molding Department of an Audio Company

A production scheduling problem for making plastic molds of hi-fi models is considered. The objective is to minimize the total machine makespan in the presence of due dates, variable lot size, multiple machine types, sequence dependent, machine dependent setup times, and inventory limits. Goal programming and load balancing are applied to select the set of machine types and assign mold types to machines, resulting in a set of single-machine scheduling problems. A mixed-integer program (MIP) is formulated for the general problem but could solve only small instances. A single-machine scheduling heuristic is designed to adopt a production sequence from a travelling salesman solution. The start time of every cycle is determined by a simplified MIP. Production cycles are defined to equalize the stockout times of mold types. A post-processing step reduces the number of setups in the last cycle. Results using real-life data are promising. Characteristics giving rise to high machine utilization are discussed.     

Optimal assignment of NOP due-dates and sequencing in a single machine shop

We consider the problem of optimal assignment of NOP due-dates ton jobs and sequencing them on a single machine to minimize a penalty function depending on the values of assigned constant waiting allowance and maximum job tardiness. It is shown that the earliest due date (EDD) order is an optimal sequence. For finding optimal constant waiting allowance, we reduce the problem to a multiple objective piecewise linear programming with single variable. An efficient algorithm for optimal solution of the problem is given.     

一个非常规目标函数的单机随机调度的最优策略

本文考虑了n个工件在同一台机器上加工的调度问题 ,其中工件的加工时间和交货期都是具有任意分布的随机变量 .我们考虑了一个非常规目标函数 ,其中工件的权数与平均加工时间成比例 .在工件的交货期与加工时间满足相容条件下 ,得到了个简单的最优排序策略 .     

A novel ant colony optimization approach for on-line scheduling and due date determination

This paper aims to develop an on-line Ant Colony Optimization (ACO) framework, where jobs arrive over time, and at any time we lack knowledge concerning future jobs. A due date is determined upon job arrival, and jobs are sequenced on the machine to optimize the sum of weighted lead times with all due dates met. We propose that each ant is associated with a sequence of waiting jobs with quoted due dates. This waiting sequence is constantly updated over time (whenever a job is selected to be processed or a new job arrives). The on-line schedule is constructed by selecting the first job in the waiting list of the “best” ant to process (along with its due date) as the machine becomes available. However, for the ant where this job is not the first one in the list, processing it pushes back the waiting jobs positioned before it. If such push back results in a due date violation, this ant will be eliminated. Further, our ACO framework does not include the iterative procedure due to the characteristics of the on-line problem; this is one difference from the traditional ACO framework besides ant elimination. The computational testing on generated instances shows that our ACO algorithm outperforms an existing effective on-line algorithm in the literature. Also, with local search incorporated using the EDD (Earliest Due Date) rule, improvements can be obtained in both computational outcome and time.     

主次指标为最小化总完工时间和存储费用的带有准备时间的单机分批排序问题

In this paper, the single machine scheduling problem with release dates and two hierarchical criteria is discussed. The first criterion is to minimize makespan, and the second criterion is to minimize stocking cost. We show that this problem is strongly NP-hard. We also give an O(n2) time algorithm for the special case that all stocking costs of jobs in unit time are 1.     

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.     

Scheduling with agreeable release times and due dates on a batch processing machine

We consider the problem of scheduling semiconductor burn-in operations, where burn-in ovens are modeled as batch processing machines. The job release times and due dates are assumed to be agreeable. Two different objective functions are considered: minimize the maximum tardiness and minimize the number of tardy jobs. We study the complexity of the problems. Efficient algorithms are also provided for the case when the job release times, due dates, and processing times are agreeable, which generalize those provided by Lee, Uzsoy and Martin-Vega (1992).     

带交货期的工件族生产与配送的排序问题

本文考虑了多个客户订购不同种类的工件,工件生产完后需要运输到客户的单机供应链排序问题.由于工件属于不同的种类,在加工不同种类工件前要有一个准备时间.每个客户分布在不同位置,客户的每个工件都有一个交货期,工件是分批配送的,每一批配送需要花费一定的时间及费用.考虑了两个与交货期有关的目标函数,分别给出了它们的最优算法.