Single machine weighted earliness–tardiness penalty problem with a common due date

In this paper, we have considered a class of single machine job scheduling problems where the objective is to minimize the weighted sum of earliness–tardiness penalties of jobs. The weights are job-independent but they depend on whether a job is early or tardy. The restricted version of the problem where the common due date is smaller than a critical value, is known to be NP-complete. While dynamic programming formulation runs out of memory for large problem instances, depth-first branch-and-bound formulation runs slow for large problems since it uses a tree search space. In this paper, we have suggested an algorithm to optimally solve large instances of the restricted version of the problem. The algorithm uses a graph search space. Unlike dynamic programming, the algorithm can output optimal solutions even when available memory is limited. It has been found to run faster than dynamic programming and depth-first branch-and-bound formulations and can solve much larger instances of the problem in reasonable time. New upper and lower bounds have been proposed and used. Experimental findings are given in detail.Scope and purposeA class of single machine problems arising out of scheduling jobs in JIT environment has been considered in this paper. The objective is to minimize the total weighted earliness–tardiness penalties of jobs. In this paper, we have presented a new algorithm and conducted extensive empirical runs to show that the new algorithm performs much better than the existing approaches in solving large instances of the problem.     

A branch-and-bound algorithm for single machine scheduling with quadratic earliness and tardiness penalties

This paper considers the problem of scheduling a single machine, in which the objective function is to minimize the weighted quadratic earliness and tardiness penalties and no machine idle time is allowed. We develop a branch and bound algorithm involving the implementation of lower and upper bounding procedures as well as some dominance rules. The lower bound is designed based on a lagrangian relaxation method and the upper bound includes two phases, one for constructing initial schedules and the other for improving them. Computational experiments on a set of randomly generated instances show that one of the proposed heuristics, used as an upper bound, has an average gap less than 1.3% for instances optimally solved. The results indicate that both the lower and upper bounds are very tight and the branch-and-bound algorithm is the first algorithm that is able to optimally solve problems with up to 30 jobs in a reasonable amount of time.     

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

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

Heuristics for the single machine scheduling problem with quadratic earliness and tardiness penalties

In this paper, we consider the single machine scheduling problem with quadratic earliness and tardiness costs, and no machine idle time. We propose several dispatching heuristics, and analyse their performance on a wide range of instances. The heuristics include simple and widely used scheduling rules, as well as adaptations of those rules to a quadratic objective function. We also propose heuristic procedures that specifically address both the earliness and the tardiness penalties, as well as the quadratic cost function. Several improvement procedures were also analysed. These procedures are applied as an improvement step, once the heuristics have generated a schedule.     

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.     

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.     

带有交货期的比例流水车间调度问题的合作博弈

针对具有多个客户订单的比例流水车间调度问题,在考虑有交货期及提前和拖期惩罚下,以客户支出成本为优化指标,在客户通过合作结成联盟的方式下,以联盟内成员进行重新调度所获得的最大成本节省为联盟的价值,建立合作博弈模型.该合作博弈是具有无外部性的平衡博弈,从而有非空核.考虑到客户对提前加工和延迟加工的迫切程度不同,提出基于提前及拖期惩罚的β规则分配方法,该方法能得到带有交货期的比例流水车间调度合作博弈的一个核分配.通过混合差分进化算法求解最优调度顺序,实验结果验证了基于合作博弈模型的调度方法及成本分配方法的有效性.     

A meta-heuristic approach to solve a JIT scheduling problem in hybrid flow shop

In this paper we address a hybrid flow shop scheduling problem considering the minimization of the sum of the total earliness and tardiness penalties. This problem is proven to be NP-hard, and consequently the development of heuristic and meta-heuristic approaches to solve it is well justified. So, we propose an ant colony optimization method to deal with this problem. Our proposed method has several features, including some heuristics that specifically take into account both earliness and tardiness penalties to compute the heuristic information values. The performance of our algorithm is tested by numerical experiments on a large number of randomly generated problems. A comparison with solutions performance obtained by some constructive heuristics is presented. The results show that the proposed approach performs well for this problem.     

An exact approach to early/tardy scheduling with release dates

In this paper, we consider the single machine earliness/tardiness scheduling problem with different release dates and no unforced idle time. The problem is decomposed into weighted earliness and weighted tardiness subproblems. Lower bounding procedures are proposed for each of these subproblems, and the lower bound for the original problem is the sum of the lower bounds for the two subproblems. The lower bounds and several versions of a branch-and-bound algorithm are then tested on a set of randomly generated problems, and instances with up to 30 jobs are solved to optimality. To the best of our knowledge, this is the first exact approach for the early/tardy scheduling problem with release dates and no unforced idle time.     

Due date assignments and scheduling a single machine with a general earliness/tardiness cost function

We study three different due date assignment problems in scheduling a single machine which differ from each other based upon the objective function and due date assignment method being used. Two different objective functions are considered. The first is a cost function that includes earliness, tardiness and due date assignment penalties and the second is a function that includes penalties due to the number of tardy jobs and due date assignments. We assume that the earliness, tardiness and due date assignment penalties are continuous and non-decreasing functions of the corresponding duration. The goal is to minimize each objective function for two different due date assignment methods. The first is a method in which the assigned due dates are restricted to be equal while the second is a method that allows us to assign different due dates to different jobs.     

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.     

Minimizing total earliness and tardiness through unrelated parallel machine scheduling using distributed release time control

Using unrelated parallel machine scheduling to minimize the total earliness and tardiness of jobs with distinct due dates is a nondeterministic polynomial-hard problem. Delayed customer orders may result in penalties and reduce customer satisfaction. On the other hand, early completion creates inventory storage costs, which increase the total cost. Although parallel machines can increase productivity, machine assignments also increase the complexity of production. Therefore, the challenge in parallel machine scheduling is to dynamically adjust the machine assignment to complete the job within the shortest possible time. In this paper, we address an unrelated parallel machine scheduling problem for jobs with distinct due dates and dedicated machines. The objective is to dynamically allocate jobs to unrelated parallel machines in order to minimize the total earliness and tardiness time. We formulate the problem as a mixed integer linear programming (MILP) model and develop a modified genetic algorithm (GA) with a distributed release time control (GARTC) mechanism to obtain the near-optimal solution. A preliminary computational study indicates that the developed GARTC not only provides good quality solutions within a reasonable amount of time, but also outperforms the MILP model, a classic GA and heuristic approaches described in the literature.     

考虑多个RMAs的单机调度问题

在处理时间不断恶化的情况下,针对插入多个机器维护阶段(RMAs)和考虑交货期安排的单机调度问题展开研究,目标是最小化提前和拖期惩罚。产品加工过程中,在处理工件之前插入多个RMAs可以降低恶化现象从而恢复机器的生产效率,目的是同时找到最优序列、最优松弛时间和RMAs的最优位置以使提前和拖期惩罚最小。根据问题的特点,提出了相关的性质和定理,通过证明得出了最优的松弛时间。最后,证明了该问题在多项式时间内是可解的。     

Solving production scheduling with earliness/tardiness penalties by constraint programming

This paper deals with an application of constraint programming in production scheduling with earliness and tardiness penalties that reflects the scheduling part of the Just-In-Time inventory strategy. Two scheduling problems are studied, an industrial case study problem of lacquer production scheduling, and also the job-shop scheduling problem with earliness/tardiness costs. The paper presents two algorithms that help the constraint programming solver to find solutions of these complex problems. The first algorithm, called the cost directed initialization, performs a greedy initialization of the search tree. The second one, called the time reversing transformation and designed for lacquer production scheduling, reformulates the problem to be more easily searchable when the default search or the cost directed initialization is used. The conducted experiments, using case study instances and randomly generated problem instances, show that our algorithms outperform generic approaches, and on average give better results than other nontrivial algorithms.     

Exact and heuristic procedures for single machine scheduling with quadratic earliness and tardiness penalties

The present paper studies the single machine, no-idle-time scheduling problem with a weighted quadratic earliness and tardiness objective. We investigate the relationship between this problem and the assignment problem, and we derive two lower bounds and several heuristic procedures based on this relationship. Furthermore, the applicability of the time-indexed integer programming formulation is investigated. The results of a computational experiment on a set of randomly generated instances show (1) the high-quality results of the proposed heuristics, (2) the low optimality gap of one of the proposed lower bounds and (3) the applicability of the integer programming formulation to small and medium size cases of the problem.     

Efficient constructive and composite heuristics for the Permutation Flowshop to minimise total earliness and tardiness

In this paper we address the problem of scheduling jobs in a permutation flowshop with a just-in-time objective, i.e. the minimisation of the sum of total tardiness and total earliness. Since the problem is NP-hard, there are several approximate procedures available for the problem, although their performance largely depends on the due dates of the specific instance to be solved. After an in-depth analysis of the problem, different cases or sub-problems are identified and, by incorporating this knowledge, four heuristics are proposed: a fast constructive heuristic, and three different local search procedures that use the proposed constructive heuristic as initial solution.The proposed Prod. Type: FLPheuristics have been compared on an extensive set of instances with the best-so-far heuristic for the problem, as well as with adaptations of efficient heuristics for similar scheduling problems. The computational results show the excellent performance of the proposed algorithms. Finally, the positive impact of the efficient heuristics is evaluated by including them as seed sequences for one of the best metaheuristic for the problem.     

A tabu search algorithm for order acceptance and scheduling

We consider a make-to-order production system, where limited production capacity and order delivery requirements necessitate selective acceptance of the orders. Since tardiness penalties cause loss of revenue, scheduling and order acceptance decisions must be taken jointly to maximize total revenue. We present a tabu search algorithm that solves the order acceptance and scheduling problem on a single machine with release dates and sequence dependent setup times. We analyze the performance of the tabu search algorithm on an extensive set of test instances with up to 100 orders and compare it with two heuristics from the literature. In the comparison, we report optimality gaps which are calculated with respect to bounds generated from a mixed integer programming formulation. The results show that the tabu search algorithm gives near optimal solutions that are significantly better compared to the solutions given by the two heuristics. Furthermore, the run time of the tabu search algorithm is very small, even for 100 orders. The success of the proposed heuristic largely depends on its capability to incorporate in its search acceptance and scheduling decisions simultaneously.     

Minimizing maximum earliness on parallel identical machines

This paper addresses the scheduling problem of minimizing maximum earliness (or more generally — maximizing minimum lateness) on parallel identical machines. We prove that the two-machine case is NP-hard in the ordinary sense, and introduce a pseudo-polynomial dynamic programming algorithm for this case. When the number of machines is arbitrary, the problem is shown to be NP-hard in the strong sense. Then we introduce an efficient heuristic and two simple upper bounds on the optimal minimum lateness value. Finally we provide an extensive numerical study which indicates that the heuristic performs well in various job and machine settings.Scope and purposeIn recent years many researchers have focused on minimizing both earliness and tardiness costs. Only a few studies have considered problems with (maximum or total) earliness as the sole performance measure. We believe that the earliness measure is appropriate for many real-life settings, where the main cost component is the earliness (inventory) cost, and the tardiness (positive lateness) cost component is negligible. Our paper studies the scheduling problem of minmax earliness on parallel identical machines: we analyze the complexity of the problem, and introduce an efficient heuristic and simple bounds on the optimal cost.     

Minimizing the weighted sum of maximum earliness and maximum tardiness costs on a single machine with periodic preventive maintenance

We consider the problem of scheduling a set of jobs on a single machine against a common and restrictive due date. In particular, we are interested in the problem of minimizing the weighted sum of maximum earliness and maximum tardiness costs. This kind of objective function is related to the just-in-time environment where penalties, such as storage cost and additional charges for late delivery, should be avoided. First we present a mixed integer linear model for the problem without availability constraints and we prove that this model can be reduced to a polynomial-time model. Secondly, we suppose that the machine undergoes a periodic preventive maintenance. We present then a second mixed integer linear model to solve the problem to optimality. Although the latter problem can be solved to optimality for small instances, we show that the problem reduces to the one-dimensional bin packing problem. Computational results show that the proposed algorithm best fit decreasing performs well.     

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.