Minimizing total weighted tardiness on a batch-processing machine with non-agreeable release times and due dates

This study considers the scheduling problem observed in the burn-in operation of semiconductor final testing, where jobs are associated with release times, due dates, processing times, sizes, and non-agreeable release times and due dates. The burn-in oven is modeled as a batch-processing machine which can process a batch of several jobs as long as the total sizes of the jobs do not exceed the machine capacity and the processing time of a batch is equal to the longest time among all the jobs in the batch. Due to the importance of on-time delivery in semiconductor manufacturing, the objective measure of this problem is to minimize total weighted tardiness. We have formulated the scheduling problem into an integer linear programming model and empirically show its computational intractability. Due to the computational intractability, we propose a few simple greedy heuristic algorithms and meta-heuristic algorithm, simulated annealing (SA). A series of computational experiments are conducted to evaluate the performance of the proposed heuristic algorithms in comparison with exact solution on various small-size problem instances and in comparison with estimated optimal solution on various real-life large size problem instances. The computational results show that the SA algorithm, with initial solution obtained using our own proposed greedy heuristic algorithm, consistently finds a robust solution in a reasonable amount of computation time.     

Scheduling identical parallel machines with machine eligibility restrictions to minimize total weighted flowtime in automobile gear manufacturing

In this paper, we address a scheduling problem for minimizing total weighted flowtime, observed in automobile gear manufacturing. Specifically, the bottleneck operation of the pre-heat treatment stage of gear manufacturing process has been dealt with in scheduling. Many real-life scenarios like unequal release times, sequence dependent setup times, and machine eligibility restrictions have been considered. A mathematical model taking into account dynamic starting conditions has been proposed. The problem is derived to be NP-hard. To approach the problem, a few heuristic algorithms have been proposed. Based on planned computational experiments, the performance of the proposed heuristic algorithms is evaluated: (a) in comparison with optimal solution for small-size problem instances and (b) in comparison with the estimated optimal solution for large-size problem instances. Extensive computational analyses reveal that the proposed heuristic algorithms are capable of consistently yielding near-statistically estimated optimal solutions in a reasonable computational time.     

Minimizing total weighted tardiness on heterogeneous batch processors with incompatible job families

In this paper, we address a scheduling problem for minimizing total weighted tardiness. The background for the paper is derived from the automobile gear manufacturing process. We consider the bottleneck operation of heat treatment stage of gear manufacturing. Real-life scenarios like unequal release times, incompatible job families, non-identical job sizes, heterogeneous batch processors, and allowance for job splitting have been considered. We have developed a mathematical model which takes into account dynamic starting conditions. The problem considered in this study is NP-hard in nature, and hence heuristic algorithms have been proposed to address it. For real-life large-size problems, the performance of the proposed heuristic algorithms is evaluated using the method of estimated optimal solution available in literature. Extensive computational analyses reveal that the proposed heuristic algorithms are capable of consistently obtaining near-optimal statistically estimated solutions in very reasonable computational time.     

Heuristics for assembly operation scheduling problem in flexible assembly systems

In this paper we address the problem of scheduling n assembly operations with in-tree constraints on m unrelated parallel workstations in flexible assembly systems, which we call the assembly operation scheduling problem (AOSP). No preemption of assembly operations is allowed and the primary objective is to minimize the maximum completion time. This problem is equivalent to R|tree|C_max. For this notorious NP-hard problem, four heuristic algorithms including decomposition (DECOMP), earliest completion time (ECT), shortest processing time (SPT), and earliest starting time(EST) heuristic are proposed and their performances are comparatively investigated. DECOMP uses a decomposition technique to practically solve this problem. The assembly operation tree is decomposed and then AOSP is reduced to a set of subproblems of R||C_max and R,r_j|r_i|C_max. Two efficient heuristics were proposed for the reduced subproblems. The other three heuristics basically use the machine selection rules to determine the machine for processing the current operation. Of these heuristics, DECOMP showed the best performance in terms of quality of schedule. Computational results show that all the proposed algorithms except the EST heuristic perform quite well in terms of both quality of solution and computation time.     

多工艺路线的批量生产调度优化

以优化生产周期为目标,研究了多工艺路线的批量调度问题,提出了一种基于工序优先级的调度算法,并将该算法嵌入到遗传算法中,得到了全局优化的批量调度算法。遗传算法搜索最佳染色体,调度算法把染色体解码为调度。在调度算法中,采用了3种提高生产率的策略,即区分批量启动时间与工序加工时间,在工件到达机床之前做好准备工作;把一批工件分成多个小生产批次,每批次独立加工:一批工件加工部分后就运向后续加工机床,缩小后续机床的等待时间。仿真表明,该调度方法能取得较好结果。     

Flow shop scheduling with two batch processing machines and nonidentical job sizes

A batch processing machine can process several jobs simultaneously. In this research, we consider the problem of a two-stage flow shop with two batch processing machines to minimize the makespan. We assume that the processing time of a batch is the longest processing time among all the jobs in that batch and the sizes of the jobs are nonidentical. There is a limitation on batch sizes and the sum of job sizes in a batch must be less than or equal to the machine capacity. Since this problem is strongly nondeterministic polynomial time hard, we propose two heuristic algorithms. The first one is knowledge-based and the other is based on the batch first fit heuristic proposed previously. To further enhance the solution quality, two different simulated annealing (SA) algorithms based on the two constructive heuristics is also developed. Since heuristic methods for this problem has not been proposed previously, a lower bound is developed for evaluating the performance of the proposed methods. Several test problems have been solved by SAs and lower bound method and the results are compared. Computational studies show that both algorithms provide good results but the first SA (ARSA) algorithm considerably outperforms the second one (FLSA). In addition, the results of ARSA algorithm, optimal solutions, and lower bounds are compared for several small problems. The comparisons show that except for one instance, the ARSA could find the optimal solutions and the proposed lower bound provides small gaps comparing with the optimal solutions.     

Solution algorithms for the total weighted completion time minimization flow shop scheduling with decreasing linear deterioration

In this paper, we consider a two-machine flow shop scheduling problem with decreasing linear deterioration. By decreasing linear deterioration, we mean that the processing time is a decreasing function of its execution start time. The objective is to find a sequence that minimizes the total weighted completion time. Several dominance properties and some lower bounds are derived to speed up the elimination process of a branch-and-bound algorithm. Two heuristic algorithms are also proposed to overcome the inefficiency of the branch-and-bound algorithm. Computational results for randomly generated problem instances are presented.     

A heuristic algorithm for the just-in-time single machine scheduling problem with setups: a comparison with simulated annealing

This paper addresses the single machine early/tardy problem with unrestricted common due date and sequence-dependent setup times. Two algorithms are introduced to reach near-optimum solutions: the SAPT, a heuristic tailored for the problem, and a simulated annealing (SA) algorithm. It will be shown that SA provides solutions with slightly better quality; however, SAPT requires much less computational time. SAPT-SA is a hybrid heuristic that combines both approaches to obtain high quality solutions with low computational cost. Solutions provided by the three algorithms were compared to optimal solutions for problems with up to 25 jobs and to each other for larger problems.     

Sequencing of an M machine flow shop with setup, processing and removal times separated

In this research, a flow shop scheduling problem in which setup, processing and removal times are separated, with the objective of minimizing makespan, is considered. A tabu search based heuristic is presented for solving the addressed problem. The proposed heuristic begins with the construction of artificial processing times for each operation; then a modified NEH algorithm is used to generate an initial solution, followed by a designed tabu search procedure applied for further improvement of the solution. The proposed heuristic, as well as the existing one, is evaluated in a large number of randomly generated problems. The results of the experimental investigations of the proposed heuristic algorithm and the existing heuristic in meeting the objective of makespan are also reported. It is found that the solution quality of the proposed tabu search heuristic is better than that of the existing heuristic, but for large size problems more computational efforts are needed; however, the CPU time is still acceptable.     

Minimization of total tardiness on unrelated parallel machines with sequence- and machine-dependent setup times under due date constraints

The unrelated parallel machine scheduling problem with sequence- and machine-dependent setup times in the presence of due date constraints represents an important but relatively less-studied scheduling problem in the literature. In this study, a simple iterated greedy (IG) heuristic is presented to minimize the total tardiness of this scheduling problem. The effectiveness and efficiency of the proposed IG heuristic are compared with existing algorithms on a benchmark problem dataset used in earlier studies. Extensive computational results indicate that the proposed IG heuristic is capable of obtaining significantly better solutions than the state-of-the-art algorithms on the same benchmark problem dataset with similar computational resources.     

Development and analysis of constructive heuristic algorithms for flow shop scheduling problems with sequence-dependent setup times

This paper focuses on the problem of determining a permutation schedule for n jobs in an m-machine flow shop that operates in a sequence-dependent setup time (SDST) environment. Two constructive heuristic algorithms are developed with the minimisation of makespan as the objective. The first heuristic algorithm termed as setup ranking algorithm obtains the sequence using the setup times of jobs only. The second heuristic algorithm, fictitious job setup ranking algorithm (FJSRA), is developed using the concept of fictitious jobs. Pairs of jobs with minimum setup time between them constitute the fictitious jobs. Both these algorithms are compared with an existing constructive algorithm. For the purpose of experimentation, Taillard benchmark problems are used to develop SDST benchmark problems at eight different levels of sequence-dependent setup times. Graphical analysis, relative performance index analysis and statistical analysis are carried out on the results obtained for all the eight sets of benchmark problems. The analysis reveals that FJSRA emerges as the better algorithm for larger problems and for smaller problems with higher level of setup time. The results of statistical analysis are used to develop setup time dominance matrix for deciding upon the algorithm to be used for a particular size of problem.     

Single-machine scheduling with controllable processing times and learning effect

In this paper, we consider single-machine scheduling problem with controllable processing times and learning effect, i.e., processing times of jobs are controllable variables with linear costs and also are defined as functions of positions in a schedule. We concentrate on two goals separately, namely minimizing a cost function containing makespan, total completion time, total absolute differences in completion times, and total compression cost and minimizing a cost function containing makespan, total waiting time, total absolute differences in waiting times, and total compression cost. The problem is modeled as an assignment problem and thus can be solved with the well-known algorithms.     

Iterated hybrid metaheuristic algorithms for unrelated parallel machines problem with unequal ready times and sequence-dependent setup times

The problem considered in this paper involves a set of independent jobs on unrelated parallel machines with sequence-dependent setup times and unequal ready times, and the objective is to minimize the weighted number of tardy jobs. Iterated hybrid metaheuristic algorithms are proposed to address this problem. The algorithms begin with effective initial solution generators to generate initial feasible solutions; then, hybrid metaheuristics are applied to improve the initial solutions, integrating the principles of the variable neighborhood descent approach and tabu search. If the search becomes trapped at a local optimum, a perturbation operator is developed to help the search escape. To evaluate the performance of the suggested algorithms, heuristic rules and iterated local search algorithms are examined and compared. Computational experimental results show that the proposed algorithms outperform the other heuristics.     

Two bi-directional heuristics for the assembly line type II problem

In this paper, we proposed two heuristic algorithms for solving the assembly line balancing type II problem. The proposed algorithms first generate an initial solution by a bi-directional assignment procedure, then the obtained initial solution is further improved by swapping tasks among workstations. In order to test the performance of the two algorithms, a comparison is carried out on a set of 302 instances found in the literature and a set of 1440 randomly generated instances. The computational results show that the proposed heuristic algorithms for solving the assembly line balancing Type II problem are efficient in minimizing both the cycle time and the mean absolute deviation.     

A genetic algorithm and particle swarm optimization for no-wait flow shop problem with separable setup times and makespan criterion

This paper considers the problem of no-wait flow shop scheduling, in which a number of jobs are available for processing on a number of machines in a flow shop context with the added constraint that there should be no waiting time between consecutive operations of a job. Each operation has a separable setup time, meaning that the setup time of an operation is independent on the previous operations; and the machine can be prepared for a specific operation and remain idle before the operation actually starts. The considered objective function in this paper is the makespan. The problem is proven to be NP-hard. In this paper, two frameworks based on genetic algorithm and particle swarm optimization are developed to deal with the problem. For the case of no-wait flow shop problem without setup times, the developed algorithms are applied to a large number of benchmark problems from the literature. Computational results confirm that the proposed algorithms outperform other methods by improving many of the best-known solutions for the test problems. For the problems with setup time, the algorithms are compared against the famous 2-Opt algorithm. Such comparison reveals the efficiency of the proposed method in solving the problem when separable setup times are considered.     

A drastic hybrid heuristic algorithm to approach to JIT policy considering controllable processing times

Job scheduling has always been a challenging task in modern manufacturing and the most real life scheduling problems which involves multi-criteria, multi-machine environments. In this research, the single-machine scheduling problem is studied in which job processing times are controllable, namely, they may vary within a specified interval. The goal of this research is to minimize total tardiness and earliness on a single machine, simultaneously. In this context, we first propose a mathematical model for the considered problem and then a net benefit compression–net benefit expansion heuristic is presented for obtaining the set of amounts of compression and expansion of jobs processing times in a given sequence. Two meta-heuristic approaches are then employed to solve medium-to-large-sized problems as local search methods. Thereafter, we apply a hybrid method based on our heuristic as well as these two meta-heuristics in order to obtain solutions with higher quality within lesser computational time. The addressed problem is NP-hard since the single machine total tardiness problem is already NP-hard. The computational results show that our proposed heuristics can effectively solve such Just-In-Time problem with a high-quality solution.     

Algorithms for the single machine total weighted completion time scheduling problem with release times and sequence-dependent setups

This paper considers the problem of scheduling n jobs on a single machine to minimize the total weighted completion time in the presence of sequence-dependent setup times and release times. To the best of our knowledge, little research has been devoted to this scheduling problem. Therefore, we developed two exact algorithms, including a constraint programming model and a branch-and-bound method for small problems. The obtained optimal solutions can be used as a benchmark for evaluating the performance of heuristics. With the complexity in mind, two heuristics, including a best index dispatch (BID) and a modified weighted shortest processing time (MWSPT) based on non-delay concepts are also proposed for large problems. The time complexities of the two proposed heuristics are O(n ⁴) and O(n ³), respectively. The computational results showed that the branch-and-bound method could solve most instances with 40 jobs under the time limit of 7,200 s. The BID heuristic is superior to the MWSPT in solution quality, although both can efficiently and effectively obtain near-optimal solutions for large instances.     

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.     

Scheduling jobs on parallel machines: a restricted tabu search approach

Many real scheduling problems are often much more complex than problems that are analytically tractable. The main difficulty in obtaining optimal job schedules arises from the existence of sequence dependent setup times among jobs and job release times. In this paper, we present a restricted tabu search algorithm that schedules jobs on parallel machines in order to minimise the maximum lateness of the jobs. The jobs have release times and due dates, and sequence-dependent setup times exist between the jobs. The parallel machines are either identical or non-identical in terms of the processing times of the jobs. The restricted tabu search algorithm employs a restricted search with the elimination of non-effective job moves, for finding the best neighbourhood schedule. The restricted search algorithm reduces search effort significantly while obtaining good quality final schedule. The experimental results show that the proposed algorithm obtains much better solutions more quickly than other heuristic algorithms such as the Rolling Horizon Procedure (RHP) heuristic, the basic tabu search and simulated annealing.     

A mathematical model and extension algorithm for assembly flexible flow shop scheduling problem

In this paper, a scheduling problem for a two-stage production system including machining operations and assembly operations is studied. In this system, a number of products of different kinds are produced. Each product is assembled with a set of several parts. The first stage is a hybrid flow shop to produce parts. All machines can process all kinds of parts in this stage, but each machine can process only one part at a time. The second stage is a single assembly machine or a single assembly team of workers. The considered objective is to minimize the completion time of all products (makespan). A mathematical modeling is presented, and since this problem has been proved strongly nondeterministic polynomial-time hard, a series of heuristic algorithms based on the basic idea of Johnson algorithm is proposed. Also, two lower bounds is introduced and improved to evaluate the final solution obtained from heuristic algorithms. The numerical experiments are used to evaluate the performance of the proposed algorithms.