Heuristic methods for the single machine scheduling problem with different ready times and a common due date

The single machine scheduling problem with a common due date and non-identical ready times for the jobs is examined in this work. Performance is measured by the minimization of the weighted sum of earliness and tardiness penalties of the jobs. Since this problem is NP-hard, the application of constructive heuristics that exploit specific characteristics of the problem to improve their performance is investigated. The proposed approaches are examined through a computational comparative study on a set of 280 benchmark test problems with up to 1000 jobs.     

A robust scheduling for the multi-mode project scheduling problem with a given deadline under uncertainty of activity duration

The problem of this paper deals with the multi-mode project scheduling problem under uncertainty of activity duration where only the renewable resources are taken into account and a given deadline has to be met at the cost of recruiting additional resources. A heuristic algorithm is employed to solve this problem, and to maintain the robustness of the baseline schedule, the concept of critical chain project management (CCPM) is applied in which a new definition to resource buffer is considered. A simulation methodology is used to determine the size and location of resource buffers in the schedules in which three different buffer sizes and three different uncertainty levels are considered. Results and analysis of the simulation outcomes illustrate that resource buffers are useful and should be simulated by the CCPM schedules, as they help to decrease the total duration of the project during implementation and meet the deadline of the project with more assurance.     

Ant colony optimisation algorithms for two-stage permutation flow shop with batch processing machines and nonidentical job sizes

This paper focuses on minimising the maximum completion time for the two-stage permutation flow shop scheduling problem with batch processing machines and nonidentical job sizes by considering blocking, arbitrary release times, and fixed setup and cleaning times. Two hybrid ant colony optimisation algorithms, one based on job sequencing (JHACO) and the other based on batch sequencing (BHACO), are proposed to solve this problem. First, max-min pheromone restriction rules and a local optimisation rule are embedded into JHACO and BHACO, respectively, to avoid trapping in local optima. Then, an effective lower bound is estimated to evaluate the performances of the different algorithms. Finally, the Taguchi method is adopted to investigate and optimise the parameters for JHACO and BHACO. The performances of the proposed algorithms are compared with that of CPLEX on small-scale instances and those of a hybrid genetic algorithm (HGA) and a hybrid discrete differential evolution (HDDE) algorithm on full-scale instances. The computational results demonstrate that BHACO outperforms JHACO, HDDE and HGA in terms of solution quality. Besides, JHACO strikes a balance between solution quality and run time.     

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.     

Strength and adaptability of problem-space based neighborhoods for resource-constrained scheduling

In this paper, Resource Constrained Scheduling (RCS) consists of scheduling activities on scarce resources, each activity may require more than one resource at a time, and each resource is available in the same quantity throughout the planning period. This paper described a methodology for RCS that can be easily adapted to consider different regular measures of performance. The solution approach is local search using a recent development published in the literature; namely, problem-space based neighborhoods. Computational results are encouraging when searching these spaces using simple local search techniques. Further improvements are explored through the use of a genetic algorithm. In both cases, close-to-optimal solutions are found for standard problems from the literature. The adaptability of the methodology is demonstrated using makespan and mean tardiness as performance measures.     

Some recent results in the analysis of greedy algorithms for assignment problems

We survey some recent developments in the analysis of greedy algorithms for assignment and transportation problems. We focus on the linear programming model for matroids and linear assignment problems with Monge property, on general linear programs, probabilistic analysis for linear assignment and makespan minimization, and on-line algorithms for linear and non-linear assignment problems.This is an expanded version of a survey lecture presented at the DGOR/NSOR Symposium, Amsterdam, 1993     

Comparisons of bi-objective genetic algorithms for hybrid flowshop scheduling with sequence-dependent setup times

This paper addresses the scheduling problems in a hybrid flowshop with two objectives of minimising the makespan and total tardiness. Since this problem is NP-hard, evolutionary algorithms based on the genetic algorithm (GA) namely; BOGAW, BOGAC, BOGAT, and BOGAS are proposed for searching the Pareto-optimal frontier. In these algorithms, we propose to generate a section of solutions for the next generation using a neighbourhood search structure on the best individual in each generation. The selection procedure selects the best chromosome based on an evaluation mechanism used in the algorithm (i.e., weighted sum, crowding distance, TOPSIS and single-objective). The aim of this paper is to clarify that the cited characteristic is efficient and it enhances the efficiency of algorithms. Therefore, we perform a comparison between the proposed algorithms to find the best alternative. Data envelopment analysis is used to evaluate the performance of approximation methods. The obtained result from the comparison shows that, BOGAC is the more efficient. To continue, since the efficiency of our idea is not clear, we compare our efficient algorithm with other efficient algorithms in the literature (namely PGA-ALS and MOGLS). The final persuasive results support the idea that BOGAC in comparison with PGA-ALS and MOGLS is more effective and efficient.     

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     

Asymptotic optimality of shortest processing time-based algorithms for flow shop and open shop problems with nonlinear objective functions

This article investigates the criterion of minimizing total k-power completion time (TKCT) in flow shop and open shop scheduling. For these NP-hard problems, the asymptotic optimality of the shortest processing time-based algorithms is proven for a sufficiently large problem scale. To numerically evaluate the convergence of the algorithms, new lower bounds with performance guarantees are presented for the flow shop TKCT problem. Computational results demonstrate the performance of the proposed algorithms and the effectiveness of the nonlinear objective. In addition, theoretical results on the single-machine TKCT problem are obtained for mathematical deduction.     

The extended resource task network: a framework for the combined scheduling of batch processes and CHP plants

The issue of energy has emerged as one of the greatest challenges facing mankind. In an industrial perspective, the development of site utility systems (generally combined heat and power (CHP) systems) for the generation and management of utilities provides a great potential source for energy savings. However, in most industrial sites, a master–slave relationship usually governs this kind of system and limits the potential operating capacity of CHP. To improve the decision-making process, Agha et al. (2010. Integrated production and utility system approach for optimising industrial unit operation. Energy, 35, 611–627) have proposed an integrated approach that carries out simultaneous and consistent scheduling of batch production plants and site utility systems. The modelling of the problem relies on a mixed integer linear programming (MILP) formulation. Nevertheless, although it is a powerful mathematical tool, it still remains difficult to use for non-expert engineers. In this framework, a graphical formalism based on existing representations (STN, RTN) has been developed: the extended resource task network (ERTN). Combined with an efficient and generic MILP formulation, it permits various kinds of industrial problems, including production and consumption of utility flows to be modelled homogenously. This paper focuses on the semantic elements of the ERTN formalism and illustrates their use through representative examples.