Minimising total tardiness in the m-machine flowshop problem: A review and evaluation of heuristics and metaheuristics

In this work, a review and comprehensive evaluation of heuristics and metaheuristics for the m-machine flowshop scheduling problem with the objective of minimising total tardiness is presented. Published reviews about this objective usually deal with a single machine or parallel machines and no recent methods are compared. Moreover, the existing reviews do not use the same benchmark of instances and the results are difficult to reproduce and generalise. We have implemented a total of 40 different heuristics and metaheuristics and we have analysed their performance under the same benchmark of instances in order to make a global and fair comparison. In this comparison, we study from the classical priority rules to the most recent tabu search, simulated annealing and genetic algorithms. In the evaluations we use the experimental design approach and careful statistical analyses to validate the effectiveness of the different methods tested. The results allow us to clearly identify the state-of-the-art 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.     

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.     

Adaptive lead time quotation in a pull production system with lead time responsive demand

In this paper, a single-stage single-class kanban controlled manufacturing system is considered, where the problem is quoting accurate lead times for orders that are generated by an MRP system. Order release mechanism as in classical MRP is sensitive to the changes in the lead time according to the concept of lead time syndrome. The objective is to establish a cost effective lead time quoting procedure. The problem is modeled as a two-dimensional Markov chain, and it is solved explicitly by using matrix geometric techniques. Comparative analysis is done between static and dynamic lead time quoting procedures, and significant cost benefits of the dynamic procedure are shown under various scenarios. Guidelines for setting design parameters such as the number of kanbans and the frequency of updating the lead time are provided through numerical tests.     

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.     

一种新调度类型及其在作业车间调度中的应用

研究改进遗传算法解决作业车间调度问题,问题染色体的编码采用基于工序的编码。针对传统的调度类型的局限性,提出全主动调度及其基于工序编码的产生机制。为了克服传统遗传算法求解调度问题易于早熟收敛的缺点,设计基于优先工序交叉(Precedence operation crossover,POX)和改进子代产生模式的遗传算法。用改进的遗传算法求解传统调度问题、交货期调度问题和提前/拖期(Earliness/Tardiness, E/T)调度问题,研究半主动、主动和全主动三种不同的调度解码机制对遗传算法提供解质量的影响。     

无等待排列流水车间提前/延期调度问题

在满足任务的交货期相同和工序无等待等假设条件后,提出了一种排列流水车间提前/延期惩罚调度问题的启发式算法. 该算法首先按照7种任务排序的规则分别得到任务的较优次序,然后分别使用NEH算法构造优化解,再对每个不同解进行邻域搜索,最后比较得出最优解. 在中小规模问题的数据实验中,该算法求解与最优解的相近程度达到99%左右,并且通过大量数据样本的标准差验证,求解的稳定性也非常好. 在大规模问题的数据实验中,该启发式算法体现出非常好的优化性能,同constraint programming(ILOG-CP）优化引擎算法比较,计算结果也明显占优.     

Scheduling of jobs and maintenance in a textile company

In this paper we consider a periodic maintenance scheduling problem in a textile company. In our research, a periodic maintenance schedule consists of several maintenance periods and each maintenance period is scheduled after a periodic time interval. The purpose of this paper is to find a schedule that minimizes the maximum tardiness subject to periodic maintenance and nonresumable jobs. An efficient heuristic is developed to provide the near optimal schedule for the problem. A branch-and-bound algorithm is also proposed to find the optimal schedule. Some important theorems associated with the problem are implemented in the algorithm. Computational results show that the proposed heuristic is highly accurate and efficient.     

Rule-based scheduling in wafer fabrication with due date-based objectives

Wafer fabrication is a capital-intensive and highly complex manufacturing process. In the wafer fabrication facility (fab), wafers are grouped as a lot to go through repeated sequences of operations to build circuitry. Lot scheduling is an important task for manufacturers to improve production efficiency and meet customers’ requirements of on-time delivery. In this research we propose a dispatching rule for lot scheduling in wafer fabs, focusing on three due date-based objectives: on-time delivery rate, mean tardiness, and maximum tardiness. Although many dispatching rules have been proposed in the literature, they usually perform well in some objectives and bad in others. Our rule implements good principles in existing rules by means of (1) an urgency function for a single lot, (2) a priority index function considering total urgency of multiple waiting lots, (3) a due date extension procedure for dealing with tardy lots, and (4) a lot filtering procedure for selecting urgent lots. Simulation experiments are conducted using nine data sets of fabs. Six scenarios formed by two levels of load and three levels of due date tightness are tested for each fab. Performance verification of the proposed rule is achieved by comparing with nine benchmark rules. The experimental results show that the proposed rule outperforms the benchmark rules in terms of all concerned objective functions.     

An investigation on a two-agent single-machine scheduling problem with unequal release dates

This paper addresses a two-agent scheduling problem on a single machine with arbitrary release dates, where the objective is to minimize the tardiness of one agent, while keeping the lateness of the other agent below or at a fixed level Q. A mixed integer programming model is first presented for its optimal solution, admittedly not to be practical or useful in the most cases, but theoretically interesting since it models the problem. Thus, as an alternative, a branch-and-bound algorithm incorporating with several dominance properties and a lower bound is provided to derive the optimal solution and a marriage in honey-bees optimization algorithm (MBO) is developed to derive the near-optimal solutions for the problem. Computational results are also presented to evaluate the performance of the proposed algorithms.