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.     

Cell loading and family scheduling for jobs with individual due dates to minimise maximum tardiness

This paper focuses on cell loading and family scheduling in a cellular manufacturing environment. The performance measure is minimising the maximum tardiness of jobs. What separates this study from others is the presence of individual due dates for every job in a family and also allowing family splitting among cells. Three methods are examined in order to solve this problem, namely mathematical modelling, genetic algorithms (GA) and heuristics. The results showed that GA is capable of finding the optimal solution with varying frequency of 60–100% and it is efficient as compared to the mathematical modelling especially for larger problems in terms of execution times. The heuristics, on the other hand, were easy to implement but they could not find the optimal solution. The results of experimentation also showed that family splitting was observed in all multi-cell optimal solutions and therefore it can be concluded that family splitting is a good strategy for the problem considered in this paper.     

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.     

New scheduling algorithms and digital tool for dynamic permutation flowshop with newly arrived order

The permutation flowshop scheduling problem has been widely studied under static environment by assuming machines and jobs are available at the time of zero. However, in reality, new orders arrive at production systems randomly, which leads to sheer complexity in scheduling due to the dynamic changes given various constraints of resources. Previous studies simply attach new orders directly after the existing schedule. Recent study shows mixing jobs of old and new orders could result in better scheduling solutions. But the heuristic algorithms are still lacking to implement the job mixing policy. To address this problem, a novel scheduling strategy is herein proposed by integrating match-up strategy and real-time strategy (MR) in order to make use of the remaining time before the old order due date. Based on the new MR strategy, eleven new heuristics are introduced with ten existing and one new priority rules. Computational results illustrate the effectiveness of the new heuristics. A digital tool is developed for ease of application of these heuristics, and it is validated by case studies.     

A scatter search approach to sequence-dependent setup times job shop scheduling

Scheduling jobs on multiple machines is a difficult problem when real-world constraints such as the sequence setup time, setup times for jobs and multiple criteria are used for solution goodness. It is usually sufficient to obtain a near-optimal solution quickly when an optimal solution would require days or weeks of computation. Common scheduling heuristics such as Shortest Processing Time can be used to obtain a feasible schedule quickly, but are not designed for multiple simultaneous objectives. We use a new meta-heuristic known as a scatter search (SS) to solve these types of job shop scheduling problems. The results are compared with solutions obtained by common heuristics, a tabu search, simulated annealing, and a genetic algorithm. We show that by combining the mechanism of diversification and intensification, SS produces excellent results in a very reasonable computation time. The study presents an efficient alternative for companies with a complicated scheduling and production situation.     

A comprehensive analysis of group scheduling heuristics in a job shop cell

This paper describes a broad-based simulation study of the performance of two-stage group scheduling heuristics in a job shop cell. The objective of this study was to examine the direct and interactive effects of a variety of shop factors on the performance of the best, previously reported, group scheduling heuristics. A set of traditional single-stage scheduling heuristics were examined as well. Shop factors considered include: setup to runtime ratio, cell load level and variability of inter-arrival times. An assumption common to group scheduling research which provides for an equal division of the part family into subfamilies is also examined. This is accomplished through the creation of an alternative scenario where the majority of the parts are assigned to one subfamily, i.e. one subfamily dominates the part family population. The effects of set up to runtime ratio and cell load have been examined in previous group scheduling research, but not in conjunction with the inter-arrival time variability factor. Further, no study has examined the impact of subfamily dominance on group scheduling heuristics in a full-scale simulation study. The results indicate that performance comparable to that of the two -stage heuristics can be obtained with the easily implementable single-stage heuristics when factors which lessen the impact of setup times are in place. In particular, the tardiness performance of two-stage scheduling heuristics deteriorates when subfamily dominance is in effect while the single-stage heuristics exhibit dramatic improvements in tardiness performance. Low setup to runtime ratio, shop load, and less variable inter-arrivals all induce dramatic performance gains across all measures among the single-stage heuristics, while yielding only marginal improvement in the performance of the two-stage heuristics. As a result, in many instances when combinations of these factors are in effect, the single-stage heuristics yield similar performance to the two-stage heuristics.     

Scheduling with multiple-job-on-one-processor pattern

Most scheduling literature considers a “one-job-on-one-processor” pattern, which assumes that a processor processes exactly one job at a time. In this paper we consider a new scheduling problem with a “multiple-job-on-one-processor” pattern, where several jobs can be processed by a single processor simultaneously, provided that the total size of the jobs being processed does not exceed the capacity of the processor at any point in time. This problem is motivated by the operation of berth allocation, which is to allocate vessels (jobs) to a berth (processor), where the vessels, if small in dimension, may share the berth with some other vessels for loading/unloading the goods. We consider the problem to minimize the makespan of the schedule. The well-known First-Fit Decreasing heuristic is generalized and applied to several variations of the problem, and the worst-case behavior of the generalized heuristics is studied. Worst-case error bounds are obtained for those models. Computational experiments are conducted to test the heuristics. The results suggest that the heuristics are effective in producing near-optimal solutions.     

Single machine group scheduling with family setups to minimize total tardiness

This paper considers the single machine scheduling problem with independent family (group) setup times where jobs in each family are processed together. A sequence-independent setup is required to process a job from a different family. The objective is to minimize total tardiness. A mixed-integer linear programming model capable of solving small-sized problems is described. In view of the NP-hard nature of the problem, two-phase heuristics including simulated annealing algorithms are proposed to find optimal or near-optimal schedules. Empirical results show that the proposed heuristic algorithms are quite effective in minimizing total tardiness for a single machine group scheduling problem with family setup times.     

Optimisation of flow-shop scheduling with batch processor and limited buffer

This paper deals with a flow-shop scheduling problem with limited intermediate buffer. Jobs are grouped in incompatible job families. Each job has to be processed by a batch processor followed by a discrete processor in the same order. The batch processor can process several jobs simultaneously so that all jobs of the same batch start and complete together. We assume that the capacity of batch processor is bounded. The batch processing time is identical for batches of the same family. A batch which has completed processing on the batch processor may block the processor until there is a free unit in the buffer. The objective is to determine a batching and scheduling for all jobs so as to minimise mean completion time. A lower bound and two heuristics algorithm are developed. Moreover, a two-stage method embedded with a Differential Evolution (DE) algorithm is also developed. DE is one of the latest evolutionary computation algorithms, which implements mutation, crossover, and selection operators to improve the candidate solutions iteratively. Three variants of DE are first compared with a continuous Genetic Algorithm employing the random key representation. Then, one variant of the DE with the best convergence speed is selected. Numerical experiments are conducted to evaluate the performances of the selected two-stage meta-heuristic and two heuristics.     

Bottleneck-based heuristics to minimize tardy jobs in a flexible flow line with unrelated parallel machines

This paper develops new bottleneck-based heuristics with machine selection rules to solve the flexible flow line problem with unrelated parallel machines in each stage and a bottleneck stage in the flow line. The objective is to minimize the number of tardy jobs in the problem. The heuristics consist of three steps: (1) identifying the bottleneck stage; (2) scheduling jobs at the bottleneck stage and the upstream stages ahead of the bottleneck stage; (3) using dispatching rules to schedule jobs at the downstream stages behind the bottleneck stage. A new approach is developed to find the arrival times of the jobs at the bottleneck stage, and two decision rules are developed to schedule the jobs on the bottleneck stage. This new approach neatly overcomes the difficulty of determining feasible arrival times of jobs at the bottleneck stage. In order to evaluate the performance of the proposed heuristics, six well-known dispatching rules are examined for comparison purposes. Six factors are used to design 729 production scenarios, and ten test problems are generated for each scenario. Computational results show that the proposed heuristics significantly outperform all the well-known dispatching rules. An analysis of the experimental factors is also performed and several interesting insights into the heuristics are discovered.     

A bounded-search iterated greedy algorithm for the distributed permutation flowshop scheduling problem

As the interest of practitioners and researchers in scheduling in a multi-factory environment is growing, there is an increasing need to provide efficient algorithms for this type of decision problems, characterised by simultaneously addressing the assignment of jobs to different factories/workshops and their subsequent scheduling. Here we address the so-called distributed permutation flowshop scheduling problem, in which a set of jobs has to be scheduled over a number of identical factories, each one with its machines arranged as a flowshop. Several heuristics have been designed for this problem, although there is no direct comparison among them. In this paper, we propose a new heuristic which exploits the specific structure of the problem. The computational experience carried out on a well-known testbed shows that the proposed heuristic outperforms existing state-of-the-art heuristics, being able to obtain better upper bounds for more than one quarter of the problems in the testbed.     

Scheduling a flow-line manufacturing cell: a tabu search approach

The performance of two heuristic procedures for the scheduling of a flow-line manufacturing cell was compared. We propose a procedure based on a combinatorial search technique known as tabu search. The new procedure is compared with a heuristic based on simulated annealing which was proposed in earlier research. The scheduling problem addressed here differs from the traditional flow-shop scheduling problem in the sense that we are interested in sequencing part families (i.e. groups of jobs which share a similar setup) as well as individual jobs within each family. The results reveal that the tabu search heuristic outperforms the simulated annealing heuristic by generating 'better solutions' in less computation time.     

Scheduling parallel batch processing machines with arbitrary job sizes and incompatible job families

Motivated by a bottleneck operation in an MLCC (multi-layer ceramic capacitor) production line, we study the scheduling problem of parallel batch processing machines in which a number of jobs can be processed simultaneously in a machine as a batch. Volumes of the jobs are different from each other and each job belongs to the family in which all jobs have the same processing time. In this situation, we analyse three kinds of problems whose performance measures are makespan, total completion time, and total weighted completion time, respectively. Since these problems are known to be NP-hard, we propose a number of heuristics and design genetic algorithms for the problems. Through some computational experiments, we evaluate the performances of the heuristic algorithms proposed, including the genetic algorithms for each of three problems.     

A general framework for scheduling equipment and manpower at container terminals

In this paper, we propose a general model for various scheduling problems that occur in container terminal logistics. The scheduling model consists of the assignment of jobs to resources and the temporal arrangement of the jobs subject to precedence constraints and sequence-dependent setup times. We demonstrate how the model can be applied to solve several different real-world problems from container terminals in the port of Hamburg (Germany). We consider scheduling problems for straddle carriers, automated guided vehicles (AGVs), stacking cranes, and workers who handle reefer containers. Subsequently, we discuss priority rule based heuristics as well as a genetic algorithm for the general model. Based on a tailored generator for experimental data, we examine the performance of the heuristics in a computational study. We obtain promising results that suggest that the genetic algorithm is well suited for application in practice.     

A heuristic for scheduling in flowshop and flowline-based manufacturing cell with multi-criteria

The problem of scheduling in flowshop and flowline-based manufacturing cell is considered with the bicriteria of minimizing makespan and total flowtime of jobs, The formulation of the scheduling problems for both the flowshop and the flowline-based manufacturing cell is first discussed. We then present the development of the proposed heuristic for flowshop scheduling. A heuristic preference relation is developed as the basis for the heuristic so that only the potential job interchanges are checked for possible improvement with respect to bicriteria, The proposed heuristic algorithm as well as the existing heuristic are evaluated in a large number of randomly generated large-sized flowshop problems. We also investigate the effectiveness of these heuristics with respect to the objective of minimizing total machine idletime. We then modify the proposed heuristic for scheduling in a cell, and evaluate its performance.     

Evaluating scheduling heuristics for non-identical parallel processors

Job allocation and job sequencing decisions are combined to develop scheduling heuristics for non-identical parallel processor systems. Several factors affecting the system are examined and the relative performance of the heuristics are evaluated in terms of flow time, tardiness and proportion of tardy jobs. An understanding of the relationship between variables in a scheduling system leads to decision rules that provide feasible and effective production schedules.     

An evaluation of group scheduling heuristics in a flow-line manufacturing cell

When a company adopts cellular manufacturing and creates a cell, one operational problem that must be addressed is how to schedule parts within the cell. Many studies have investigated scheduling rules in a cellular manufacturing environment. However, there has been little consensus on the best scheduling rule to use. To address this lack of consensus, this study evaluated the best scheduling rules from most of these studies in a flow-line cell. The impact of two environmental factors, setup to runtime ratio and number of part families, was also investigated. Out of the five best scheduling rules found, three of these had not been investigated in previous group scheduling studies. The scheduling rule that most often performed best was selecting the part family with the most waiting jobs and sequencing these jobs in shortest processing time order, a relatively simple rule. The more complex rules generally showed poorer performance.     

Solving the n-job 3-stage flexible flowshop scheduling problem using an agent-based approach

In this paper, a general methodology of agent-based manufacturing systems scheduling, incorporating game theoretic analysis of agent cooperation is presented to solve the n-job 3-stage flexible flowshop scheduling problem. The flowshops are flexible in the sense that a job can be processed by any of the identical machines at each stage. Our objective is to schedule a set of n jobs so as to minimize the makespan. We perform error bound analysis using the lower bound estimates developed in the literature as a datum for comparing the agent-based scheduling solutions with other heuristic solutions. The results of the evaluation show that the agent-based scheduling approach outperforms existing heuristics for the majority of the testing problems.     

Scheduling with controllable processing times and compression costs using population-based heuristics

This paper considers the single machine scheduling problem of jobs with controllable processing times and compression costs and the objective to minimise the total weighted job completion time plus the cost of compression. The problem is known to be intractable, and therefore it was decided to be tackled by population-based heuristics namely differential evolution (DE), particle swarm optimisation (PSO), genetic algorithms (GAs), and evolution strategies (ES). Population-based heuristics have found wide application in most areas of production research including scheduling theory. It is therefore surprising that this problem has not yet received any attention from the corresponding heuristic algorithms community. This work aims at contributing to fill this gap. An appropriate problem representation scheme is developed together with a multi-objective procedure to quantify the trade-off between the total weighted job completion time and the cost of compression. The four heuristics are evaluated and compared over a large set of test instances ranging from five to 200 jobs. The experiments showed that a differential evolution algorithm is superior (with regard to the quality of the solutions obtained) and faster (with regard to the speed of convergence) to the other approaches.     

A genetic algorithm based approach for scheduling of jobs containing multiple orders in a three-machine flowshop

This paper investigates a new scheduling problem of multiple orders per job (MOJ) in a three-machine flowshop consisting of an item-processing machine, a lot-processing machine and a batch-processing machine, for a semiconductor manufacturing operation that must form a layer on the wafers. The three-machine flowshop MOJ scheduling problem deals with sequencing customer orders, assigning orders to jobs, and then combining the formed jobs into batches. Genetic algorithms are presented for this scheduling problem to minimise the total weighted tardiness (TWT), in the presence of non-zero order ready times, different order due dates, different order weights and unequal order sizes. Extensive experiments were performed to compare the proposed genetic algorithm (GA)-based approach with the benchmark heuristics presented in previous studies. The experiments led to the conclusions that the GA-based approach is significantly superior over other heuristics in terms of TWT and can find near-optimal solutions in an acceptable amount of computation time.