A discrete artificial bee colony algorithm for single machine scheduling problems

This paper presents a discrete artificial bee colony algorithm for a single machine earliness–tardiness scheduling problem. The objective of single machine earliness–tardiness scheduling problems is to find a job sequence that minimises the total sum of earliness–tardiness penalties. Artificial bee colony (ABC) algorithm is a swarm-based meta-heuristic, which mimics the foraging behaviour of honey bee swarms. In this study, several modifications to the original ABC algorithm are proposed for adapting the algorithm to efficiently solve combinatorial optimisation problems like single machine scheduling. In proposed study, instead of using a single search operator to generate neighbour solutions, random selection from an operator pool is employed. Moreover, novel crossover operators are presented and employed with several parent sets with different characteristics to enhance both exploration and exploitation behaviour of the proposed algorithm. The performance of the presented meta-heuristic is evaluated on several benchmark problems in detail and compared with the state-of-the-art algorithms. Computational results indicate that the algorithm can produce better solutions in terms of solution quality, robustness and computational time when compared to other algorithms.     

基于三阶段解码机制的作业车间JIT调度算法研究

零部件加工过程的精细化管控是保证大型复杂装备制造企业高效、均衡和低成本运营的重要手段。针对现有JIT调度方法普遍采用两阶段求解策略导致调度算法计算效率较低的问题,本文提出一种单阶段的改进型遗传算法解决思路：针对每一迭代优化过程中的染色体,设计了一种包含半主动解码、拖期工件贪婪插入、提前工件贪婪插入的三阶段渐进式解码机制,以引导待调度工序集尽可能在各自的交货时间点准时完工。这种三阶段解码方法具有与非正规调度指标吻合、解码机制简单和解码速度快等独特优势,最后采用72个JIT调度标准算例验证了该方法在优化性能、计算效率等方面的有效性。     

Simulated annealing for parallel machine scheduling with earliness-tardiness penalties and sequence-dependent set-up times

Scheduling problems with earliness and tardiness penalties are commonly encountered in today's manufacturing environment due to the current emphasis on the just-in-time (JIT) production philosophy. The problem studied in this work is the parallel machine earliness-tardiness non-common due date sequence-dependent set-up time scheduling problem (PETNDDSP) for jobs with varying processing times, where the objective is to minimize the sum of the absolute deviations of job completion times from their corresponding due dates. The research presented provides a first step towards obtaining near optimal solutions for this problem using local search heuristics in the framework of a meta-heuristic technique known as simulated annealing (SA). The computational study shows that, using the SA methodology, significant improvements to the local search heuristic solutions can be achieved for problems of this type.     

SCHEDULING A SINGLE MACHINE TO MINIMIZE TWO CRITERIA: MAXIMUM TARDINESS AND NUMBER OF TARDY JOBS

In this paper we consider a single machine scheduling problem with two criteria; minimizing both maximum tardiness and the number of tardy jobs. We present both heuristic and branch-and-bound algorithms to find the schedule which minimizes the number of tardy jobs among all schedules having minimal maximum tardiness. Computational results show that problems with up to 40 jobs can be solved in less than one minute of computer time, and solution difficulty tends to increase as the range of due dates increases relative to the total processing time. We extend our results to generate all nondominated schedules for the two criteria. Computational experiments indicate that all non-dominated solutions to problems with 40 jobs can be generated. However, solution difficulty for these problems is highly dependent on problem parameters.     

Scheduling about an unrestricted common due windowwith arbitrary earliness/tardiness penalty rates

We consider the NP-hard problem of scheduling jobs on a single machine about an unrestricted due window to minimize total weighted earliness and tardiness cost. Each job has an earliness penalty rate and a tardiness penalty rate that are allowed to be arbitrary. Earliness or tardiness cost is assessed when a job completes outside the due window, which may be an instant in time or a time increment defining acceptable job completion. In this paper we present properties that characterize the structure of an optimal schedule, present a lower bound, propose a two-step branch and bound algorithm, and report results from a computational experiment. We find that optimal solutions can be quickly obtained for medium-sized problem instances.     

A moving block heuristic to minimise earliness and tardiness costs on parallel machines

Earliness and tardiness problems are commonly encountered in just-in-time manufacturing systems, where the operations are performed neither early nor late. In this paper, a parallel machine moving block heuristic (Pm-MBH) with polynomial-time computational complexity is developed to address an earliness and tardiness scheduling problem. A mixed integer program (MIP) is presented in order to analyse the solution quality of the Pm-MBH solutions. Using a paired t-test, an analysis is performed to analyse the performance of Pm-MBH when compared to time-constrained MIP (MIPH) over the experimental space. Based on the computational results, Pm-MBH obtains good solutions in a short amount of computation time.     

Effective dynamic dispatching rule and constructive heuristic for solving single-machine scheduling problems with a common due window

This study addresses the single-machine scheduling problem with a common due window (CDW) that has a constant size and position. The objective is to minimise the total weighted earliness–tardiness penalties for jobs completed out of the CDW. To determine a schedule as close to optimum as possible, this study develops a dynamic dispatching rule and an effective constructive heuristic. The better performance of the proposed heuristic is demonstrated by comparing the results of it with those of a state-of-the-art greedy heuristic on a well-known benchmark problem set. In addition, we incorporate the constructive heuristic into a best-so-far meta-heuristic to examine the benefit of the proposed heuristic. The results show that the best known solutions in 144 out of the 250 benchmark instances are improved.     

Permutation flow shop scheduling with earliness and tardiness penalties

We consider the permutation flow shop scheduling problem with earliness and tardiness penalties (E/T) and common due date for jobs. We show that the problem can be sub-divided into three cases: (i) the due date is such that all jobs are necessarily tardy; (ii) the due date is unrestricted; and (iii) the due date is between the two. Based on analytical results we provide partial characterisation of the optimal solution and develop a comprehensive approach for solving the problem over the entire range of due dates. Our approach, which draws upon the existing literature and results for the single machine problem, successfully exploits the properties of the optimal solution. Limited computational results indicate that the performance of the heuristic is reasonable and has the potential to significantly improve performance. This approach has been incorporated as part of the scheduling module of the production planning and scheduling system we developed for a medium-sized bulk drug manufacturer.     

Parallel machine scheduling problem with ready times,due times and sequence-dependent setup times using meta-heuristic algorithms

This article considers a parallel machine scheduling problem with ready times, due times and sequence-dependent setup times. The objective of this problem is to determine the allocation policy of jobs and the scheduling policy of machines to minimize the weighted sum of setup times, delay times and tardy times. A mathematical model for optimal solution is derived. An in-depth analysis of the model shows that it is very complicated and difficult to obtain optimal solutions as the problem size becomes large. Therefore, two meta-heuristics, genetic algorithm (GA) and a new population-based evolutionary meta-heuristic called self-evolution algorithm (SEA), are proposed. The performances of the meta-heuristic algorithms are evaluated through comparison with optimal solutions using several randomly generated examples.     

Minimising earliness and tardiness penalties in single machine scheduling against common due date using imperialist competitive algorithm

In this paper a novel evolutionary-based approach is utilised for efficiently solving the NP-hard problem of scheduling numerous common-due-date jobs on a single machine. Minimising the sum of earliness and tardiness penalties for all jobs is considered as the target function. The performance of the proposed approach is examined through a computational comparative study with 280 benchmark problems with up to 1000 jobs where the numerical results indicate that it can produce ‘better’ solutions in less computational time when compared to benchmark results and the methods available in the literature, namely genetic algorithm (GA), Tabu search (TS) and differential evolution (DE).     

Minimising total tardiness for the identical parallel machine scheduling problem with splitting jobs and sequence-dependent setup times

This paper focuses on an identical parallel machine scheduling problem with minimising total tardiness of jobs. There are two major issues involved in this scheduling problem; (1) jobs which can be split into multiple sub-jobs for being processed on parallel machines independently and (2) sequence-dependent setup times between the jobs with different part types. We present a novel mathematical model with meta-heuristic approaches to solve the problem. We propose two encoding schemes for meta-heuristic solutions and three decoding methods for obtaining a schedule from the meta-heuristic solutions. Six different simulated annealing algorithms and genetic algorithms, respectively, are developed with six combinations of two encoding schemes and three decoding methods. Computational experiments are performed to find the best combination from those encoding schemes and decoding methods. Our findings show that the suggested algorithm provides not only better solution quality, but also less computation time required than the commercial optimisation solvers.     

Variable neighbourhood search for minimising tardiness objectives on flow shop with batch processing machines

This paper presents the scheduling problem on flow shop with many batch processing machines (BPM) to minimise total tardiness, maximum tardiness and number of tardy jobs, respectively. We propose an efficient variable neighbourhood search (VNS) for the problem, in which job permutation is the only optimisation object and the solutions of batch formation and batch scheduling can be directly obtained by using the permutation. To obtain the promising results, an initial solution of VNS is first produced and then one insertion operation and two swap operations are applied to improve the solution. The proposed VNS is finally tested and the computational results show its good performance on many-BPM flow shop scheduling.     

准时化(JIT)思想下有关交货期窗口的单机调度问题

研究了有关交货期窗口的单机调度问题。在过去的１０年中,准时化的概念对中国工业的影响很大。早于或晚于交货期窗口的任务都不受欢迎,且将导致提前或拖期惩罚。如果任务的完工时间偏离了交货期窗口,就要受到固定的惩罚,惩罚量与提前或拖期完工无关。目标是极小化所有惩罚的和。设如果任务在交货期准时完工,则不受惩罚;目标就是寻找一个最优调度极小化提前和拖期任务的总数。给出了确定最优调度的多项式时间算法,最后的例子说     

Bi-objective reentrant hybrid flowshop scheduling: an iterated Pareto greedy algorithm

The multi-objective reentrant hybrid flowshop scheduling problem (RHFSP) exhibits significance in many industrial applications, but appears under-studied in the literature. In this study, an iterated Pareto greedy (IPG) algorithm is proposed to solve a RHFSP with the bi-objective of minimising makespan and total tardiness. The performance of the proposed IPG algorithm is evaluated by comparing its solutions to existing meta-heuristic algorithms on the same benchmark problem set. Experimental results show that the proposed IPG algorithm significantly outperforms the best available algorithms in terms of the convergence to optimal solutions, the diversity of solutions and the dominance of solutions. The statistical analysis manifestly shows that the proposed IPG algorithm can serve as a new benchmark approach for future research on this extremely challenging scheduling problem.     

A two‐phase approach for single machine scheduling problems: Minimizing the total absolute deviation

Abstract

This paper presents a heuristic for solving a single machine scheduling problem with the objective of minimizing the total absolute deviation. The job to be scheduled on the machine has a processing time, p_i , and a preferred due date, d_i . The total absolute deviation is defined as the sum of the earliness or tardiness of each job on a schedule 5. This problem is proved to be NP‐complete by Garey et al. [8]. As a result, we developed a two‐phase procedure to provide a near‐optimal solution to this problem. The two‐phase procedure includes the following steps: First, a greedy heuristic is applied to the set of jobs, N, to generate a “good” initial sequence. According to this initial sequence, we run Garey's local optimization algorithm to provide an initial schedule. Then, a pairwise switching algorithm is adopted to further reduce the total deviation of the schedule. The effectiveness of the two‐phase procedure is empirically evaluated and has been found to indicate that the solutions obtained from this heuristic procedure are often better than other heuristic approaches.     

Minimizing Weighted Absolute Deviation in Single Machine Scheduling

This paper presents a procedure to minimize the total penalty when jobs are scheduled on a single machine subject to earliness and tardiness penalties. This performance criterion has been shown to be non-regular thus, requiring a search among schedules with inserted machine idle time to find a solution. A procedure to optimally insert idle time is also presented.     

Multi-objective fuzzy parallel machine scheduling problems under fuzzy job deterioration and learning effects

This paper investigates a multi-objective parallel machine scheduling problem under fully fuzzy environment with fuzzy job deterioration effect, fuzzy learning effect and fuzzy processing times. Due dates are decision variables for the problem and objective functions are to minimise total tardiness penalty cost, to minimise earliness penalty cost and to minimise cost of setting due dates. Due date assignment problems are significant for Just-in-Time (JIT) thought. A JIT company may want to have optimum schedule by minimising cost combination of earliness, tardiness and setting due dates. In this paper, we compare different approaches for modelling fuzzy mathematical programming models with a local search algorithm based on expected values of fuzzy parameters such as job deterioration effect, learning effect and processing times.     

A dispatching rule and a random iterated greedy metaheuristic for identical parallel machine scheduling to minimize total tardiness

This paper addresses a real-life production scheduling problem with identical parallel machines, originating from a plant producing Acrylonitrile-Butadiene-Styrene (ABS) plate products. In the considered practical scheduling problem, ABS plate has some specific specifications and each specification has several different levels. Because there is at least one different level of specification between two ABS plate products, it is necessary to make a set-up adjustment on each machine whenever a switch occurs from processing one ABS plate product to another product. As tardiness leads to extra penalty costs and opportunity losses, the objective of minimising total tardiness has become one of the most important tasks for the schedule manager in the plant. The problem can be classified as an identical parallel machine scheduling problem to minimise the total tardiness. A dispatching rule is proposed for this problem and evaluated by comparing it with the current scheduling method and several existing approaches. Moreover, an iterated greedy-based metaheuristic is developed to further improve the initial solution. The experimental results show that the proposed metaheuristic can perform better than an existing tabu search algorithm, and obtain the optimal solution for small-sized problems and significantly improve the initial solutions for large-sized problems.     

A problem space algorithm for single machine weighted tardiness problems

We propose a problem space genetic algorithm to solve single machine total weighted tardiness scheduling problems. The proposed algorithm utilizes global and time-dependent local dominance rules to improve the neighborhood structure of the search space. They are also a powerful exploitation (intensifying) tool since the global optimum is one of the local optimum solutions. Furthermore, the problem space search method significantly enhances the exploration (diversification) capability of the genetic algorithm. In summary, we can improve both solution quality and robustness over the other local search algorithms reported in the literature.     

SINGLE-MACHINE SCHEDULING WITH CONTROLLABLE PROCESSING TIMES AND EARLINESS,TARDINESS AND COMPLETION TIME PENALTIES

The paper considers the problem of scheduling nindependent and simultaneously available jobs on a single machine, where the job processing times are compressible as a linear cost function. The objective is to find an optimal permutation of the jobs, an optimal due date and the optimal processing times which jointly minimize a cost function consisting of the earliness, tardiness, completion time and compressing costs. It shows that the problem can be solved as an assignment problem.