双机无等待流水作业调度算法研究

考虑双机无等待流水作业调度问题,此问题中每台机器都受一个非可用时间的约束,工件都有不同的释放时间。机器的非可用性时间间隔是部分重叠并且已知。目标使Makespan(最大流程时间)最小。通过不同的方式计算上限和下限,完善分支定界法。计算机实验结果显示了所述方法的有效性。     

No-wait scheduling of a two-machine flow-shop to minimise the makespan under non-availability constraints and different release dates

In this paper, we consider the two-machine no-wait flow-shop scheduling problem, when every machine is subject to one non-availability constraint and jobs have different release dates. The non-availability intervals of the machines overlap and they are known in advance. We aim to find a non-resumable schedule that minimises the makespan. We propose several lower bounds and upper bounds. These bounding procedures are used in a branch-and-bound algorithm. Computational experiments are carried out on a large set of instances and the obtained results show the effectiveness of our method.     

Scheduling trucks in container terminals using a genetic algorithm

Trucks are the most popular transport equipment in most mega-terminals, and scheduling them to minimize makespan is a challenge that this article addresses and attempts to resolve. Specifically, the problem of scheduling a fleet of trucks to perform a set of transportation jobs with sequence-dependent processing times and different ready times is investigated, and the use of a genetic algorithm (GA) to address the scheduling problem is proposed. The scheduling problem is formulated as a mixed integer program. It is noted that the scheduling problem is NP-hard and the computational effort required to solve even small-scale test problems is prohibitively large. A crossover scheme has been developed for the proposed GA. Computational experiments are carried out to compare the performance of the proposed GA with that of GAs using six popular crossover schemes. Computational results show that the proposed GA performs best, with its solutions on average 4.05% better than the best solutions found by the other six GAs.     

Development of a hybrid metaheuristic to minimise earliness and tardiness in a hybrid flowshop with sequence-dependent setup times

This paper presents an efficient hybrid metaheuristics for scheduling jobs in a hybrid flowshop with sequence-dependent setup times. The problem is to determine a schedule that minimises the sum of earliness and tardiness of jobs. Since this problem class is NP-hard in the strong sense, there seems to be no escape from appealing to metaheuristic procedures to achieve near-optimal solutions for real life problems. This paper proposes the hybrid metaheuristic algorithm which comprises three components: an initial population generation method based on an ant colony optimisation, a simulated annealing algorithm as an evolutionary algorithm that employs certain probability to avoid becoming trapped in a local optimum, and a variable neighbourhood search which involves three local search procedures to improve the population. A design of experiments approach is employed to calibrate the parameters of the algorithm. Results of computational tests in solving 252 problems up to 100 jobs have shown that the proposed algorithm is computationally more effective in yielding solutions of better quality than the adapted random key genetic algorithm and immune algorithm presented previously.     

Parallel machine scheduling considering a job-splitting property

This paper focuses on the problem of scheduling jobs on parallel machines considering a job-splitting property. In this problem, it is assumed that a job can be split into a discrete number of subjobs and they are processed on parallel machines independently. A two-phase heuristic algorithm is suggested for the problem with the objective of minimizing total tardiness. In the first phase, an initial sequence is constructed by an existing heuristic method for the parallel-machine scheduling problem. In the second phase, each job is split into subjobs considering possible results of the split, and then jobs and subjobs are rescheduled on the machines using a certain method. To evaluate performance of the suggested algorithm, computational experiments are performed on randomly generated test problems. Results of the experiments show that the suggested algorithm performs better than an existing one.     

A novel hybrid meta-heuristic algorithm for a no-wait flexible flow shop scheduling problem with sequence dependent setup times

In this paper, we contemplate the problem of scheduling a set of n jobs in a no-wait flexible flow shop manufacturing system with sequence dependent setup times to minimising the maximum completion time. With respect to NP-hardness of the considered problem, there seems to be no avoiding application of metaheuristic approaches to achieve near-optimal solutions for this problem. For this reason, three novel metaheuristic algorithms, namely population based simulated annealing (PBSA), adapted imperialist competitive algorithm (AICA) and hybridisation of adapted imperialist competitive algorithm and population based simulated annealing (AICA?+?PBSA), are developed to solve the addressed problem. Because of the sensitivity of our proposed algorithm to parameter's values, we employed the Taguchi method as an optimisation technique to extensively tune different parameters of our algorithm to enhance solutions accuracy. These proposed algorithms were coded and tested on randomly generated instances, then to validate the effectiveness of them computational results are examined in terms of relative percentage deviation. Moreover, some sensitive analyses are carried out for appraising the behaviour of algorithms versus different conditions. The computational evaluations manifestly support the high performance of our proposed novel hybrid algorithm against other algorithms which were applied in literature for related production scheduling problems.     

Minimising interference for scheduling two parallel machines with a single server

In this paper, we consider the problem of scheduling a set of jobs on two parallel machines with set-up times. The set-up has to be performed by a single server. The objective is to minimise the forced idle time. The problem of minimising the forced idle time (interference problem) is known to be unary NP-hard for the case of two machines and equal set-up and arbitrary processing times. We propose a mixed integer linear programming model, which describes a special class of schedules where the jobs from a list are scheduled alternatively on the machines, and a heuristic algorithm is tested on instances with up to 100,000 jobs. The computational results indicate that the algorithm has an excellent performance even for very large instances, where mostly an optimal solution is obtained within a very small computational time.     

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.     

A method combining rules with genetic algorithm for minimizing makespan on a batch processing machine with preventive maintenance

This paper considers the problem of minimising makespan on a single batch processing machine with flexible periodic preventive maintenance. This problem combines two sub-problems, scheduling on a batch processing machine with jobs’ release dates considered and arranging the preventive maintenance activities on a batch processing machine. The preventive maintenance activities are flexible but the maximum continuous working time of the machine, which is allowed, is determined. A mathematical model for integrating flexible periodic preventive maintenance into batch processing machine problem is proposed, in which the grouping of jobs with incompatible job families, the starting time of batches and the preventive maintenance activities are optimised simultaneously. A method combining rules with the genetic algorithm is proposed to solve this model, in which a batching rule is proposed to group jobs with incompatible job families into batches and a modified genetic algorithm is proposed to schedule batches and arrange preventive maintenance activities. The computational results indicate the method is effective under practical problem sizes. In addition, the influences of jobs’ parameters on the performance of the method are analyzed, such as the number of jobs, the number of job families, jobs’ processing time and jobs’ release time.     

Batch scheduling in differentiation flow shops for makespan minimisation

This paper considers a two-stage three-machine differentiation flow shop that comprises a common machine at stage 1 and two independent dedicated machines at stage 2. Two types of jobs are to be processed. All jobs must visit the stage-1 machine, and then the jobs of each type proceed to their dedicated machine for stage-2 processing. The stage-1 machine processes the jobs in batches, each of which, whenever formed, requires a constant setup time. The objective is to find a schedule that attains the minimum makespan. While the problem is strongly NP-hard, we investigate the case where the processing sequences of the two types of jobs are given and fixed. A polynomial-time dynamic programming algorithm is designed to solve this problem. We then deploy this algorithm to compute the lower bounds of the general problem.     

A comparison of metaheuristic procedures to schedule jobs in a permutation flow shop to minimise total earliness and tardiness

This paper considers the problem of scheduling jobs in a permutation flow shop with the objective of minimising total earliness and tardiness. A genetic algorithm is proposed for the problem. This procedure and five other procedures were tested on problem sets that varied in terms of number of jobs, machines and the tightness and range of due dates. It was found that the genetic algorithm procedure was consistently effective in generating good solutions relative to the other procedures.     

A new heuristic for the flowshop scheduling problem to minimize makespan and maximum tardiness

This paper presents a new heuristic for solving the flowshop scheduling problem that aims to minimize makespan and maximize tardiness. The algorithm is able to take into account the aforementioned performance measures, finding a set of non-dominated solutions representing the Pareto front. This method is based on the integration of two different techniques: a multi-criteria decision-making method and a constructive heuristic procedure developed for makespan minimization in flowshop scheduling problems. In particular, the technique for order preference by similarity of ideal solution (TOPSIS) algorithm is integrated with the Nawaz–Enscore–Ham (NEH) heuristic to generate a set of potential scheduling solutions. To assess the proposed heuristic's performance, comparison with the best performing multi-objective genetic local search (MOGLS) algorithm proposed in literature is carried out. The test is executed on a large number of random problems characterized by different numbers of machines and jobs. The results show that the new heuristic frequently exceeds the MOGLS results in terms of both non-dominated solutions, set quality and computational time. In particular, the improvement becomes more and more significant as the number of jobs in the problem increases.     

Assigning jobs to time frames on a single machine to minimize total tardiness

This paper deals with a sequencing problem arising in the management of paced-flowlines, that is production lines where jobs are released at constant time intervals. The problem is to sequence jobs to minimis total tardiness. The problem can be formulated as an assignment problem with a number of knapsack constraints. We prove the strong NP-hardness of the problem and give a number of lower bounds which are used in a branch-and-bound algorithm. Computational results in realistic settings confirm the effectiveness of the procedure developed. The results are particularly interesting with reference to mixed-model assembly lines in which several jobs of few different types are produced periodically.     

A branch-and-bound algorithm for a two-stage hybrid flowshop scheduling problem minimizing total tardiness

A two-stage hybrid flowshop-scheduling problem is considered with the objective of minimizing total tardiness of jobs. In the hybrid flowshop, there is one machine at the first stage and multiple identical parallel machines at the second stage. Dominance properties and lower bounds are developed for the problem and a branch-and-bound algorithm is suggested using them. Results of computational experiments show that the suggested algorithm can find optimal solutions for problems with up to 15 jobs in a reasonable amount of central processing unit time.     

Generating all efficient solutions of a rescheduling problem on unrelated parallel machines

In this paper, we consider a rescheduling problem where a set of jobs has already been assigned to unrelated parallel machines. When a disruption occurs on one of the machines, the affected jobs are rescheduled, considering the efficiency and stability measures. Our efficiency measure is the total flow time and stability measure is the total reassignment cost caused by the differences in the machine allocations in the initial and new schedules. We propose a branch and bound algorithm to generate all efficient solutions with respect to our efficiency and stability measures. We improve the efficiency of the algorithm by incorporating powerful reduction and bounding mechanisms. Our computational tests on large sized problem instances have revealed the satisfactory behaviour of our algorithm.     

Spread time considerations in operational fixed job scheduling

In this study, we consider the operational fixed job scheduling problem on identical parallel machines. We assume that the jobs have fixed ready times and deadlines, and spread time constraints are imposed on machines. Our objective is to select a set of jobs for processing so as to maximise the total weight. We show that the problem is strongly NP-hard, and we investigate several special polynomially solvable cases. We propose a branch and bound algorithm that employs size reduction mechanisms, dominance conditions, and powerful lower and upper bounds. The computational results reveal that the branch and bound algorithm returns optimal solutions for problem instances with up to 100 jobs in reasonable solution times.     

Operational fixed job scheduling problem under spread time constraints: a branch-and-price algorithm

This study addresses the operational fixed job scheduling problem under spread time constraints. The problem is to select a subset of jobs having fixed ready times and deadlines for processing on identical parallel machines such that total weight of the selected jobs is maximised. We first give a mathematical formulation of the problem and then reformulate it using Dantzig-Wolfe decomposition. We propose a branch-and-price algorithm that works on the reformulation of the problem. Computational results show that our algorithm is far superior to its competitor in the literature. It solves instances that could not be solved in one hour CPU time in less than a second and is able to solve large-scale instances in reasonable times which make it a computationally viable tool for decision-making.     

Scheduling of Customized Jobs on a Single Machine under Item Availability

We study a problem of scheduling customized jobs on a single-machine. Each job requires two operations: one standard and one specific. Standard operations are processed in batches under item availability, and each batch requires a set-up time. Based on structural properties of the optimal solution, we introduce a generic dynamic programming scheme that builds an optimal schedule by alternately inserting blocks of operations of two distinct types. Our approach yields efficient algorithms for the sum of completion times problem with agreeable processing times and the maximum lateness problem. The number of late jobs problem is shown to be NP-hard in the ordinary sense, but is pseudo-polynomially solvable. A polynomial algorithm is also given for a special case of this problem. Our results indicate the differences between this problem and its counterpart under batch availability.     

Solution algorithms for the number of tardy jobs minimisation scheduling with a time-dependent learning effect

This paper deals with a single-machine scheduling problem with a time-dependent learning effect. The goal is to determine the job sequence that minimise the number of tardy jobs. Two dominance properties, two heuristic algorithms and a lower bound to speed up the search process of the branch-and-bound algorithm are proposed. Computational experiments show that the branch-and-bound algorithm can solve instances up to 18 jobs in a reasonable amount of time, and the proposed heuristic algorithm MFLA performs effectively and efficiently     

Makespan minimisation for a parallel machine scheduling problem with preemption and job incompatibility

In this paper, an extension of the graph colouring problem is introduced to model a parallel machine scheduling problem with job incompatibility. To get closer to real-world applications, where the number of machines is limited and jobs have different processing times, each vertex of the graph requires multiple colours and the number of vertices with the same colour is bounded. In addition, several objectives related to scheduling are considered: makespan, number of pre-emptions and summation over the jobs’ throughput times. Different solution methods are proposed, namely, two greedy heuristics, two tabu search methods and an adaptive memory algorithm. The latter uses multiple recombination operators, each one being designed for optimising a subset of objectives. The most appropriate operator is selected dynamically at each iteration, depending on its past performance. Experiments show that the proposed algorithm is effective and robust, while providing high-quality solutions on benchmark instances for the graph multi-colouring problem, a simplification of the considered problem.