Iterated greedy algorithms to minimize the total family flow time for job-shop scheduling with job families and sequence-dependent set-ups

This study addresses a variant of job-shop scheduling in which jobs are grouped into job families, but they are processed individually. The problem can be found in various industrial systems, especially in reprocessing shops of remanufacturing systems. If the reprocessing shop is a job-shop type and has the component-matching requirements, it can be regarded as a job shop with job families since the components of a product constitute a job family. In particular, sequence-dependent set-ups in which set-up time depends on the job just completed and the next job to be processed are also considered. The objective is to minimize the total family flow time, i.e. the maximum among the completion times of the jobs within a job family. A mixed-integer programming model is developed and two iterated greedy algorithms with different local search methods are proposed. Computational experiments were conducted on modified benchmark instances and the results are reported.     

Production sequencing problem with re-entrant work flows and sequence dependent setup times

This paper addresses a shop scheduling problem where a set of n jobs needs to be scheduled on two machines for the side frame press shop in a truck manufacturing company. A most unusual aspect of the problem is that the setup times required for a job in the first machine depend not on the immediately preceding job but on the job which is two steps prior to it. Redefining the job elements, the problem is formulated into a general two machine flow shop problem which can be solved by dynamic programming with the objective of the minimum makespan. An optimal schedule is found utilizing the sequence dominance conditions and the decisiondelay scheme. Since the computational requirements of dynamic programming are impracticably demanding for large-sized problems, a genetic algorithm is developed and its performance is examined through a comparative study.     

A priority scheduling approach for flexible job shops with multiple process plans

This paper considers the job shop scheduling problem with alternative operations and machines, called the flexible job shop scheduling problem. As an extension of previous studies, operation and routing flexibilities are considered at the same time in the form of multiple process plans, i.e. each job can be processed through alternative operations, each of which can be processed on alternative machines. The main decisions are: (a) selecting operation/machine pair; and (b) sequencing the jobs assigned to each machine. Since the problem is highly complicated, we suggest a practical priority scheduling approach in which the two decisions are done at the same time using a combination of operation/machine selection and job sequencing rules. The performance measures used are minimising makespan, total flow time, mean tardiness, the number of tardy jobs, and the maximum tardiness. To compare the performances of various rule combinations, simulation experiments were done on the data for hybrid systems with an advanced reconfigurable manufacturing system and a conventional legacy system, and the results are reported.     

The production capacity of job shops with limited storage space

Suppose the number of jobs which can be stored in front of the machines in a job shop is limited. As a result, arriving jobs for which there is no space in the shop will form a shop queue. The production capacity or maximum departure rate of jobs from the shop will depend on the way in which jobs are selected from the shop queue for release to the machine queues. For a job shop with two identical machines and random routing of jobs a number of release rules are compared. It is shown that the production capacity is increased when the number of jobs in the shop is kept less than the available storage space. Among release rules independent'of job processing times and number of operations the optimum release rule is shown, using dynamic programming, to be the idle machine rule, i.e. only release a job to the shop when a machine would otherwise be idle.     

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 problems with generalised due-dates and job-rejection

We study single machine scheduling problems. Generalised due dates are assumed, i.e. job due dates are specified according to the positions of the jobs in the sequence, rather than their identity. Thus, assuming that due dates are numbered in a non-decreasing order, the jth due date refers to the job assigned to the jth position. In addition, we allow the option of job rejection, i.e. not all jobs must be processed. In this case, the scheduler is penalised for each rejected job, and the total rejection cost becomes part of the objective function. Two objective functions are considered: maximum tardiness plus rejection cost, and total tardiness plus rejection cost. Both problems are proved to be NP-hard. Pseudo-polynomial dynamic programmes and efficient heuristics are introduced and tested numerically.     

New approximation algorithms for flow shop total completion time problem

This article addresses the flow shop scheduling problem to minimize the sum of the completion times. On the basis of the properties in job sequencing, the triangular shortest processing time (TSPT) first and dynamic triangular shortest processing time first heuristics are designed to solve the static and dynamic versions of this problem, respectively. Moreover, an improvement scheme is provided for these heuristics to enhance the quality of the original solutions. For further numerical evaluation of the heuristics, two new lower bounds with performance guarantees are presented for the two versions of the problem. At the end of the article, a series of numerical experiments is conducted to demonstrate the effectiveness of the algorithms.     

A hybrid electromagnetism-like algorithm for two-stage assembly flow shop scheduling problem

This paper presents a study on the two-stage assembly flow shop scheduling problem for minimising the weighed sum of maximum makespan, earliness and lateness. There are m machines at the first stage, each of which produces a component of a job. A single machine at the second stage assembles the m components together to complete the job. A novel model for solving the scheduling problem is built to optimise the maximum makespan, earliness and lateness simultaneously. Two optimal operation sequences of jobs are determined and verified. As the problem is known to be NP-hard, a hybrid variable neighbourhood search – electromagnetism-like mechanism (VNS-EM) algorithm is proposed for its handling. To search beyond local optima for a global one, VNS algorithm is embedded in each iteration of EM, whereby the fine neighbourhood search of optimum individuals can be realised and the solution is thus optimised. Simulation results show that the proposed hybrid VNS-EM algorithm outperforms the EM and VNS algorithms in both average value and standard deviation.     

Genetic algorithms for job shop scheduling problems with alternative routings

The purpose of this research is to solve a general job shop problem with alternative machine routings. We consider four performance measures: mean flow time, makespan, maximum lateness, and total absolute deviation from the due dates. We first develop mixed-integer linear programming (MILP) formulations for the problems. The MILP formulations can be used either to compute optimal solutions for small-sized problems or to test the performance of existing heuristic algorithms. In addition, we have developed a genetic algorithm that can be used to generate relatively good solutions quickly. Further, computational experiments have been performed to compare the solution of the MILP formulations with that of existing algorithms.     

Single-machine scheduling problems with a batch-dependent aging effect and variable maintenance activities

We consider single-machine scheduling problems with a batch-dependent ageing effect and variable maintenance activities between batches. The machine can process several jobs as a batch. It requires maintenance activities where the maintenance time depends on the flow time of the pre-batch, i.e. the batch processed before a batch. A job’s actual processing time is an increasing exponential function of its operation time within a batch. The objectives are to minimise the makespan and the total completion time. We develop polynomial time algorithms for the makespan minimisation problem and the total completion time minimisation problem under the condition that the ageing factor is greater than one. We also provide a mathematical programming approach and two heuristic algorithms to analyse the total completion time minimisation problem when the ageing factor is less than one for even one batch. The computational analysis indicates that the proposed heuristic algorithms are more efficient for the smaller ageing factor, whereas the Modified Shortest Processing Time algorithm is more efficient than the proposed heuristic algorithms for the larger ageing factor.     

Job shop scheduling with alternative machines

In this paper we investigate the problem of minimizing the mean flow time in a general job shop type machining system with alternative machine tool routeings. An analytical formulation of the problem as a mixed integer programming is developed. An efficient algorithm based on this formulation is developed to solve the problem by decomposing it into subproblems that are easier to solve. The algorithm solves large problems in relatively short time. A second algorithm based on the SPT rule is developed and its performance is compared with the first algorithm. A greedy procedure is also developed for the case when a penalty cost is associated with adding alternative machines. Numerical examples are given to demonstrate the use of the above algorithms.     

Single machine batch scheduling with sequential job processing

The problem of scheduling n jobs on a single machine in batches to minimize some regular cost functions is studied. Jobs within each batch are processed sequentially so that the processing time of a batch is equal to the sum of the processing times of the jobs contained in it. Jobs in the same batch are completed at the same time when the last job of the batch has finished its processing. A constant set-up time precedes the processing of each batch. The number of jobs in each batch is bounded by some value b. If b < n, then the problem is called bounded. Otherwise, it is unbounded. For both the bounded and unbounded problems, dynamic programming algorithms are presented for minimizing the maximum lateness, the number of late jobs, the total tardiness, the total weighted completion time, and the total weighted tardiness when all due dates are equal, which are polynomial if there is a fixed number of distinct due dates or processing times. More efficient algorithms are derived for some special cases of both the bounded and unbounded problems in which all due dates and/or processing times are equal. Several special cases of the bounded problem are shown to be NP-hard. Thus, a comprehensive classification of the computational complexities of the special cases is provided.     

Minimising the makespan in the two-machine job shop problem under availability constraints

Classical scheduling problem assumes that machines are available during the scheduling horizon. This assumption may be justified in some situations but it does not apply if maintenance requirements, machine breakdowns or other availability constraints have to be considered. In this paper, we treat a two-machine job shop scheduling problem with one availability constraint on each machine to minimise the maximum completion time (makespan). The unavailability periods are known in advance and the processing of an operation cannot be interrupted by an unavailability period (non-preemptive case). We present in our approach properties dealing with permutation dominance and the optimality of Jackson's rule under availability constraints. In order to evaluate the effectiveness of the proposed approach, we develop two mixed integer linear programming models and two schemes for a branch and bound method to solve the tackled problem. Computational results validate the proposed approach and prove the efficiency of the developed methods.     

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.     

Job shop scheduling with the option of jobs outsourcing

Incorporating outsourcing in scheduling is addressed by several researchers recently. However, this scope is not investigated thoroughly, particularly in the job shop environment. In this paper, a new job shop scheduling problem is studied with the option of jobs outsourcing. The problem objective is to minimise a weighted sum of makespan and total outsourcing cost. With the aim of solving this problem optimally, two solution approaches of combinatorial optimisation problems, i.e. mathematical programming and constraint programming are examined. Furthermore, two problem relaxation approaches are developed to obtain strong lower bounds for some large scale problems for which the optimality is not proven by the applied solution techniques. Using extensive numerical experiments, the performance of the solution approaches is evaluated. Moreover, the effect the objectives's weights in the objective function on the performance of the solution approaches is also investigated. It is concluded that constraint programming outperforms mathematical programming significantly in proving solution optimality, as it can solve small and medium size problems optimally. Moreover, by solving the relaxed problems, one can obtain good lower bounds for optimal solutions even in some large scale problems.     

A combined dispatching criteria approach to scheduling dual flow-shops

This study investigates a dual flow-shops scheduling problem. In the scheduling context, there are two flow shops and each shop involves three processing stages. The two shops are functionally identical but their stage processing times for a job are different. While sequentially going through the three processing stages, each job is allowed to travel between the two shops. That is, for a job, each of its three stages could be processed in any of the two shops. Such a context is called dual flow-shops in the sense that the two flow shops’ capacities are completely shared. The scheduling problem involves two decisions: (1) route assignment (i.e. assigning the processing stages of a job to a shop), and (2) job sequencing (i.e. sequencing the jobs waiting before each stage). The scheduling objective is to minimise the coefficient of variation of slack time (CV_S ), in which the slack time (also called lateness) denotes the difference between the due date and total completion time of a job. We propose five genetic-algorithm-based (GA-based) solution methods to solve the scheduling problem, which are called GA-EDD, GA-FIFO, GA-SPT, GA-LFO, and GA-COMBO respectively. Numerical experiments indicate that GA-COMBO outperforms the other four methods.     

SPT, Data Analysis, and a Bit of Common Sense in Bus Maintenance Operations: A Case Study

A fundamental result in the theory of scheduling is the optimality of the shortest processing time (SPT) rule for minimizing mean flow time in the basic single-machine scheduling problem. The relationship between flow time and inventory also makes this rule an appropriate one to use if the objective is one of rapid turnaround, even when the scheduling environment is dynamic (i.e., where jobs arrive over time). This paper presents a case study where the principle behind SPT sequencing was used for a job shop bus maintenance operation. The results obtained by this implementation are further evidence that the application of SPT sequencing can yield significant improvements in scenarios considerably more complex than the basic single-machine scheduling problem.     

Robust scheduling of a two-stage hybrid flow shop with uncertain interval processing times

This paper studies the makespan minimisation scheduling problem in a two-stage hybrid flow shop. The first stage has one machine and the second stage has m identical parallel machines. Neither the processing time nor probability distribution of the processing time of each job is uncertain. We propose a robust (min–max regret) scheduling model. To solve the robust scheduling problem, which is NP-hard, we first derive some properties of the worst-case scenario for a given schedule. We then propose both exact and heuristic algorithms to solve this problem. In addition, computational experiments are conducted to evaluate the performance of the proposed algorithms.     

Flexible job shop with continuous material flow

A new scheduling problem, the continuous flow flexible job shop (CF-FJS) is proposed. The formulation combines the well-known flexible job shop (FJS) problem and a dedicated continuous material flow model (MFM). In the MFM, operations are represented by material flow functions derived by integration of arbitrarily defined speed patterns. Two main concepts of the MFM formalism, i.e. variable speed of processing and continuous material flow, lead to position-dependent processing times and overlapping in operations which extend standard FJS formulation. Properties of the CF-FJS are investigated. A tabu search sched uling algorithm utilising these properties is proposed. Effective neighbourhood functions are defined based on elimination approaches. Two auxiliary procedures: search intensification level switching and fast feasibility detection are added to improve algorithm efficiency. The algorithm is verified using dedicated benchmark instances which comprise non-trivial representations of the CF-FJS specific features, i.e. machine efficiency patterns and minimum inter-operation buffers. The research is motivated by task scheduling in a fastener factory, but the presented results can be useful in many domains, such as production of granular goods, steel details, glass and fluids. The solution can be used in real-world applications. The published results can be helpful in testing new CF-FJS scheduling algorithms.     

Minimising makespan in the two-stage assembly hybrid flow shop scheduling problem using artificial immune systems

Two-stage hybrid flow shop (HFS) scheduling problem followed by single assembly machine is addressed in this paper. To produce the final product, parts need to be processed on the HFS stages and thereafter, several parts are joined under the assembly operations based on the predefined Bill of Materials of the product. The aim of this research is to find the schedule which minimises completion time of the last product, i.e. makespan. For the considered problem, lower bound, heuristic algorithms and two metaheuristic techniques based on artificial immune system are developed. Computational results demonstrate that the proposed lower bound and heuristic algorithms outperform the existent lower bounds and heuristic algorithms.