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

ＩｎｔｒｏｄｕｃｔｉｏｎＴｈｅｓｃｈｅｄｕｌｉｎｇｔｈｅｏｒｙｉｓａｒａｐｉｄｌｙｄｅｖｅｌｏｐｉｎｇｂｒａｎｃｈａｎｄｆｒｅｑｕｅｎｔｌｙｕｓｅｄｉｎｔｈｅｆｉｅｌｄｓｏｆｍａｎａｇｅｍｅｎｔｓｃｉｅｎｃｅｏｆｉｎｔｅｒｎａｔｉｏｎａｌｅｘｃｈａｎ...

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.

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.

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

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

具有位置相关权重的工期分配排序问题研究

针对具有位置相关权重的工期分配排序问题进行了研究,其目标是在共同工期分配/松弛工期分配两种模式下,找到最优的工件加工序列以极小化工件工期与工件延误的线性加权和,其中权重是与位置相关的权重。通过证明一系列性质得到工期的计算方法,进而将所要研究的两类工期分配问题转换为与工件加工时间有关的函数。根据每个工件对应的系数来给出具体求解算法从而得到最优的工件序列,以及对应的最优共同工期/最优松弛工期。通过具体的算例验证了此算法可在多项式时间内求解。

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.

考虑交货期的双资源柔性作业车间节能调度

为解决含有机器和工人双资源约束的柔性作业车间节能调度问题,在考虑交货期的基础上,建立了以总提前和拖期惩罚值及总能耗最小为目标的双资源柔性作业车间节能调度模型。提出了一种改进的非支配排序遗传算法(improved non-dominated sorting genetic algorithmⅡ,INSGA-Ⅱ)进行求解。针对所优化的目标,设计了一种三阶段解码方法以获得高质量的可行解;利用动态自适应交叉和变异算子以获得更多优良个体;改进拥挤距离以获得收敛性和分布性更优的种群。将INSGA-Ⅱ与多种多目标优化算法进行对比分析,实验结果表明所提算法可行且有效。

异构边缘资源的任务卸载和协同调度

边缘计算广泛应用于物联网、车联网和在线游戏等新兴领域,通过网络边缘部署计算资源为终端设备提供低延迟计算服务.针对如何进行任务卸载以权衡任务执行时间与传输时间、如何调度多个不同截止期任务以最小化总延迟时间等挑战性问题,提出1种异构边缘协同的任务卸载和调度框架,包括边缘网络拓扑节点排序、边缘节点内任务排序、任务卸载策略、任务调度和结果调优等算法组件;设计多种任务卸载策略和任务调度策略;借助多因素方差分析(multi-factor analysis of variance,ANOVA)技术在大规模随机实例上校正算法算子和参数,得到统计意义上的最佳调度算法.基于EdgeCloudSim仿真平台,将所提出调度算法与其3个变种算法从边缘节点数量、任务数量、任务分布、截止期取值区间等角度进行性能比较.实验结果表明,所提出调度算法在各种情形下性能都优于对比算法.

考虑加班的无拖期作业车间调度问题多目标金鹰优化算法研究

按期交货是面向订单型制造企业生产运作所追求的重要目标之一。当制造系统生产负荷较重时,加班作业是保证交货期最常采用的有效措施。为实现订单的无拖期交付和加班时间的合理优化使用,以面向订单型制造系统为背景,提出了一种考虑加班的多目标无拖期作业车间调度问题,建立了以最小化总加班时间和最大完工时间为目标的数学规划模型。为有效求解该问题,提出了一种多目标金鹰优化算法。在算法中设计了连续解空间映射至问题离散解空间的编码方法;提出了两阶段解码方案;融入了基于精英保留策略的非支配排序选择算子;引入了自适应子代个体生成策略。以23个作业车间调度问题基准算例为实验对象进行了对比实验,实验结果验证了所提出算法的有效性和优越性。

基于多智能体强化学习的纺织面料染色车间动态调度方法

针对任务随订单动态到达环境下的纺织面料染色车间动态调度问题,以最小化总拖期时间为优化目标,提出了基于多智能体循环近端策略优化(MA-RPPO)强化学习的完全反应式调度方法。首先,针对染色车间调度的组批和排缸两个子问题,设计了组批和排缸两个强化学习智能体;然后,针对车间任务的动态性,引入长短期记忆网络(LSTM)提取车间动态信息,提高智能体对动态环境的自适应能力;进一步提出组批智能体和排缸智能体的交互机制,实现组批与排缸全局优化;最后,抽取问题约束与优化目标的相关特征并设计奖励函数,通过动态调度机制驱动智能体的交互学习获得最优调度策略。经某印染企业的实例验证表明,所提方法对不同规模问题的求解性能均优于多种常用的高性能启发式规则,有效降低了产品的总拖期时间,提升了企业订单的准时交付能力。

考虑交通拥塞时变特性的预制构件生产调度与装车组合集成优化

生产调度、装车组合与交通拥塞是影响预制构件制造企业生产运营效率及成本的重要主客观因素,如何在考虑交通拥塞时变特性的情况下有效集成生产调度与工件装车组合方案是预制构件制造企业迫切需要解决的问题。针对该集成优化问题,首先以最小化总提前拖期惩罚和车辆运输费用之和为目标,建立了预制构件生产调度与工件装车组合集成优化数学模型。随后为降低问题求解困难,通过深入分析问题解结构特点,提出了一种基于自适应多邻域协同搜索的果蝇优化算法(AMNCS-FOA)。其主要特点是:设计了一种带有插零操作的集成决策编码方式用于表示生产调度和工件装车组合方案;在算法的嗅觉搜索阶段,基于组内交换、组间交换、组内插入和组间插入四种邻域构造,提出了一种自适应概率邻域选择策略;在视觉搜索阶段,为提高算法全局搜索能力,以一定概率接受劣解作为种群中心进一步执行迭代搜索。计算结果显示,AMNCS-FOA算法在求解该集成优化问题时具有更快的收敛速度以及更好的求解质量。与预制构件制造企业常用的规则启发式方法相比,提出算法在求解质量上具有不低于13%的平均改进率,有望显著增加预制构件企业净利润并提高客户满意度。