An effective hybrid multi-objective genetic algorithm for bi-criteria scheduling on a single batch processing machine with non-identical job sizes

This paper addresses the problem of scheduling jobs with non-identical sizes on a single batch processing machine. A batch processing machine is one which can process multiple jobs simultaneously as a batch as long as the total size of jobs being processed does not exceed the machine capacity. The batch processing time is equal to the longest processing time among all jobs in the batch. For the simultaneous minimization of the bi-criteria of makespan and maximum tardiness, we propose two different multi-objective genetic algorithms based on different representation schemes. While the first algorithm do search via generating sequences of jobs using genetic operators and then batching jobs keeping their order in the sequence, the second algorithm uses the idea of generating batches of jobs directly using genetic operators and ensures feasibility through using heuristic procedures. The type of representation used in the second algorithm allows introducing heuristics with the ability of biasing the search towards each objective and also allows hybridization with a local search heuristic that gives the ability of finding Pareto-optimal or locally efficient Pareto-solutions. Computational results show that the non-dominated solutions obtained by the latter algorithm are very superior in closeness to the true Pareto-optimal solutions and to keep diversity in the obtained Pareto-set, as the problem size increases.     

A branch and price algorithm to minimize makespan on a single batch processing machine with non-identical job sizes

In this paper, we consider the scheduling problem on a single batch processing machine with non-identical job sizes; in which the machine has a limited capacity and can process a group of jobs simultaneously as a batch. The processing time of a batch is the longest processing time of all jobs in the batch. The objective is to minimize the makespan. We formulate the problem using Dantzig–Wolfe decomposition as a set partitioning problem. Based on the set partitioning formulation, we present a tight lower bound using column generation method. A heuristic algorithm is also developed to generate the basic solution in the column generation method. A branch and price algorithm which combines the column generation technique with branch and bound method is then presented to obtain the optimal solution of the problem. The efficiency of the proposed branch and price algorithm is ultimately compared to the branch and bound algorithm from the literature, based on the generated sample problems.     

传搁时间约束下的运输与批处理机生产协调调度

针对炼钢模铸系统钢锭高温运作的特点,提出带有传搁时间约束的生产前运输与批处理机生产协调的调度问题.工件的加工时间依赖于其传搁时间,每批工件的加工时间为该批工件中加工时间最大值.目标函数为最小化总完工时间与生产费用的线性组合.通过复杂性分析,证明该问题是强NP难解问题.建立混合整数规划模型,基于动态规划提出两种特殊情况的最优算法,设计原问题的启发式算法并进行最坏情况下性能比分析.实验仿真结果验证了所提出启发式算法的有效性与稳定性.     

Minimizing makespan in a flow shop with two batch-processing machines using simulated annealing

This paper aims at minimizing the makespan of two batch-processing machines in a flow shop. The processing times and the sizes of the jobs are known and non-identical. The machines can process a batch as long as its capacity is not exceeded. The processing time of a batch is the longest processing time among all the jobs in that batch. The problem under study is NP-hard for makespan objective. Consequently, a heuristic based on Johnson's algorithm and a simulated annealing (SA) algorithm is proposed. Random instances were generated to verify the effectiveness of the proposed approaches. The results obtained from SA were compared with the proposed heuristic and a commercial solver. The SA outperformed both the heuristic and the commercial solver. On larger problem instances, the heuristic outperformed the commercial solver.     

Heuristics for minimizing total completion time and maximum lateness on identical parallel machines with setup times

This paper aims at minimizing the total completion time together with the maximum lateness. Jobs are processed by parallel machines in batches. A setup is required before processing a batch, which is common for all jobs in the batch. Jobs are continuously processed after the setup time. The processing length of a batch is the sum of the setup time and processing times of the jobs it contains. Due to the availability constraint, the completion time of a job is the time when a batch is totally processed. Considering due dates, the jobs need to be processed in a way that the total completion time and the maximum lateness are minimized. This problem is a kind of NP-hard so first we present a constructive heuristic to solve the problem. Then we propose a genetic algorithm whose initial population is formed by using the heuristic approach. Computational experiments are carried out to evaluate the performance of the proposed algorithms.     

Tabu search heuristic for two-machine flowshop with batch processing machines

Batch processing machines are frequently encountered in many industrial environments. A batch processing machine is one which can process several jobs simultaneously as a batch. The processing time of a batch is equal to the largest processing time of any job in the batch. This study deals with the problem of scheduling jobs in a flowshop with two batch processing machines such that the makespan is minimized. A heuristic based on Tabu search (TS) technique is proposed. The proposed heuristic is compared with a heuristic based on mixed integer linear programming (MILP). Because the complexity of the MILP-based heuristic is depended on the number of job batches, the comparison is under up-to-eight batches problem. In order to measure the proposed TS-based heuristic in larger batch problem, the relative error percentage with the lower bound (REP_LB) is used. The results show that the proposed heuristic is efficient and effective for the problems with relative large job sizes.     

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.     

Single facility scheduling with nonlinear processing times

This paper considers the static single facility scheduling problem where the processing times of jobs are a monotonically increasing function of their starting (waiting) times and the objective is to minimize the total elapsed time (called the makespan) in which all jobs complete their processing. Based on the combinatorial analysis of the problem, an exact optimization algorithm is developed for the general processing time function which is then specialized for the linear case. In view of the excessive computational burden of the exact optimization algorithm for the nonlinear processing time functions, heuristic algorithms are proposed. The effectiveness of these proposed alogrithms is empirically evaluated and found to indicate that these heuristic algorithms yield optimal or near optimal schedules in many cases.     

Decomposition heuristics for minimizing earliness–tardiness on parallel burn-in ovens with a common due date

This paper considers a scheduling problem for parallel burn-in ovens in the semiconductor manufacturing industry. An oven is a batch processing machine with restricted capacity. The batch processing time is set by the longest processing time among those of all the jobs contained in the batch. All jobs are assumed to have the same due date. The objective is to minimize the sum of the absolute deviations of completion times from the due date (earliness–tardiness) of all jobs. We suggest three decomposition heuristics. The first heuristic applies the exact algorithm due to Emmons and Hall (for the nonbatching problem) in order to assign the jobs to separate early and tardy job sets for each of the parallel burn-in ovens. Then, we use job sequencing rules and dynamic programming in order to form batches for the early and tardy job sets and sequence them optimally. The second proposed heuristic is based on genetic algorithms. We use a genetic algorithm in order to assign jobs to each single burn-in oven. Then, after forming early and tardy job sets for each oven we apply again sequencing rules and dynamic programming techniques to the early and tardy jobs sets on each single machine in order to form batches. The third heuristic assigns jobs to the m early job sets and m tardy jobs sets in case of m burn-in ovens in parallel via a genetic algorithm and applies again dynamic programming and sequencing rules. We report on computational experiments based on generated test data and compare the results of the heuristics with known exact solution for small size test instances obtained from a branch and bound scheme.     

极小化最大完工时间的单机连续型批调度问题

从钢铁工业中加热炉对管坯的加热过程,提出一种新的连续型批处理机调度问题,与传统批处理机调度问题的批进批出方式不同,其主要特征为批中工件的进入、处理和离开都连续进行,批B_i的处理时间与该批的大小|B_i|、批中工件T_j的处理时间p_j及机器的容量C都有关,表示为p^{(i)}=\dmax_{T_j\in B_i}\{p_j\}(1+\displaystyle\frac{|B_i|-1}{C}).对于极小化最大完工时间问题,给出了一个复杂性为O(n^2)的动态规划算法,并证明了这个算法的最优性.     

Unrelated parallel machine scheduling with setup times and a total weighted tardiness objective

This paper presents several search heuristics and their performance in batch scheduling of parallel, unrelated machines. Identical or similar jobs are typically processed in batches in order to decrease setup times and/or processing times. The problem accounts for allotting batched work parts into unrelated parallel machines, where each batch consists of a fixed number of jobs. Some batches may contain different jobs but all jobs within each batch should have an identical processing time and a common due date. Processing time of each job of a batch is determined according to the machine group as well as the batch group to which the job belongs. Major or minor setup times are required between two subsequent batches depending on batch sequence but are independent of machines. The objective of our study is to minimize the total weighted tardiness for the unrelated parallel machine scheduling. Four search heuristics are proposed to address the problem, namely (1) the earliest weighted due date, (2) the shortest weighted processing time, (3) the two-level batch scheduling heuristic, and (4) the simulated annealing method. These proposed local search heuristics are tested through computational experiments with data from dicing operations of a compound semiconductor manufacturing facility.     

单台批处理机总加权完成时间最小化的启发式算法

批处理机总加权完成时间最小化问题的复杂性目前还没有确定,因此有必要研究该问题的启发式算法．基于对该问题最优解性质的分析,提出了工件分批的最优性质．分别基于WSPT规则和SPT规则对工件进行总排序,利用工件最优分批性质进行分批,提出了两种启发式算法（简称WSPTS和SPTS）．为了检验算法的性能．将提出的算法与此问题的基准算法和常规算法进行了比较,结果表明,启发式算法WSPTS要优于其他的算法,而SPTS算法的性能最优．     

Machine scheduling with job class setup and delivery considerations

We study machine scheduling problems in which the jobs belong to different job classes and they need to be delivered to customers after processing. A setup time is required for a job if it is the first job to be processed on a machine or its processing on a machine follows a job that belongs to another class. Processed jobs are delivered in batches to their respective customers. The batch size is limited by the capacity of the delivery vehicles and each shipment incurs a transport cost and takes a fixed amount of time. The objective is to minimize the weighted sum of the last arrival time of jobs to customers and the delivery (transportation) cost. For the problem of processing jobs on a single machine and delivering them to multiple customers, we develop a dynamic programming algorithm to solve the problem optimally. For the problem of processing jobs on parallel machines and delivering them to a single customer, we propose a heuristic and analyze its performance bound.     

A DP algorithm for minimizing makespan and total completion time on a series-batching machine

This paper studies a bicriteria scheduling problem on a series-batching machine with objective of minimizing makespan and total completion time simultaneously. A series-batching machine is a machine that can handle up to b jobs in a batch and the completion time of all jobs in a batch is equal to the finishing time of the last job in the batch and the processing time of a batch is the sum of the processing times of jobs in the batch. In addition, there is a constant setup time s for each batch. For the problem we can find all Pareto optimal solutions in O(n²) time by a dynamic programming algorithm, where n denotes the number of jobs.     

Single machine total completion time minimization scheduling with a time-dependent learning effect and deteriorating jobs

In this article, we consider a single machine scheduling problem with a time-dependent learning effect and deteriorating jobs. By the effects of time-dependent learning and deterioration, we mean that the job processing time is defined by a function of its starting time and total normal processing time of jobs in front of it in the sequence. The objective is to determine an optimal schedule so as to minimize the total completion time. This problem remains open for the case of ?1?a?a denotes the learning index; we show that an optimal schedule of the problem is V-shaped with respect to job normal processing times. Three heuristic algorithms utilising the V-shaped property are proposed, and computational experiments show that the last heuristic algorithm performs effectively and efficiently in obtaining near-optimal solutions.     

Algorithms for scheduling incompatible job families on single batching machine with limited capacity

Motivated by applications in food processing and semiconductor manufacturing industries, we consider the scheduling problem of a batching machine with jobs of multiple families. The machine has a limited capacity to accommodate jobs. The jobs are in arbitrary sizes and multiple families. Jobs from different families cannot be processed in a batch. We show the problems of minimizing makespan and total batch completion time are both NP-hard in the strong sense. We present a mixed integer programming model for the problems. Then we propose two polynomial time heuristics based on longest processing time first rule and first fit rule. For the special case where a larger job also has a longer processing time, the heuristic for minimizing makespan is optimal. For the general case, we show the performance guarantee of the methods for the two objectives respectively.     

A heuristic approach for single-machine scheduling with due dates and class setups

The single-machine sequence-independent class setup scheduling problem is examined in this paper. It is assumed that jobs are classified into classes and a setup is required between jobs of different classes, but not of the same class. Furthermore, this setup time is fixed and depends only on the current job. Since the problem is NP-hard, a heuristic algorithm is proposed to find an approximate schedule that minimizes the maximum lateness on a set of jobs. The algorithm can easily be modified to solve the maximum tardiness problems as well. The accuracy of the heuristic algorithm in generating near optimal solutions is empirically evaluated.Scope and purposeFor batch manufacturing, it maybe desirable to produce many items of the same type, or class, at the same run in order to save the setup cost. However, committing facilities to long production runs for one product may inevitably make others tardy. Small batch size may conform urgent jobs to their delivery date, but one of the consequences would be the loss of productive efficiency due to numerous setups. Therefore, scheduling is basically a trade-off between the inherently conflicting efficiency measure and due-date compliance. This paper considers a single-machine scheduling problem in which jobs are classified into classes and a setup is required between jobs of different classes. The setup time is fixed and depends only on the current job. This problem is called a sequence-independent class setup problem and is NP-complete.     

就绪时间受限的负荷单机环境下返工工件重调度方法

研究了返工工件的单机重调度问题.在初始调度中初始工件带有不同的就绪时间,优化目标为最小化初始工件等待时间和;重调度时在满足每个初始工件最大等待时间约束情况下安排返工工件的生产,优化目标为最小化所有工件等待时间和.文中首先建立了RRSM （Rescheduling for reworks on single machine）问题模型,并证明其为NP难问题.然后,提出并证明了三个RRSM问题性质,进而根据诸性质设计了求解RRSM问题的动态插入启发式（Dynamic insert heuristic,DIH）算法.证明了应用DIH算法能在多项式时间内求得两种特殊RRSM问题的最优解. 最后,分析了DIH算法解的特点,给出了最优解的判定方法,并通过算例说明了DIH算法的有效性.     

Minimizing the makespan on a batch machine with non-identical job sizes: an exact procedure

A batch processing machine can simultaneously process several jobs forming a batch. This paper considers the problem of scheduling jobs with non-identical capacity requirements, on a single-batch processing machine of a given capacity, to minimize the makespan. The processing time of a batch is equal to the largest processing time of any job in the batch. We present some dominance properties for a general enumeration scheme and for the makespan criterion, and provide a branch and bound method. For large-scale problems, we use this enumeration scheme as a heuristic method.Scope and purposeUsually in classical scheduling problems, a machine can perform only one job at a time. Although, one can find machines that can process several jobs simultaneously as a batch. All jobs of a same batch have common starting and ending times. Batch processing machines are encountered in many different environments, such as burn-in operations in semiconductor industries or heat treatment operations in metalworking industries. In the first case, the capacity of the machine is defined by the number of jobs it can hold. In the second case, each job has a certain capacity requirement and the total size of a batch cannot exceed the capacity of the machine. Hence, the number of jobs contained in each batch may be different. In this paper, we consider this second case (which is more difficult) and we provide an exact method for the makespan criterion (minimizing the last ending time).     

Scheduling a batch processing machine with incompatible job families

The problem of scheduling batch processors is important in some industries and, at a more fundamental level, captures an element of complexity common to many practical scheduling problems. We describe a branch and bound procedure applicable to a batch processor model with incompatible job families. Jobs in a given family have identical job processing times, arbitrary job weights, and arbitrary job sizes. Batches are limited to jobs from the same family. The scheduling objective is to minimize total weighted completion time. We find that the procedure returns optimal solutions to problems of up to about 25 jobs in reasonable CPU time, and can be adapted for use as a heuristic for larger problems.