Ant colony optimisation algorithms for two-stage permutation flow shop with batch processing machines and nonidentical job sizes

This paper focuses on minimising the maximum completion time for the two-stage permutation flow shop scheduling problem with batch processing machines and nonidentical job sizes by considering blocking, arbitrary release times, and fixed setup and cleaning times. Two hybrid ant colony optimisation algorithms, one based on job sequencing (JHACO) and the other based on batch sequencing (BHACO), are proposed to solve this problem. First, max-min pheromone restriction rules and a local optimisation rule are embedded into JHACO and BHACO, respectively, to avoid trapping in local optima. Then, an effective lower bound is estimated to evaluate the performances of the different algorithms. Finally, the Taguchi method is adopted to investigate and optimise the parameters for JHACO and BHACO. The performances of the proposed algorithms are compared with that of CPLEX on small-scale instances and those of a hybrid genetic algorithm (HGA) and a hybrid discrete differential evolution (HDDE) algorithm on full-scale instances. The computational results demonstrate that BHACO outperforms JHACO, HDDE and HGA in terms of solution quality. Besides, JHACO strikes a balance between solution quality and run time.     

A multi-objective flow shop scheduling with resource-dependent processing times: trade-off between makespan and cost of resources

In traditional flow shop scheduling problems (FSSPs), the processing times are assumed to be pre-known and fixed parameters while in many practical environments, the processing times can be controlled by consumption of extra resources. In this paper, we propose resource-dependent processing times (RDPT) for permutation FSSP in which the processing time of a job depends on the amount of additional resources assigned to that job. To make a trade-off between makespan and required amount of resources, two conflict objective functions are considered: the minimisation of maximum completion time and the minimisation of total cost of resources. In order to solve the problem considered in this paper, a decomposition approach is suggested that strives to deal with the original model via two sub-problems: (i) sequencing problem; and (ii) resource allocation problem. A hybrid discrete differential evolution (HDDE) algorithm with an effective coordinate directions search and a variable neighbourhood search (VNS) are combined to solve two sub-problems. Furthermore, a statistical procedure is employed to adjust the significant parameters of the proposed HDDE and VNS algorithms. This procedure is based on the stepwise regression (SR) technique. The effectiveness of the suggested hybrid algorithm is investigated through a computational study and obtained results show the good performance of our approach with regard to the other algorithms.     

Determination of an optimal common due date and optimal sequence in a single machine job shop

In this paper we consider an n jobs one machine sequencing problem in which all jobs have a common due date and a deviation in its completion time occurs when a job is completed before or after the common due date. The objective is to find an optimal value of this common due date and a corresponding optimal sequence such that the mean absolute deviation of the completion times of the jobs in the optimal sequence from the corresponding optimal common due date is at its global minimum. Starting with an arbitrary sequence we relate the problem to a generalized linear goal program from which some basic results are proved using elementary properties of linear equations and a linear goal programming problem. Using these results and the idea of sensitivity analysis in linear programming, an algorithm is developed that determines the optimal due date and the corresponding optimal sequence yielding the global minimum value of the mean absolute deviation of the completion times of the jobs in the optimal sequence from the corresponding optimal common due date. In the end a numerical example to explain the algorithm is provided.     

含不一致任务重量的同型熔炼炉批调度优化

为求解含不一致任务重量的同型熔炼炉批调度问题,建立了最小化最大任务完工时间优化模型,设计了一种混合粒子群算法（HPSO）。算法使用随机生成的任务序列作为粒子,采用批首次匹配（BFF）规则对任务序列分批,最长加工时间（LPT）规则将批分配到批处理机,并提出了一种最小完工时间差（MCD）规则对LPT调度结果进行优化;为避免早熟,算法引入交叉和变异操作搜索最优解。通过仿真实验与SA、GA算法对比,实验结果表明算法具有良好的性能。     

Algorithms with performance guarantees for flow shops with regular objective functions

We consider flow-shop scheduling problems with regular (nondecreasing) objective functions such as the minimization of makespan in the presence of arbitrary precedence constraints, the weighted sum of job completion times in the presence of series-parallel precedence constraints, the discounted total weighted completion time, and the sum of the quadratic job completion times. We present algorithms with tight worst-case performance bounds for all of these problems by utilizing the optimal permutations for the corresponding single-machine problems. We also investigate the asymptotic optimality of our algorithms.     

Multiple machine JIT scheduling: a tabu search approach

This paper presents an approach to solving the multiple machine, non-preemptive, earliness-tardiness scheduling problem with unequal due dates in a flow shop with machine tiers (FMT). In this variant of the flow shop problem, machines are arranged in tiers or groups, and the jobs must visit one machine in each tier. The processing times, machine assignments, and due dates are deterministic and known in advance. The objective is to find a permutation schedule that minimizes the total deviation of each job from its due date. A tabu search (TS) meta-heuristic combined with an LP evaluation function is applied to solve this problem and results are compared to optimal permutation solutions for small problems and the earliest due date schedule for large problems. Several neighborhood generation methods and two diversification strategies are examined to determine their effect on solution quality. Results show that the TS method works well for this problem. TS found the optimal solution in all but one of the small problem instances and improved the earliest due date solutions for larger instances where no optimal solutions could be found.     

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.     

Jobs and tool sequencing in an automated manufacturing environment

A practical approach is presented for determining the sequence of jobs and tools in the magazine that would be required to process the jobs in an automated manufacturing environment. Each job has to be completed before a given due date. The magazine has a limited capacity necessitating setups which increase the lead times, Processing jobs also requires an appropriate fixture. Setting up a fixture also contributes to the setup times. A heuristic procedure is developed which determines the above sequences while minimizing the total setup and processing times. The performance of the heuristic is checked against optimal solutions for small-size problems while bounds are obtained (based on statistical lower bounding procedures) on the optimal solution for large-size problems. Computational results are provided for 155 test problems.     

Scheduling learning dependent jobs in customised assembly lines

The large variety of product models required by customised markets implies lot size reduction. This strongly affects manual-based production activities, since workers need to promptly adapt to the specifications of the next model to be produced. Completion times of manual-based activities tend to be highly variable among workers, and are difficult to estimate. This affects the scheduling of those activities since scheduling precision depends on reliable estimates of job completion times. This paper presents a method that combines learning curves and job scheduling heuristics aimed at minimising the total weighted earliness and tardiness. Workers performance data is collected and modelled using learning curves, enabling a better estimation of the completion time of jobs with different size and complexity. Estimated completion times are then inputted in new scheduling heuristics for unrelated parallel workers, equivalent to machines in this study, created by modifying heuristics available in the literature. Performance of the proposed heuristics is assessed analysing the difference between the optimal schedule objective function value and that obtained using the heuristics, as well as the workload imbalance among workers. Some contributions in this paper are: (i) use of learning curves to estimate completion times of jobs with different sizes and complexities from different teams of workers; and (ii) use of a more complex scheduling objective function, namely the total weighted earliness and tardiness, as opposed to most of the developments in the current scheduling literature. A shoe manufacturing application illustrates the developments in the paper.     

Two-dimensional phase unwrapping using a hybrid genetic algorithm

A novel hybrid genetic algorithm (HGA) is proposed to solve the branch-cut phase unwrapping problem. It employs both local and global search methods. The local search is implemented by using the nearest-neighbor method, whereas the global search is performed by using the genetic algorithm. The branch-cut phase unwrapping problem [a nondeterministic polynomial (NP-hard) problem] is implemented in a similar way to the traveling-salesman problem, a very-well-known combinational optimization problem with profound research and applications. The performance of the proposed algorithm was tested on both simulated and real wrapped phase maps. The HGA is found to be robust and fast compared with three well-known branch-cut phase unwrapping algorithms.     

A note on minimising total absolute deviation of job completion times on a two-machine no-wait proportionate flowshop

A popular measure used in service systems is that of total absolute deviation of job completion times (TADC). It is relevant to settings where the objective is to balance the level of service provided to different customers. During the last decade, TADC has been studied in various machine settings, and under various assumptions on the job processing times. In this note, we study TADC on a two-machine no-wait proportionate flow shop, i.e. a flow shop with machine-independent processing times, and with no buffer between the machines. A very surprising and unique result is introduced: a simple index policy (the well-known largest processing time (LPT) first sequence) is shown to be optimal for instances of no more than seven jobs. This property does not hold for larger instances. We show that for instances of eight and nine jobs, there are exactly two schedules which are candidates for optimality. For the 10-job instance, the number of candidates increases. This uncommon behaviour of the optimal solution and, consequently, the complexity of the problem studied here, remain open questions, and are challenging topics for future research.     

Single-machine scheduling with deteriorating effects and machine maintenance

In this paper, the single-machine scheduling problems with deteriorating effects and a machine maintenance are studied. In this circumstance, the deterioration rates of the jobs during the machining process are the same which reduces the production efficiency. The actual processing time of the job is a linearly increasing function of the starting time. In this process, the machine only performs a maintenance activity, and the maintenance time is a fixed value. After the maintenance work is completed, the machine will be restored to the initial state, and the deterioration of the job will be start again. The goal is to determine the optimal schedule in order to minimise the maximum completion time (i.e. the makespan) and the sum of job completion times. We prove that both problems are polynomial time solvable, and we also provide the corresponding algorithms.     

Parallel-machine scheduling with controllable processing times and rate-modifying activities to minimise total cost involving total completion time and job compressions

In this paper, we consider unrelated parallel-machine scheduling involving controllable processing times and rate-modifying activities simultaneously. We assume that the actual processing time of a job can be compressed by allocating a greater amount of a common resource to process the job. We further assume that each machine may require a rate-modifying activity during the scheduling horizon. The objective is to determine the optimal job compressions, the optimal positions of the rate-modifying activities and the optimal schedule to minimise a total cost function that depends on the total completion time and total job compressions. If the number of machines is a given constant, we propose an efficient polynomial time algorithm to solve the problem.     

Scheduling algorithms to minimise the total family flow time for job shops with job families

This paper considers the job scheduling problem in which jobs are grouped into job families, but they are processed individually. The decision variable is the sequence of the jobs assigned to each machine. This type of job shop scheduling can be found in various production systems, especially in remanufacturing systems with disassembly, reprocessing and reassembly shops. In other words, the reprocessing shop can be regarded as the job shop with job families since it performs the operations required to bring parts or sub-assemblies disassembled back to like-new condition before reassembling them. To minimise the deviations of the job completion times within each job family, we consider the objective of minimising the total family flow time. Here, the family flow time implies the maximum among the completion times of the jobs within a job family. To describe the problem clearly, a mixed integer programming model is suggested and then, due to the complexity of the problem, two types of heuristics are suggested. They are: (a) priority rule based heuristics; and (b) meta-heuristics. Computational experiments were performed on a number of test instances and the results show that some priority rule based heuristics are better than the existing ones. Also, the meta-heuristics improve the priority rule based heuristics significantly.     

基于规则和仿真的多机并行作业车间生产调度研究

资源分派和能力分派是作业车间生产调度中的重要问题,路径选择规则和分派规则是解决上述问题的有效途径。采用基于规则的仿真研究多机并行作业车间资源分派和能力分派问题,分析工件加工时间、到达率以及机器加工速率对调度结果的影响,以平均完工时间、平均延迟交货率以及平均资源利用率为评价指标,通过对4种路径选择规则和6种分派规则的仿真试验,确定不同性能指标下最佳的调度规则。仿真研究表明:调度规则的选用取决于车间资源配置和调度目标,应避免仅凭借经验或偏好选择规则的调度方法。     

Job shop scheduling with a non-regular objective: A comparison of neighbourhood structures based on a sequencing/timing decomposition

Commercial software packages for production management are characterized by a gap between MRP logic, based on a backward scheduling approach, and finite capacity scheduling, usually based on forward scheduling. In order to partially bridge that gap, we need scheduling algorithms able to meet due dates while keeping WIP and inventory costs low. This leads us to consider job shop scheduling problems characterized by non-regular objective functions; such problems are even more difficult than classical job shop scheduling, and suitable heuristics are needed. One possibility is to consider local search strategies based on the decomposition of the overall problem into sequencing and timing sub-problems. For given job sequences, the optimal timing problem can be solved as a node potential problem on a graph. Since solving the timing problem is a relatively time-consuming task, we need to define a suitable neighbourhood structure to explore the space of job sequences; this can be done by generalizing well-known results for the minimum makespan problem. A related issue is if solving timing problems exactly is really necessary, or if an approximate solution is sufficient; hence, we also consider solving the timing problem approximately by a fast heuristic. We compare different neighbourhood structures, by embedding them within a pure local improvement strategy. Computational experiments show that the overall approach performs better than release/dispatch rules, although the performance improvement depends on the problem characteristics, and that the fast heuristic is quite competitive with the optimal timing approach. On the one hand, these results pave the way to the development of better local search algorithms (based e.g. on tabu search); on the other hand, it is worth noting that the heuristic timing approach, unlike the optimal one, can be extended to cope with the complicating features typical of practical scheduling problems.     

Genetic algorithm with local search for the unrelated parallel machine scheduling problem with sequence-dependent set-up times

In this paper, a genetic algorithm (GA) with local search is proposed for the unrelated parallel machine scheduling problem with the objective of minimising the maximum completion time (makespan). We propose a simple chromosome structure consisting of random key numbers in a hybrid genetic-local search algorithm. Random key numbers are frequently used in GAs but create additional difficulties when hybrid factors are implemented in a local search. The best chromosome of each generation is improved using a local search during the algorithm, but the better job sequence (which might appear during the local search operation) must be adapted to the chromosome that will be used in each successive generation. Determining the genes (and the data in the genes) that would be exchanged is the challenge of using random numbers. We have developed an algorithm that satisfies the adaptation of local search results into the GAs with a minimum relocation operation of the genes’ random key numbers – this is the main contribution of the paper. A new hybrid approach is tested on a set of problems taken from the literature, and the computational results validate the effectiveness of the proposed algorithm.     

A genetic algorithm for solving the economic lot scheduling problem in flow shops

In this study, we propose a hybrid genetic algorithm (HGA) to solve the economic lot scheduling problem in flow shops. The proposed HGA utilizes a so-called Proc PLM heuristic that tests feasibility for the candidate solutions obtained in the evolutionary process of genetic algorithm. When a candidate solution is infeasible, we propose to use a binary search heuristic to ‘fix’ the candidate solution so as to obtain a feasible solution with the minimal objective value. To evaluate the performance of the proposed HGA, we randomly generate a total of 2100 instances from seven levels of utilization rate ranged from 0.45 to 0.80. We solve each of those 2100 instances by the proposed HGA and the other solution approaches in the literature. Our experiments show that the proposed HGA outperforms traditional methods for solving the economic lot scheduling problem in flow shops.     

Scheduling a batch processing machine with non-identical job sizes

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 arbitrary job processing times, job weights and job sizes. The scheduling objective is to minimize total weighted completion time. We find that the procedure returns optimal solutions to problems of up to 25 jobs in reasonable CPU time, and can be adapted for use as a heuristic for larger problems.     

Scheduling job shop problems with sequence-dependent setup times

In this work we consider job shop problems where the setup times are sequence dependent under minimisation of the maximum completion time or makespan. We present a genetic algorithm to solve the problem. The genetic algorithm is hybridised with a diversification mechanism, namely the restart phase, and a simple form of local search to enrich the algorithm. Various operators and parameters of the genetic algorithm are reviewed to calibrate the algorithm by means of the Taguchi method. For the evaluation of the proposed hybrid algorithm, it is compared against existing algorithms through a benchmark. All the results demonstrate that our hybrid genetic algorithm is very effective for the problem.