Constrained binary artificial bee colony to minimize the makespan for single machine batch processing with non-identical job sizes

This paper proposes an artificial bee colony approach to minimize the makespan for a single batch-processing machine. The single batch-processing problem is characterized by discontinuity in the objective function and having integer variables. Since the problem under study is NP-hard, an artificial bee colony approach is proposed. The penalty function method is used to convert the constrained problem to unconstrained problem, which is then solved by the ABC algorithm. A procedure to generate initial solutions is presented, which is based on filling partially filled batches first. The analysis in the article shows that the colony size, the value of the penalty parameter, the penalty function iteration, the ABC iteration, and maximum trials per food source all have a significant effect on the performance of the ABC algorithm; however, no pattern can be established.     

基于自由搜索算法求解单机差异工件批调度问题*

采用自由搜索（free search,FS）算法对单机差异工件批调度问题的制作跨度进行优化。针对该问题的离散优化特征以及自由搜索算法的不足,将自由搜索算法与实数编码遗传算法相结合,在标准FS算法的基础上引入两种杂交算子和精英保留策略,提出混合自由搜索（hybrid free search,HFS）算法。仿真实验结果表明,该算法表现出良好的鲁棒性和收敛性,与标准FS、FFLPT以及BFLPT算法相比,HFS算法提高了寻优精度。     

An improved meta-heuristic for makespan minimization of a single batch machine with non-identical job sizes

We consider the problem of minimizing the makespan on a single batch machine with non-identical job sizes, where several jobs can be simultaneously processed as a batch. We formulate makespan minimization as a problem of minimizing the wasted space. Applying a candidate set strategy to narrow the search space, combined with a wasted-space-based heuristic to update the pheromone information, an improved max–min ant system algorithm is presented. A specific local search method is incorporated to gain better performance. Appropriate parameter settings in the proposed algorithm are determined by extensive experiments. The experimental results show that the proposed algorithm outperforms several previously studied algorithms.     

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).     

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.     

An ACO algorithm for makespan minimization in parallel batch machines with non-identical job sizes and incompatible job families

We study the problem of scheduling a set of N jobs with non-identical job sizes from F different families on a set of M parallel batch machines; the objective is to minimize the makespan. The problem is known to be NP-hard. A meta-heuristic based on Max–Min Ant System (MMAS) is presented. The performance of the algorithm is compared with several previously studied algorithms by computational experiments. According to our results, the average distance between the solutions found by our proposed algorithm and the lower bounds is about 4% less than that of the best of all the compared algorithms, demonstrating that our algorithm outperforms the previously studied algorithms.     

Scheduling unrelated parallel batch processing machines with non-identical job sizes

Scheduling unrelated parallel batch processing machines to minimize makespan is studied in this paper. Jobs with non-identical sizes are scheduled on batch processing machines that can process several jobs as a batch as long as the machine capacity is not violated. Several heuristics based on best fit longest processing time (BFLPT) in two groups are proposed to solve the problem. A lower bound is also proved to evaluate the quality of the heuristics. Computational experiments were undertaken. These showed that J_SC-BFLPT, considering both load balance of machines and job processing times, was robust and outperformed other heuristics for most of the problem categories.     

Enhanced grouping league championship and optics inspired optimization algorithms for scheduling a batch processing machine with job conflicts and non-identical job sizes

This research aims to address scheduling of a single batch processing machine, where jobs are in different sizes and have a conflicting nature with each other, in the sense that two conflicting jobs cannot share the same batch and hence, cannot be processed simultaneously by the machine. The problem is referred to as SBMC. After formulating the problem, a strong lower bound procedure is developed by transforming a relaxed version of the scheduling problem to the multiple bottleneck transportation problem (MTP) with conflicts. An efficient Lagrangian relaxation procedure is proposed, which takes advantage of decomposable nature of the relaxed problem, to attain a lower bound for MTP which in essence is a lower bound for SBMC. To solve the problem, two metaheuristic algorithms, namely the League Championship Algorithm (LCA) and Optic Inspired Optimization (OIO), are adapted and fundamentally modified to match the problem unique structure (i.e., the grouping structure) and accordingly the grouping version of these algorithms is developed. The effectiveness of the lower bound procedure, as well as algorithms, are evaluated through extensive computational experiments. To show they perform efficiently in running times and effective in finding near-optimal bounds for most of the problem instances, we generate 20 different classes of problems according to variability in job sizes, number of jobs and density of incompatibility matrix. Then, we make comparison with two of extensively used algorithms from literature, SA and GA. Our proposed algorithms obtain solutions with objective values less than 6% gap from the lower bound and outperform SA and GA algorithms, especially for large instances. Moreover, values of the lower bound procedure lie within less than 4% of objective values provided by CPLEX.     

不同尺寸工件批调度问题的自适应蚁群退火算法*

研究不同尺寸工件单机批调度问题,将蚁群算法与模拟退火算法相结合,引入自适应状态转移概率,提出了一种自适应蚁群退火算法AACSA(adaptive ant colony simulated annealing)。该算法利用模拟退火算法实现了一种新的混合信息素更新策略,此外根据停滞次数,动态改变状态转移概率,有效地避免算法陷入停滞以及局部最优,提高算法的性能。仿真实验结果表明,AACSA与蚁群优化算法BACO、模拟退火算法SA、启发式规则BFLPT相比,算法求解的性能更好。     

Minimising makespan for two batch-processing machines with non-identical job sizes in job shop

In this article, the job shop scheduling problem with two batch-processing machines is considered. The machines have limited capacity and the jobs have non-identical job sizes. The jobs are processed in batches and the total size of each batch cannot exceed the machine capacity. The processing times of a job on the two machines are proportional. We show the problem of minimising makespan is NP-hard in the strong sense. Then we provide an approximation algorithm with worst-case ratio no more than 4, and the running time of the algorithm is O(n?log?n). Finally, the performance of the proposed algorithm is tested by different levels of instances. Computational results demonstrate the effectiveness of the algorithm for all the instances.     

Scheduling unrelated parallel batch processing machines with non-identical job sizes and unequal ready times

This research analyzes the problem of scheduling a set of n jobs with arbitrary job sizes and non-zero ready times on a set of m unrelated parallel batch processing machines so as to minimize the makespan. Unrelated parallel machine is a generalization of the identical parallel processing machines and is closer to real-world production systems. Each machine can accommodate and process several jobs simultaneously as a batch as long as the machine capacity is not exceeded. The batch processing time and the batch ready time are respectively equal to the largest processing time and the largest ready time among all the jobs in the batch. Motivated by the computational complexity and the practical relevance of the problem, we present several heuristics based on first-fit and best-fit earliest job ready time rules. We also present a mixed integer programming model for the problem and a lower bound to evaluate the quality of the heuristics. The small computational effort of deterministic heuristics, which is valuable in some practical applications, is also one of the reasons that motivates this study. The results show that the heuristic proposed in this paper has a superior performance compared to the heuristics based on ideas proposed in the literature.     

动态自适应加权多态蚁群算法求解差异工件单机批调度问题*

针对差异工件的单机批调度问题,提出了动态自适应加权多态蚁群算法对最大完工时间进行优化,该算法引入了不同种类的蚁群,每种蚁群都有不同的信息素调控机制,并根据批调度问题对不同种类的蚁群的状态转移概率和信息素更新机制进行了改进,同时将局域搜索与全局搜索相结合,从而更符合蚁群的真实信息处理机制。对不同规模的算例进行了仿真,结果验证了该算法的有效性和可行性。     

差异工件平行机批调度问题的SAGA*

为了求解差异工件平行机批调度问题,提出了一种模拟退火遗传算法 (simulated annealing genetic algorithm,SAGA)。将模拟退火算法（simulated annealing,SA）的状态转移操作引入基于最优保留的遗传算法(genetic algorithm,GA)中,作为局部搜索算子,以避免算法陷入局部最优,也有效地发挥了SA和GA在局部搜索与全局搜索能力方面的优势。为了解决GA迭代后期适应函数难以区分一些适应度接近的个体这个问题,SAGA分两阶段标定适应函数,在进化后期     

模糊环境下多目标差异作业单机批调度问题研究

针对现实生产制造系统中存在的时间参数模糊化问题,采用梯形模糊数表征时间参数,给出一种具有模糊交货期和模糊加工时间,以最小化提前/拖期惩罚、制造跨度以及加工费用为目标的多目标差异作业单机批调度问题模型.在对该问题进行求解方面,针对基本粒子群算法容易陷入局部最优的问题,引入混沌局部搜索策略,给出了一种基于混沌优化技术的混合粒子群算法.仿真实验验证了所提出算法的可行性和有效性.     

模糊环境下的差异作业单机批调度优化问题的研究*

针对现实生产制造系统中存在的时间参数模糊化问题,本文用梯形模糊数表征时间参数,给出了一种具有模糊加工时间和模糊批次间隔的、以最小化制造跨度为目标的模糊差异作业单机批调度问题模型。在对模糊差异作业单机批调度问题进行有效求解方面,针对基本粒子群算法容易陷入局部最优的问题,本文给出了一种基于遗传操作的混合粒子群算法,利用遗传算法思想对粒子进行交叉、变异操作,增强了算法跳出局部最优的能力。仿真实验验证了该算法具有可行性和有效性。     

The unbounded single machine parallel batch scheduling problem with family jobs and release dates to minimize makespan

In this paper we consider the unbounded single machine parallel batch scheduling problem with family jobs and release dates to minimize makespan. We show that this problem is strongly NP-hard, and give an O(n(n/m+1)^m) time dynamic programming algorithm and an O(mk^k+1P^2k−1) time dynamic programming algorithm, where n is the number of jobs, m is the number of families, k is the number of distinct release dates and P is the sum of the processing times of all families. We further give a heuristic with a performance ratio 2. We also give a polynomial-time approximation scheme for the problem.     

Flow shop scheduling to minimize makespan with decreasing time-dependent job processing times

In this study, we consider an n-job, m-machine flow shop scheduling problem with decreasing time-dependent job processing times. By the decreasing time-dependent job processing times, we mean that the processing time is a decreasing function of its execution starting time. When some dominant relationships between m − 1 machines can be satisfied, we show that the makespan minimization problem can be solved in polynomial time.     

A branch and bound algorithm for minimizing total completion time on a single batch machine with incompatible job families and dynamic arrivals

In this paper, we consider a single batch machine scheduling problem with incompatible job families and dynamic job arrivals. The objective is to minimize the total completion time. This problem is known to be strongly NP-hard. We present several dominance properties and two types of lower bounds, which are incorporated to construct a basic branch and bound algorithm. Furthermore, according to the characteristics of dynamic job arrivals, a decomposed branch and bound algorithm is proposed to improve the efficiency. The proposed algorithms are tested on a large set of randomly generated problem instances.     

Scheduling linear deteriorating jobs to minimize makespan with an availability constraint on a single machine

The scheduling problem with deteriorating jobs to minimize the makespan on a single machine where the facility has an availability constraint is studied in this paper. By a deteriorating job we mean that the processing time for the job is a function of its starting time. Even with the introduction of the availability to a facility, the linear deteriorating model can be solved using the 0-1 integer programming technique if the actual job processing time is proportional to the starting time.