Job scheduling and management of wearing tools with stochastic tool lifetimes

The problem of scheduling jobs using wearing tools is studied. Tool wearing is assumed to be stochastic and the jobs are processed in one machining centre provided with a limited capacity tool magazine. The aim is to minimize the expected average completion time of the jobs by choosing their processing order and tool management decisions wisely. All jobs are available at the beginning of the planning period. This kind of situation is met in production planning of CNC-machines. Previous studies concerning this problem have either assumed deterministic wearing for the tools or omitted the wearing completely. In our formulation of the problem, tool wearing is stochastic and the problem becomes very hard to solve analytically. A heuristic based on genetic algorithms is therefore given for the joint problem of job scheduling and tool management. The algorithm searches the most beneficial job sequence when the tool management decisions are made by a removal rule taking into account the future planned usage of the tools. The cost of each job sequence is evaluated by simulating the job processing. Empirical tests with heuristics indicate that by taking the stochastic information into account, one can reduce the average job processing time considerably.     

Sequencing and scheduling of job and tool in a flexible manufacturing system using ant colony optimization algorithm

Many optimization problems from the manufacturing systems are very complex in nature and quite hard to solve by conventional optimization techniques. The theme of this paper is to generate an active schedules and optimal sequence of job and tool that can meet minimum makespan schedule for the flexible manufacturing system. It consists of similar work center which is capable of doing many operations. The tools are stored in a common tool magazine that shares with and serves for several work centers to reduce the cost of duplicating tools in each and every work center. This type of manufacturing system is used for a manufacturing environment in which tools are expensive. To achieve the objective, the jobs and tools are sequenced and scheduled. In this work, non-traditional optimization technique such as ant colony optimization (ACO) algorithm are proposed to derive near-optimal solutions which adopt the Extended Giffler and Thompson algorithm for active feasible schedule generation. In this paper, the proposed algorithm is used for solving number of problems taken from the literature. The results available for the various existing algorithms are compared with results obtained by the ACO algorithm. The analysis reveals that ACO algorithm provides better solution with reasonable computational time.     

Combined column generation and constructive heuristic for a proportionate flexible flow shop scheduling

In a proportionate flow shop problem, jobs have to be processed through a fixed sequence of machines, and processing time for each job is equal on all machines. Such a problem has seldom been tackled. Proportionate flexible flow shop (PFFS) scheduling problems combine the properties of proportionate flow shop scheduling problems and parallel machine scheduling problems. This study presents a combined approach based on column generation (CG) for a PFFS problem with the criterion to minimize the objective of the total weighted completion time (TWCT). Minimizing TWCT in a PFFS problem significantly differs from the parallel-identical-machine scheduling problem, an optimal schedule in which jobs on each machine are in the weighted shortest processing time (WSPT) order. This combined approach adopts a CG approach to effectively handle job assignments to machines, and a constructive heuristic to obtain an optimal sequence for a single machine. Experimental results show the effectiveness of the combined approach in obtaining excellent quality solutions in a reasonable time, especially for large-scale problems.     

Algorithms for flexible flow shop problems with unrelated parallel machines, setup times, and dual criteria

In textile industries, production facilities are established as multi-stage production flow shop facilities, where a production stage may be made up of parallel machines. This known as a flexible or hybrid flow shop environment. This paper considers the problem of scheduling n independent jobs in such an environment. In addition, we also consider the general case in which parallel machines at each stage may be unrelated. Each job is processed in ordered operations on a machine at each stage. Its release date and due date are given. The preemption of jobs is not permitted. We consider both sequence- and machine-dependent setup times. The problem is to determine a schedule that minimizes a convex combination of makespan and the number of tardy jobs. A 0–1 mixed integer program of the problem is formulated. Since this problem is NP-hard in the strong sense, we develop heuristic algorithms to solve it approximately. Firstly, several basic dispatching rules and well-known constructive heuristics for flow shop makespan scheduling problems are generalized to the problem under consideration. We sketch how, from a job sequence, a complete schedule for the flexible flow shop problem with unrelated parallel machines can be constructed. To improve the solutions, polynomial heuristic improvement methods based on shift moves of jobs are applied. Then, genetic algorithms are suggested. We discuss the components of these algorithms and test their parameters. The performance of the heuristics is compared relative to each other on a set of test problems with up to 50 jobs and 20 stages.     

A beam-search-based algorithm for the tool switching problem on a flexible machine

The tool switching problem is used to determine a job sequence and the tools to be loaded on a machine with the objective of minimising the total number of tool switches. In this paper, in order to develop a practical and efficient approach to solving this problem, a beam-search-based algorithm is introduced to formulate the solution space of the problem. The performance of the heuristic algorithm is compared with the heuristic developed by Bard. The proposed algorithm is then tested on some random test problems. The results show that the beam-search-based algorithm performs well in terms of computational efficiency and solution quality.     

A hybrid discrete firefly algorithm for multi-objective flexible job shop scheduling problem with limited resource constraints

In this paper, a hybrid discrete firefly algorithm is presented to solve the multi-objective flexible job shop scheduling problem with limited resource constraints. The main constraint of this scheduling problem is that each operation of a job must follow a process sequence and each operation must be processed on an assigned machine. These constraints are used to balance between the resource limitation and machine flexibility. Three minimisation objectives—the maximum completion time, the workload of the critical machine and the total workload of all machines—are considered simultaneously. In this study, discrete firefly algorithm is adopted to solve the problem, in which the machine assignment and operation sequence are processed by constructing a suitable conversion of the continuous functions as attractiveness, distance and movement, into new discrete functions. Meanwhile, local search method with neighbourhood structures is hybridised to enhance the exploitation capability. Benchmark problems are used to evaluate and study the performance of the proposed algorithm. The computational result shows that the proposed algorithm produced better results than other authors’ algorithms.     

Unrelated parallel machine scheduling with secondary resource constraints

This paper considers unrelated parallel machine scheduling with secondary resource constraints. There are n jobs, each needing to be processed on one of the fitted machines. A setup that includes detaching one die and attaching another from the fitted die type is incurred if the type of job scheduled is different from the last job on that machine. For each kind of die type, the number of dies available is limited. Due to the mechanical structure of the machines, the processing time of a job depends on the machine on which the job is processed, and some jobs are restricted to be processed only on certain machines. In this paper, a heuristic with a capability relative to a runtime and solution quality is developed to minimise the makespan. The performance of the presented heuristic is evaluated through extensive computational experiments. Computational results show that the presented heuristic outperforms the search method tested. It is expected that this research can be applied in industry where unrelated parallel machines are used to process different components and setups for auxiliary equipments are required.     

Adaptation of the simulated annealing optimization algorithm to achieve improved near-optimum objective function values and computation times for multiple component manufacture

The paper concerns the development of the Simulated Annealing Algorithm (SAA) for the sequencing of cutter tool movement in machine tools capable of manufacturing many components, located on a box-like jig/pallet, in a single setting using a multiple tool magazine. The objective of the SAA is to minimise the total machine tool residence time. The general SAA has been enhanced, to achieve lower values of the objective function during the iterative scheme, and hence improve solution accuracy; and, to reduce computation time by cessation of the iterative scheme when no further improvement in the objective function occurs. The reconfigured SAA has been evaluated using a number of case studies. The results show that a reduction in the objective function value can be achieved in up to 6%, with far less computational effort. In addition, it is shown that the computation time can be reduced by a factor of between 20% and 72%. The improvement in the objective function value and the computational speed depends on the complexity of the problem posed to the SAA software.     

具有柔性加工路径的作业车间批量调度优化研究

古典作业车间调度问题已经被研究了几十年并证明为 NP- hard问题。柔性作业车间调度是古典作业车间调度问题的扩展 ,它允许工序可以由一个机床集合中的多台机床完成加工 ,调度的目的是将工序分配给各机床 ,并对各机床上的工序进行排序以使完成所有工序的时间最小化。本文采用遗传算法进行柔性作业车间调度研究 ,针对柔性作业车间问题提出了一种新颖直观的基因编码方法以适用于批量调度 ,并分析了几种批量调度方案 ,最后给出了这些调度的仿真结果 ,证明单件最佳调度不适合扩展成批量最佳调度     

双目标函数下需要安装时间的平行多功能机排序问题

讨论了双目标函数下需要安装时间的平行多功能机排序问题。在该问题中,每个工件对应机器集合的一个子集,且每个工件只能在相应子集中的任一台机器上加工,工件分组,不同组中的工件连续加工需要安装时间,目标函数为极小化最大完工时间和安装次数。根据实际应用背景确定双目标排序问题的形式,并证明了该问题是NP—难的。设计了一个求启发式有效解的算法,首先按照特定的规则将所有工件组都整组地安排到各台机器上,然后逐步改进最大完工时间和拆分工件组,从而得到一系列的启发式有效解。实验表明,该算法是实用而有效的。     

Minimizing total weighted tardiness on heterogeneous batch processing machines with incompatible job families

This paper addresses a specific class of scheduling parallel batching problem, which is observed in steel casting industries. The focus of this research is to minimize the total weighted tardiness on heterogeneous batch processing machines under conditions of dynamic job arrivals, incompatible job families and non-identical job sizes. This type of parallel batching problem arises in a number of different settings, including diffusion in wafer fabrication, heat treatment operations in aircraft industries, and metal working. The problem is viewed as a three stage-decision-problem: the first stage involves selecting a machine from the heterogeneous batch processing machines for scheduling; the second stage involves the selection of a job family from the available incompatible job families; and the third stage involves the selection of a set of jobs to create a batch from the selected job family based on the capacity of the selected batch-processing machine. Since the problem is NP-hard, a few greedy heuristics are proposed. The computational experiments show that the proposed greedy heuristic algorithms are capable of consistently obtaining near-optimal solutions (statistically estimated) in very reasonable computational time on a Pentium III 650 Mz with 128 MB RAM.     

Minimizing total weighted tardiness on heterogeneous batch processing machines with incompatible job families

This paper addresses a specific class of scheduling parallel batching problem, which is observed in steel casting industries. The focus of this research is to minimize the total weighted tardiness on heterogeneous batch processing machines under conditions of dynamic job arrivals, incompatible job families and non-identical job sizes. This type of parallel batching problem arises in a number of different settings, including diffusion in wafer fabrication, heat treatment operations in aircraft industries, and metal working. The problem is viewed as a three stage-decision-problem: the first stage involves selecting a machine from the heterogeneous batch processing machines for scheduling; the second stage involves the selection of a job family from the available incompatible job families; and the third stage involves the selection of a set of jobs to create a batch from the selected job family based on the capacity of the selected batch-processing machine. Since the problem is NP-hard, a few greedy heuristics are proposed. The computational experiments show that the proposed greedy heuristic algorithms are capable of consistently obtaining near-optimal solutions (statistically estimated) in very reasonable computational time on a Pentium III 650 Mz with 128 MB RAM.     

A general flow shop scheduling problem with consideration of position-based learning effect and multiple availability constraints

In this paper, a more general version of the flow shop scheduling problem with the objective of minimizing the total flow time is investigated. In order to get closer to the actual conditions of the problem, some realistic assumptions including non-permutation scheduling, learning effect, multiple availability constraints, and release times are considered. It is assumed that the real processing time of each job on a machine depends on the position of that job in the sequence, and after processing a specified number of jobs at each machine, an unavailability period is occurring because of maintenance activities. Moreover, it is supposed that each job may not be ready for processing at time zero and may have a release time. According to these assumptions, a new mixed integer linear programming (MILP) model is proposed to formulate the problem. Due to the high complexity of the problem, a heuristic method and a simulated annealing algorithm are presented to find the nearly optimal solutions for medium- and large-sized problems. To obtain better and more robust solutions, the Taguchi method is used in order to calibrate the simulated annealing algorithm parameters. Finally, the computational results are provided for evaluating the performance and effectiveness of the proposed solution methods.     

Minimizing total flow time on a single flexible machine

In this study, we address a job sequencing and tool switching problem arising in flexible manufacturing systems. We consider the single machine problem of minimizing total flow time. We prove that the problem is NP-hard in the strong sense and show that the tool switching problem is polynomially solvable for a given sequence.We propose a branch-and-bound algorithm whose efficiency is improved by precedence relations and several lower and upper bounding techniques. Our computational results reveal that the branch and bound approach produces optimal solutions in reasonable times for moderate sized problems. Our upper bounds produce very satisfactory solutions; therefore they can be an attractive alternative to solve larger sized problems.     

Flexible job shop scheduling with tabu search algorithms

This paper presents a tabu search algorithm that solves the flexible job shop scheduling problem to minimize the makespan time. As a context for solving sequencing and scheduling problems, the flexible job shop model is highly complicated. Alternative operation sequences and sequence-dependent setups are two important factors that frequently appear in various manufacturing environments and in project scheduling. In this paper, we present a model for a flexible job shop scheduling problem while considering those factors simultaneously. The purpose of this paper is to minimize the makespan time and to find the best sequence of operations and the best choice of machine alternatives, simultaneously. The proposed tabu search algorithm is composed of two parts: a procedure that searches for the best sequence of job operations, and a procedure that finds the best choice of machine alternatives. Randomly generated test problems are used to evaluate the performance of the proposed algorithm. Results of the algorithm are compared with the optimal solution using a mathematical model solved by the traditional optimization technique (the branch and bound method). After modeling the scheduling problem, the model is verified and validated. Then the computational results are presented. Computational results indicate that the proposed algorithm can produce optimal solutions in a short computational time for small and medium sized problems. Moreover, it can be applied easily in real factory conditions and for large size problems. The proposed algorithm should thus be useful to both practitioners and researchers.     

Loading algorithms for flexible manufacturing systems with partially grouped unrelated machines and additional tooling constraints

This paper considers the loading problem for flexible manufacturing systems with highly flexible partial machine grouping, i.e., machines are tooled differently, but each operation can be assigned to multiple machines. Loading is the problem of allocating operations and their associated cutting tools to machines for a given set of parts. As an extension of the existing studies, we consider unrelated machines, i.e., processing time of an operation depends on the speed of the machine to which it is allocated, and dedicated machines, i.e., certain part types must be processed on a specific machine. Also, we consider the constraints associated with cutting tools: (a) tool life restrictions and (b) number of available tool copies. An integer linear programming model is suggested for the objective of balancing the workloads assigned to machines and then due to the complexity of the problem, we suggest two-stage heuristics in which an initial solution is obtained using modified bin-packing algorithms and then it is improved by a simple search technique. The two-stage heuristics suggested in this study were tested on various test instances, and the results show that they can give reasonable quality solutions within a very short amount of computation time. Also, a sensitivity analysis was done on the tightness of the tooling constraints, and the results are reported.     

Heuristics for makespan minimization on parallel batch processing machines with unequal job ready times

This research aims at minimizing the makespan of a set of identical batch processing machines arranged in parallel. Each job is defined by its processing time, ready time, and size. Each machine can process several jobs simultaneously as long as the machine capacity is not exceeded. The batch processing and ready times depend upon the batch composition. The batch processing time is equal to the longest processing job in the batch, and the batch ready time is equal to the largest ready time among those jobs in the batch. The problem under study is NP-hard. Consequently, a constructive heuristic is proposed and its performance with respect to solution quality and computational cost is compared against other solution approaches found in the literature. The computational experiments on a set of randomly generated instances show that the performance of the proposed heuristic is competitive with respect to solution quality and requires little computational cost.     

Scheduling on unrelated parallel machines with sequence- and machine-dependent setup times and due-date constraints

We consider the unrelated parallel-machine scheduling problem with sequence- and machine-dependent setup times and due-date constraints. There are N jobs, each having a due date and requiring a single operation on one of the M machines. A setup is required if there is a switch from processing one type of job to another. Due to the characteristics of machines, the processing time depends upon the job and machine on which the job is processed, and the setup time is sequence and machine dependent. In addition, certain jobs have strict due-date constraints. An effective heuristic based on a modified apparent-tardiness-cost-with-setup procedure, the simulated annealing method, and designed improvement procedures is proposed to minimize the total tardiness of this scheduling problem. Computational characteristics of the proposed heuristic are evaluated through an extensive experiment using a newly created data set. Computational results show that the proposed heuristic is able to effectively improve the initial solutions, obtained by a modified apparent-tardiness-cost-with-setup procedure, and obtains better results than a random descent heuristic.     

考虑关键件加工质量的双资源约束车间调度算法

在工人异质性和机床类型多样的资源约束型车间中,针对资源抢占使加工质量向非关键件倾斜从而导致关键件加工质量无法保障的情况,建立了以完工时间为主要优化目标,以关键件加工质量、整体加工质量为辅助优化目标的双资源(工人/机床)约束柔性作业车间调度问题模型,并提出一种两级嵌套蚁群算法。首先采用工件候选集、资源候选集生成满足关键件加工要求的可行调度解;然后为工序寻找更合适的开工时间,针对机床类型、人机时窗差异设计了基于时窗的活动调度策略以提高算法的局部寻优能力;进而提出了一种保质策略,使关键件和总体工件加工质量水平持续提高;最后,通过算例测试验证了保质策略和两级嵌套蚁群算法的有效性。     

A modified shifting bottleneck heuristic for the reentrant job shop scheduling problem with makespan minimization

This paper proposes a modified shifting bottleneck heuristic (MSBH) for the reentrant job shop scheduling problem (RJSSP) with makespan minimization objective. Recently, the reentrant job shop has come into prominence as a new type of manufacturing shop. The principle characteristic of a reentrant job shop is that a job may visit certain machines more than once during the process flow, whereas in the classic job shop, each job visits a machine only once. The shifting bottleneck heuristic (SBH) is one of the most successful heuristic approaches for the classical job shop scheduling problem, which decomposes the problem into a number of single-machine subproblems. This paper adapts the SBH for the RJSSP and proposes a new sequencing heuristic for the single-machine maximum lateness subproblem considering the reentrant jobs in order to handle large-size RJSSPs. It also uses a subproblem criticality measure that further shortens the implementation time. The proposed MSBH is tested by using instances up to 20 machines and 100 jobs, and it is illustrated that good quality solutions can be obtained in reasonable computational times. A real-life application of the MSBH is also given as a case study to evaluate its performance.