Genetic algorithms for the optimal common due date assignment and the optimal scheduling policy in parallel machine earliness/tardiness scheduling problems

Earliness/tardiness scheduling problems with undetermined common due date which have wide application background in textile industry, mechanical industry, electronic industry and so on, are very important in the research fields such as industry engineering and CIMS. In this paper, a kind of genetic algorithm based on sectional code for minimizing the total cost of assignment of due date, earliness and tardiness in this kind of scheduling problem is proposed to determine the optimal common due date and the optimal scheduling policy for determining the job number and their processing order on each machine. Also, simulated annealing mechanism and the iterative heuristic fine-tuning operator are introduced into the genetic algorithm so as to construct three kinds of hybrid genetic algorithms with good performance. Numerical computational results focusing on the identical parallel machine scheduling problem and the general parallel machine scheduling problem shows that these algorithms outperform heuristic procedures, and fit for larger scale parallel machine earliness/tardiness scheduling problem. Moreover, with practical application data from one of the largest cotton colored weaving enterprises in China, numerical computational results show that these genetic algorithms are effective and robust, and that especially the performance of the hybrid genetic algorithm based on simulated annealing and the iterative heuristic fine-tuning operator is the best among them.     

解并行多机提前/拖后调度问题的并行遗传算法

为有效地解决带有公共交货期的非等同并行多机提前/拖后调度问题,设计了一种分段扩展排列编码的混合遗传算法,使遗传编码能同时反映调度方案和公共交货期,并对其初始种群产生、交叉和变异方法也进行了研究。同时为了更好地适应调度实时性和解大规模此类问题的需要,基于遗传算法自然并行性特点的基础上,实现了主从式控制网络模式下并行混合遗传算法。计算结果表明,此算法是有效的,优于启发式算法和遗传算法,有着较高的并行性,并能适用于大规模非等同并行多机提前/拖后调度问题。     

Optimization of Order Fulfillment in Distribution Network Problems

This paper focuses on optimization of order due date fulfillment reliability in multi-echelon distribution network problems with uncertainties present in the production lead time, transportation lead time, and due date of orders. Reliability regarding order due date fulfillment is critical in customer service, and customer retention. However, this reliability can be seriously influenced by supply chain uncertainties, which may induce tardiness in various stages throughout the supply chain. Supply chain uncertainty is inevitable, since most input values are predicted from historical data, and unexpected events may happen. Hence, a multi-criterion genetic integrative optimization methodology is developed for solving this problem. The proposed algorithm integrates genetic algorithms with analytic hierarchy process to enable multi-criterion optimization, and probabilistic analysis to capture uncertainties. The optimization involves determination of demand allocations in the network, transportation modes between facilities, and production scheduling in manufacturing plants. A hypothetical three-echelon distribution network is studied, and the computation results demonstrated the reliability of the proposed algorithms. Received: October 2004 / Accepted: September 2005     

解决并行多机提前/拖后调度问题的混合遗传算法方法

研究了带有公共交货期的并行多机提前/拖后调度问题.提出了一种混合遗传算法 方法,以便于确定公共交货期和每台机器上加工的任务代号及其加工顺序,即找到一个最优 公共交货期和最优调度,使加工完所有任务后交货期安排的成本、提前交货成本和拖后交货 成本的总和最小.数值计算结果表明了该混合遗传算法优于启发式算法,并能适用于较大规 模并行多机提前/拖后调度问题.算法计算量小,鲁棒性强.     

Common due date assignment and scheduling with ready times

We consider the problem of scheduling a set of nonsimultaneously available jobs on one machine. Each job has a ready time only at or after which the job can be processed. All the jobs have a common due date, which needs to be determined. The problem is to determine a due date and a schedule so as to minimize a total penalty depending on the earliness, tardiness and due date. We show that this problem is strongly NP-hard and give an efficient algorithm that finds an optimal due date and schedule when either the job sequence is predetermined or all jobs have the same processing time. We also propose three approximation algorithms for the general and special cases together with their experimental analysis.

Scope and purpose

We consider the single machine due date assignment problem for scheduling jobs which are ready for processing at different times. The problem under consideration arises in production planning and scheduling concerning the setting of appropriate due dates for a number of customer orders arriving over time. Most of the earlier publications on this subject assumed that the jobs are ready for processing simultaneously. This assumption is too restrictive for real-life production systems where jobs arrive at different times. We show that the problem with unequal ready times is NP-hard and develop fast heuristic algorithms for it, and exact algorithms for two special cases.     

交货期窗口下带有附加惩罚的单机提前/拖期调度问题

交货期窗口下的交货期确定和排序问题是调度领域研究的一个方面,本文对交货期口下的单机作业问题进行了研究,目标函数不仅考虑提前／拖期惩罚,还考虑附加惩罚,假设如果任务在交货期窗口内完工,则不受提前／拖期片罚;如果在交货期窗口外完工,将导致提前／拖期惩罚,本文确定了最优公共交货期,给出了相庆的最优排序,并提出了一个多项式时间算法确定了使目标函数为最小的最优调度,最后的数值例子说明了算法的有效性。     

A differential evolution approach for the common due date early/tardy job scheduling problem

The problem of scheduling multiple jobs on a single machine so that they are completed by a common specified date is addressed in this paper. This type of scheduling set costs depend on whether a job is finished before (earliness) or after (tardiness) the specified due date. The objective is to minimize a summation of earliness and tardiness penalty costs. Minimizing these costs pushes the completion time of each job as close as possible to the due date. The use of differential evolution as the optimization heuristic to solve this problem is investigated in this paper. Computational experiments over multiple (280 in total) public benchmark problems with up to 1000 jobs to be scheduled show the effectiveness of the proposed approach. The results obtained are of high quality putting new upper bounds to 60% of the benchmark instances.     

解不同交货期并行机调度问题的并行遗传算法

为有效地解决不同交货期窗口下的非等同并行多机提前/拖后调度问题,设计了一种分段编码的混合遗传算法。此编码方式能反映工件的分配序列,并利用调度优先级规则和最好适应值规则相结合的启发式算法对其顺序进行了调整,加快了收敛速度。同时为了更好地适应调度实时性和解大规模此类问题的需要,基于遗传算法自然并行性特点的基础上,实现了主从式控制网络模式下并行混合遗传算法。计算结果表明,此算法是有效的,优于遗传算法,有着较高的并行性,并能适用于大规模不同交货期窗口下非等同并行多机提前/拖后调度问题。     

Common due date assignment and scheduling with a rate-modifying activity to minimize the due date,earliness, tardiness,holding, and batch delivery cost

e consider a single-machine batch delivery scheduling and common due date assignment problem. In addition to making decisions on sequencing the jobs, determining the common due date, and scheduling job delivery, we consider the option of performing a rate-modifying activity on the machine. The processing time of a job scheduled after the rate-modifying activity decreases depending on a job-dependent factor. Finished jobs are delivered in batches. There is no capacity limit on each delivery batch, and the cost per batch delivery is fixed and independent of the number of jobs in the batch. The objective is to find a common due date for all the jobs, a location of the rate-modifying activity, and a delivery date for each job to minimize the sum of earliness, tardiness, holding, due date, and delivery cost. We provide some properties of the optimal schedule for the problem and present polynomial algorithms for some special cases.     

Intelligent controllers for bi-objective dynamic scheduling on a single machine with sequence-dependent setups

This article addresses the problem of dynamic job scheduling on a single machine with Poisson arrivals, stochastic processing times and due dates, in the presence of sequence-dependent setups. The objectives of minimizing mean earliness and mean tardiness are considered. Two approaches for dynamic scheduling are proposed, a Reinforcement Learning-based and one based on Fuzzy Logic and multi-objective evolutionary optimization. The performance of the two scheduling approaches is tested against the performance of 15 dispatching rules in four simulation scenarios with different workload and due date pressure conditions. The scheduling methods are compared in terms of Pareto optimal-oriented metrics, as well as in terms of minimizing mean earliness and mean tardiness independently. The experimental results demonstrate the merits of the proposed methods.     

A note: Common due date assignment for a single machine scheduling with the rate-modifying activity

In this paper we study the single machine common due date assignment and scheduling problem with the possibility to perform a rate-modifying activity (RMA) for changing the processing times of the jobs following this activity. The objective is to minimize the total weighted sum of earliness, tardiness and due date costs. Placing the RMA to some position in the schedule can decrease the objective function value. Several properties of the problem are considered which in some cases can reduce the complexity of the solution algorithm.     

解决单机准时调度问题的混合粒子群算法

针对共同交货期给定的单机准时调度问题,提出了一种混合粒子群优化（Hybrid Particle Swarm Optimization,HPSO）算法。该算法采用了工件排列和开工时间混合的粒子编码方式及新的粒子产生策略,非常适合于求解开工时间不为零的调度问题。为了提高算法性能,将HPSO分别与模拟退火算法、局部搜索算法和迭代的局部搜索算法相结合,得到了三种混合算法：HPSO1、HPSO2和HPSO3。基于典型算例的试验表明：三种算法在求解质量和求解效率两方面均优于Hino等人的研究成果。     

Single machine due-date scheduling of jobs with decreasing start-time dependent processing times

We study the problem of scheduling jobs whose processing times are decreasing functions of their starting times. We consider the case of a single machine and a common decreasing rate for the processing times. The problem is to determine an optimal combination of the due date and schedule so as to minimize the sum of due date, earliness and tardiness penalties. We give an O(n log n) time algorithm to solve this problem.     

一种新的遗传算法在并行机调度问题中的应用

针对相同交货期窗口非等同并行机提前/拖后调度问题,设计了一个基于向量组编码的遗传算法.此算法的编码方法简单,能有效地反映实际调度方案,收敛速度快.为适应调度实时性和解大型此类问题的需要,基于遗传算法自然并行性特点的基础上,实现了主从式控制网络模式下并行遗传算法.仿真结果表明,此算法是有效的,优于普通的遗传算法,具有较高的并行性.     

Minimization of earliness, tardiness and due date penalties on uniform parallel machines with identical jobs

We consider a problem of scheduling n identical nonpreemptive jobs with a common due date on m uniform parallel machines. The objective is to determine an optimal value of the due date and an optimal allocation of jobs onto machines so as to minimize a total cost function, which is the function of earliness, tardiness and due date values. For the problem under study, we establish a set of properties of an optimal solution and suggest a two-phase algorithm to tackle the problem. First, we limit the number of due dates one needs to consider in pursuit of optimality. Next, we provide a polynomial-time algorithm to build an optimal schedule for a fixed due date. The key result is an O(m² log m) algorithm that solves the main problem to optimality.Scope and purpose: To extend the existing research on cost minimization with earliness, tardiness and due date penalties to the case of uniform parallel machines.     

Trade-off solutions in a single-machine scheduling problem for minimizing total earliness and maximum tardiness

This paper considers a single-machine scheduling problem involving minimization of the total earliness and the maximum tardiness. Four dominant properties for the precedence relationship between jobs in a search for an optimal solution are proposed. The lower bounds of the total earliness and the maximum tardiness of a subproblem are derived. The dominance properties and the lower bounds are implemented in the branchand-bound algorithm to facilitate the search for an optimal schedule. A heuristic algorithm is then developed to overcome the inefficiency of the branch-and-bound algorithm. Computational performance of the two algorithms is also investigated.     

Exact and heuristic algorithms for the just-in-time scheduling problem in a batch processing system

Batch processing systems are commonly used in many different environments such as chemical and semiconductor industries. In this research, a just-in-time scheduling problem in a batch processing system is investigated. Minimization of total earliness and tardiness of the jobs with respect to a common due date is considered as the objective function. First, the research problem is formulated as a mixed integer linear programming model. Then, to find the optimal schedule for a predetermined set of batches, a dynamic programming algorithm is proposed. Based on the proposed dynamic programming algorithm, several heuristics are also developed. A lower bounding method is presented, and then a branch and bound algorithm is proposed to solve the problem optimally. To demonstrate the performance of the proposed algorithms, several computational experiments are conducted.     

Parallel machine earliness and tardiness scheduling with proportional weights

In this paper we study the problem of scheduling n jobs with a common due date and proportional early and tardy penalties on m identical parallel machines. We show that the problem is NP-hard and propose a dynamic programming algorithm to solve it. We also propose two heuristics to tackle the problem and analyze their worst-case error bounds.Scope and purposeScheduling problems to minimize the total weighted earliness and tardiness (WET) arise in Just-in-time manufacturing systems, where one of the objectives is to complete each job as close to its due date as possible. The earliness and tardiness weights of a job in WET tend to increase with the value of the job. Because processing time is often a good surrogate for the value of a job, it is reasonable to consider weights that are proportional to job processing times. In this paper we study the parallel identical machine WET problem with proportional weights. We propose both exact and approximation algorithms to tackle the problem.     

Earliness–tardiness minimization on scheduling a batch processing machine with non-identical job sizes

This paper considers the scheduling problem of minimizing earliness–tardiness (E/T) on a single batch processing machine with a common due date. The problem is extended to the environment of non-identical job sizes. First, a mathematical model is formulated, which is tested effectively under IBM ILOG CPLEX using the constraint programming solver. Then several optimal properties are given to schedule batches effectively, and by introducing the concept of ARB (Attribute Ratio of Batch), it is proven that the ARB of each batch should be made as small as possible in order to minimize the objective, designed as the heuristic information for assigning jobs into batches. Based on these properties, a heuristic algorithm MARB (Minimum Attribute Ratio of Batch) for batch forming is proposed, and a hybrid genetic algorithm is developed for the problem under study by combining GA (genetic algorithm) with MARB. Experimental results demonstrate that the proposed algorithm outperforms other algorithms in the literature, both for small and large problem instances.     

Dynamic scheduling of manufacturing job shops using genetic algorithms

Most job shop scheduling methods reported in the literature usually address the static scheduling problem. These methods do not consider multiple criteria, nor do they accommodate alternate resources to process a job operation. In this paper, a scheduling method based on genetic algorithms is developed and it addresses all the shortcomings mentioned above. The genetic algorithms approach is a schedule permutation approach that systematically permutes an initial pool of randomly generated schedules to return the best schedule found to date.A dynamic scheduling problem was designed to closely reflect a real job shop scheduling environment. Two performance measures, namely mean job tardiness and mean job cost, were used to demonstrate multiple criteria scheduling. To span a varied job shop environment, three factors were identified and varied between two levels each. The results of this extensive simulation study indicate that the genetic algorithms scheduling approach produces better scheduling performance in comparison to several common dispatching rules.