Scheduling problems on tardiness penalty and earliness award with simply linear processing time

In this paper, a single-machine scheduling model with a given common due date and simple linear processing times was considered. The objective is the total weighted tardiness penalty and earliness award. Some polynomial time solvable cases for this problem are given. A dynamic programming algorithm was provided and a branch and bound algorithm for general case of the problem was provided based on a rapid method for estimating the lower bound.

A dynamic programming algorithm for scheduling problems on earliness award and tardiness penalty with time-dependent processing time

In this paper, a single-machine scheduling model with a given common due date is considered. Job processing time is a linear decreasing function of its starting time. The objective function is to minimize the total weighted earliness award and tardiness penalty. Our aim is to find an optimal schedule so as to minimize the objective function. As the problem is NP-hard, some properties and polynomial time solvable cases of this problem are given. A dynamic programming algorithm for the general case of the problem is provided.

Combined Timetabling Procedure and Complete Local Search for No-Wait Job Shop Scheduling with Total Tardiness

The strong non-deterministic polynomial-hard( NP-hard)character of job shop scheduling problem( JSSP) has been acknowledged widely and it becomes stronger when attaches the nowait constraint,which widely exists in many production processes,such as chemistry process, metallurgical process. However,compared with the massive research on traditional job shop problem,little attention has been paid on the no-wait constraint.Therefore,in this paper, we have dealt with this problem by decomposing it into two sub-problems, the timetabling and sequencing problems,in traditional frame work. A new efficient combined non-order timetabling method,coordinated with objective of total tardiness,is proposed for the timetabling problems. As for the sequencing one,we have presented a modified complete local search with memory combined by crossover operator and distance counting. The entire algorithm was tested on well-known benchmark problems and compared with several existing algorithms.Computational experiments showed that our proposed algorithm performed both effectively and efficiently.

Robust single machine scheduling problem with uncertain job due dates for industrial mass production

The single machine scheduling problem which involves uncertain job due dates is one of the most important issues in the real make-to-order environment. To deal with the uncertainty, this paper establishes a robust optimization model by minimizing the maximum tardiness in the worst case scenario over all jobs. Unlike the traditional stochastic programming model which requires exact distributions, our model only needs the information of due date intervals. The worst case scenario for a given sequence that belongs to a set containing only n scenarios is proved, where n is the number of jobs. Then, the model is simplified and reformulated as an equivalent mixed 0-1 integer linear programming(MILP) problem. To solve the MILP problems efficiently, a heuristic approach is proposed based on a robust dominance rule. The experimental results show that the proposed method has the advantages of robustness and high calculating efficiency, and it is feasible for large-scale problems.

Scatter Search Based Particle Swarm Optimization Algorithm for Earliness/Tardiness Flowshop Scheduling with Uncertainty

Considering the imprecise nature of the data in real-world problems, the earliness/tardiness （E/T） fiowshop scheduling problem with uncertain processing time and distinct due windows is concerned in this paper. A fuzzy scheduling model is established and then transformed into a deterministic one by employing the method of maximizing the membership function of middle value. Moreover, an effective scatter search based particle swarm optimization （SSPSO） algorithm is proposed to minimize the sum of total earliness and tardiness penalties. The proposed SSPSO algorithm incorporates the scatter search （SS） algorithm into the frame of particle swarm optimization （PSO） algorithm and gives full play to their characteristics of fast convergence and high diversity. Besides, a differential evolution （DE） scheme is used to generate solutions in the SS. In addition, the dynamic update strategy and critical conditions are adopted to improve the performance of SSPSO. The simulation results indicate the superiority of SSPSO in terms of effectiveness and efficiency.

No-Wait Flowshops to Minimize Total Tardiness with Setup Times

The m-machine no-wait flowshop scheduling problem is addressed where setup times are treated as separate from processing times. The objective is to minimize total tardiness. Different dispatching rules have been investigated and three were found to be superior. Two heuristics, a simulated annealing (SA) and a genetic algorithm (GA), have been proposed by using the best performing dispatching rule as the initial solution for SA, and the three superior dispatching rules as part of the initial population for GA. Moreover, improved versions of SA and GA are proposed using an insertion algorithm. Extensive computational experiments reveal that the improved versions of SA and GA perform about 95% better than SA and GA. The improved version of GA outperforms the improved version of SA by about 3.5%.

Genetic Algorithm for Scheduling Problem of Chemical Batch Process with Due Date Constraints

The intense competition in the current marketplace ha s forced firms to reexamine their methods of doing business, using superior manu facturing practices in the form of just-in-time (JIT), production with JIT pra ctices pursue completion on time and zero inventory, which is often instruct ed according to the custom’s demand or the sale contract. Earliness and tardine ss are undesirable because both of them will bring the extra cost, cost will als o be increased by some factors such as operation condition, intermediate storage , clean method, etc, to minimize the total cost is often the main scheduling objective, but sometime it is most important for factories to eliminate the tar diness cost in order to maintain the commercial credit and to avoid penalty, the refore, minimum of tardiness cost becomes the first objective. It is more import ant to select a reasonable objective by the actual condition during scheduli ng. In this paper scheduling problem of chemical batch process with due date is studied, two different intermediate storage policies and two different productio n modes are also discussed, production scheduling with different intermediate st orage policy and different production mode is proposed and the result is compare d. In order to complete all products within the due date, not only earliness and tardiness but also holding problem is considered, the objective is to selec t a proper intermediate storage policy and production mode and to minimize the c ost resulted by the earliness and tardiness, even the cost result by the interme diate storage. Scheduling with multiple stage and multiple machine is known as a NP-hard problem, mathematical program (MP) method, such as branch-and-bound (BAB), mixed integer linear program (MILP), etc, is often used to solve the sche duling problem. But as is well known, MP method is not good for combination opti mization, especially for large scale and complex optimal problem, whereas geneti c algorithm (GA) can overcome the MP method’s shortcoming and is fit for solvin g such scheduling problem. In this paper a modified genetic algorithm with speci al crossover operator and mutation operator is presented to solve this schedulin g problem. The results show such problem can be solved effectively with the pres ented method.

Number of Tardy Jobs of Single Machine Scheduling Problem with Variable Processing Time

The number of tardy jobs of the single machine scheduling problem with a variable processing time is studied in accordance with the published instances of traffic transportation management engineering. It is proved by 3 partition problem that if the problem is of ready time and common deadline constrained, its complexity is NP hard in the strong sense. Finally, a polynomial algorithm for solving unit processing time and common deadline problems is proposed.

A Heuristic for the Job Scheduling Problem with a Common Due Window on Parallel and Non-Identical Machines

In this paper, we give a mathematical model for earliness-tardiness job scheduling problem with a common due window on parallel and non-identical machines. Because the job scheduling problem discussed in the paper contains a problem of minimizing make-span, which is NP-complete on parallel and uniform machines, a heuristic algorithm is presented to find an approximate solution for the scheduling problem after proving an important theorem. Two numerical examples illustrate that the heuristic algorithm is very useful and effective in obtaining the near-optimal solution.

Minimizing Tardy Jobs in a Single Machine Scheduling Problem with Fuzzy Processing Times and Due Dates

The optimality of a fuzzy logic alternative to the usual treatment of uncertainties in a scheduling system using fuzzy numbers is examined formally. Processing times and due dates are fuzzified and presented by fuzzy numbers. With introducing the necessity measure, we compare fuzzy completion times of jobs with fuzzy due dates to decide whether jobs are tardy. The object is to minimize the numbers of tardy jobs. The efficient solution method for this problem is proposed. And deterministic counterpart of this single machine scheduling problem is a special case of fuzzy version.

A Note on Single-Machine Lot Scheduling with Splittable Jobs to Minimize the Number of Tardy Jobs

The single-machine lot scheduling problem with splittable jobs to minimize the number of tardy jobs has been showed to be weakly NP-hard in the literature.In this paper,we show that a generalized version of this problem in which jobs have deadlines is strongly NP-hard,and also present the results of some related scheduling problems.

An Approximation Algorithm for the Common Due Date Scheduling Problem

In this paper,attention is paid to study an algorithm for the common due datetotal weighted tardiness problem of single machine scheduling. Anapproximation alsorithm is given. It performs well in the sense of worst-casebehaviour and its worst-case performance ratio is 2.

Simulated Annealing for Earliness/Tardiness Production Planning Model

To describe the earliness/tardiness production planning problems in the JIT environment, a nonlinear semi\|infinite programming model was proposed in \. Due to a nonconvex objective function and many infinite constraints, the model is difficult to be solved by traditional methods. In this paper, simulated annealing method combined with a heuristic is developed. Numerical results shows that the present approach is very efficient. Theoretically, the developed method is an attempt to solve a continuous domain problem by using simulated annealing.

THE SINGLE MACHINE STOCHASTIC SCHEDULING WITH THE WEIGHTED JOB TARDINESS MINIMIZATION

This paper considers scheduling n jobs on a single machine where the job processing times anddue dates are independent random variables with arbitrary distribution functions.We consider the casethat the weighted job tardiness in expectation is minimized.It is assumed that job's due dates arecompatible with processing times and weights.We show that the jobs should be sequenced indecreasing stochastic order of their due dates.

基于位置权重的窗口指派单机排序问题

研究了基于位置权重的窗口指派排序问题,机器限定为一台,其目的是在准时制环境下极小化窗口指派的窗口开始时间、窗口大小以及总延误的加权之和,以找到其最优工件加工序列以及窗口开始时间d_(k)^(1)(结束时间d_(k)^(2)),其中权重只和位置有关,而与工件无关。在共同、松弛和不同窗口指派下,通过相应最优解性质,证明此问题能够多项式时间可解。对于共同以及松弛窗口指派,算法的复杂度为O(n^(2)log n),而对不同窗口指派,问题可在O(n log n)时间内求解,其中n为给定工件数量。

具有等间隔工期的2台机器流水作业调度问题的强NP难性

考虑3个具有等间隔工期的双机流水作业调度问题,其中按照调度方案中工件的加工顺序给每个工期分配工件,且2个连续工期之间的间隔长度相同,目标分别为最小化最大延误、总延误和总误工工件数。证明了此三问题均为强NP-难的。此外,结果表明,如果P≠NP,那么这些问题没有伪多项式时间算法和完全多项式时间近似方案(FPTAS)。

基于灰数描述的不确定工时作业车间E/T调度优化

针对不确定加工时间的作业车间调度问题,考虑每个工件的交货期窗口,旨在最小化工件提前/拖期成本和机器空闲成本。分别采用基本遗传算法和混合遗传算法进行求解,并比较两种算法的求解质量。通过灰色理论和模糊数理论对不确定加工时间分别建立调度模型,分析两种模型的优化程度和稳定性。结果表明,与基本遗传算法相比,引入按指定邻域结构进行局部搜索的混合遗传算法具有更好收敛能力;与模糊数方式相比,采用灰色理论能够更好地描述不确定加工时间,且在求解过程中也具有更好的适应性和稳定性。

Minmax Common Due-Window Assignment Scheduling with Deteriorating Jobs

This paper investigates the common due-window assignment scheduling problem with deteriorating jobs on a single machine in which the processing time of a job is a proportional function of its starting time.The goal is to minimize the maximum value of earliness and tardiness penalties,as well as due-window location cost,and size cost.Depending on whether the location and size of due-window are known,this paper studies three relevant cases,all of which are solvable in polynomial time.

基于多阶段调度框架的麻雀搜索优化算法

本文提出一种多阶段调度框架,实现对麻雀种群的初始位置、觅食、侦查与反捕食不同阶段的多策略调度.利用Halton序列与Tent映射提升种群个体质量与初始位置的分布均匀性.在觅食阶段,针对发现者与加入者因位置争夺导致种群质量劣化,设计最佳适配比调控二者数量关系,对超出适配比的加入者采用碰撞反弹算子改变其优化轨迹.满足适配比后则通过侦查判断是否存在天敌,若有则进入反捕食阶段,并利用Levy飞行并结合指数分布设计随机迁移机制,生成潜在的全局最优解区域;当连续多次没有发现天敌时为避免种群陷入局部极值,建立模拟预警机制并采用蝗虫算法进行多路径开发,避免寻优方向单一化.不同策略与机制的交替运行、协同调度,平衡了算法的多样性与收敛性.实验结果表明,与最近麻雀变体算法和元启发改进算法相比,该算法在寻优效率与收敛精度上显著优于对比方法.

Improved Approximation Schemes for Early Work Scheduling on Identical Parallel Machines with a Common Due Date

We study the early work scheduling problem on identical parallel machines in order to maximize the total early work,i.e.,the parts of non-preemptive jobs that are executed before a common due date.By preprocessing and constructing an auxiliary instance which has several good properties,for any desired accuracy,we propose an efficient polynomial time approximation scheme with running time O(f(1/ε)n),where n is the number of jobs and f(1/ε)is exponential in 1/ε,and a fully polynomial time approximation scheme with running time O(1/ε^(2m+1)+n)when the number of machines is fixed.