Dynamic job shop scheduling for missed due date performance

In this research, missed due date in terms of mean absolute lateness (MAL) and mean square lateness (MSL) has been considered as a performance criterion and a scheduling study has been performed to improve the missed due date performance in dynamic, stochastic, multi machine job shop environments. In the study, a new due date assignment model was proposed and a new dynamic dispatching rule was developed. The results indicate that the proposed due date assignment model is very successful for improving the missed due date performance and the developed dispatching rule is also very successful for meeting the assigned due dates.     

Research on scheduling with job-dependent learning effect and convex resource-dependent processing times

We study resource allocation scheduling with job-dependent learning effect on a single machine with or without due date assignment considerations. For a convex resource processing time function, we provide a polynomial time algorithm to find the optimal job sequence, and resource allocations that minimise the schedule criterion (the total compression cost) subject to the constraint that the total compression cost (the schedule criterion) is less than or equal to a fixed amount.     

An adaptive scheduling algorithm for a parallel machine problem with rework processes

The development of a scheduling methodology for a parallel machine problem with rework processes is presented in this paper. The problem is to make a schedule for parallel machines with rework probabilities, due-dates, and sequence dependent setup times. Two heuristics are developed based on a dispatching algorithm and problem-space-based search method. In order to evaluate the efficacy of the proposed algorithms, six performance indicators are considered: total tardiness, maximum lateness, mean flow-time, mean lateness, the number of tardy jobs, and the number of reworks. This paper shows how these algorithms can adaptively capture the characteristics of manufacturing facilities for enhancing the performance under changing production environments. Extensive experimental results show that the proposed algorithms give very efficient performance in terms of computational time and each objective value.     

A canned food scheduling problem with batch due date

This article considers a canned food scheduling problem where jobs are grouped into several batches. Jobs can be sent to the next operation only when all the jobs in the same batch have finished their processing, i.e. jobs in a batch, have a common due date. This batch due date problem is quite common in canned food factories, but there is no efficient heuristic to solve the problem. The problem can be formulated as an identical parallel machine problem with batch due date to minimize the total tardiness. Since the problem is NP hard, two heuristics are proposed to find the near-optimal solution. Computational results comparing the effectiveness and efficiency of the two proposed heuristics with an existing heuristic are reported and discussed.     

A multi-phase covering Pareto-optimal front method to multi-objective parallel machine scheduling

This paper considers the problem of parallel machine scheduling with sequence-dependent setup times to minimise both makespan and total earliness/tardiness in the due window. To tackle the problem considered, a multi-phase algorithm is proposed. The goal of the initial phase is to obtain a good approximation of the Pareto-front. In the second phase, to improve the Pareto-front, non-dominated solutions are unified to constitute a big population. In this phase, based on the local search in the Pareto space concept, three multi-objective hybrid metaheuristics are proposed. Covering the whole set of Pareto-optimal solutions is a desired task of multi-objective optimisation methods. So in the third phase, a new method using an e-constraint hybrid metaheuristic is proposed to cover the gaps between the non-dominated solutions and improve the Pareto-front. Appropriate combinations of multi-objective methods in various phases are considered to improve the total performance. The multi-phase algorithm iterates over a genetic algorithm in the first phase and three hybrid metaheuristics in the second and third phases. Experiments on the test problems with different structures show that the multi-phase method is a better tool to approximate the efficient set than the global archive sub-population genetic algorithm presented previously.     

A note on single machine scheduling and due date assignment with general position-dependent processing times

This note considers single machine scheduling and due date assignment in which a job’s processing time depends on its position in a sequence. The objective functions include the cost of changing the due dates, the total cost of discarded jobs that cannot be completed by their due dates and the total earliness of the scheduled jobs. We analyse these problems with three different due date assignment methods. We provide a generic polynomial-time dynamic programming algorithm to solve the problems.     

A discrete electromagnetism-like mechanism for parallel machine scheduling under a grade of service provision

We consider the problem of minimising total weighted tardiness on identical parallel machines with grade of service eligibility. Due to the essential complexity of the problem, we apply an electromagnetism-like mechanism (EM), which is a novel metaheuristic, to solve the problem. In the proposed EM, the particle is redesigned to represent a valid assignment of jobs to machines. A distance measure between particles, called ‘1A2B’ distance, is proposed by the concept of a number guessing game. Then, the new attraction and repulsion operators are developed to move a particle to the new particle. To verify the proposed EM, computational experiments are conducted to make a comparison with a recent genetic algorithm (GA). The results show that the proposed EM has a good performance and outperforms the GA for the considered problem.     

Speeding up a Rollout algorithm for complex parallel machine scheduling

Rollout methodology is a constructive metaheuristic algorithm and its main characteristics are its modularity, the adaptability to different objectives and constraints and the easiness of implementation. Multi-heuristic Rollout extends the Rollout by incorporating several constructive heuristics in the Rollout framework and it is able to easily incorporate human experience inside its research patterns to fulfil complex requirements dictated by the application at hand. However, a drawback for both Rollout and multi-heuristic Rollout is often represented by the required computation time. This paper proposes some alternatives of the full multi-heuristic Rollout algorithm aimed at improving the efficiency by reducing the computational effort while preserving the effectiveness. Namely, we propose dynamic heuristics pruning and candidates reduction strategies. As illustrative case studies, we analyse complex deterministic identical parallel machine scheduling problems showing how Rollout procedures can be used to tackle several additional constraints arising in real contexts. More specifically, we considered both standard (batch production, family set-ups, release, due dates, etc.) and non-standard (machine unavailabilities, maximum campaign size) scheduling constraints. An extensive campaign of computational experiments shows the behaviour of the multi-heuristic Rollout approach and the effectiveness of the different proposed speed-up methods.     

Single-machine scheduling and common due date assignment with potential machine disruption

This paper studies a single-machine due date assignment and scheduling problem in a disruptive environment, where a machine disruption may occur at a particular time that will last for a period of time with a certain probability, and the job due dates are determined by the decision-maker using the popular common due date assignment method. The goal is to determine jointly the optimal job sequence and the common due date so as to minimise the expected value of an integrated cost function that includes the earliness, tardiness and due date assignment costs. We analyse the computational complexity status of various cases of the problem, and develop pseudo-polynomial-time solution algorithms, randomised adaptive search algorithms, and fully polynomial-time approximation schemes for them, if viable. Finally, we conduct extensive numerical testing to assess the performance of the proposed algorithms.     

Unrelated parallel machine scheduling with setup times and ready times

We consider the problem of scheduling unrelated parallel machines with sequence- and machine-dependent setup times and ready times to minimise total weighted tardiness (TWT). We present a mixed integer programming model that can find optimal solutions for the studied problem. We also propose a heuristic (ATCSR_Rm) and an iterated hybrid metaheuristic (IHM) that can find optimal or nearly optimal solutions for the studied problem within a reasonable time. The proposed IHM begins with effective initial solutions, and then improves the initial solutions iteratively. The IHM integrates the principles of the attraction–repulsion mechanism within electromagnetism-like algorithms with local search. If the search becomes trapped at a local optimum, an elite search procedure is developed to help the search escape. We have compared our proposed IHM with two existing metaheuristics, tabu search (TS) and ant colony optimisation (ACO). Computational results show that the proposed IHM outperforms TS and ACO in terms of TWT for problem instances of all sizes.     

Multi-objective unrelated parallel machine scheduling: a Tabu-enhanced iterated Pareto greedy algorithm

This work proposes a high-performance algorithm for solving the multi-objective unrelated parallel machine scheduling problem. The proposed approach is based on the iterated Pareto greedy (IPG) algorithm but exploits the accessible Tabu list (TL) to enhance its performance. To demonstrate the superior performance of the proposed Tabu-enhanced iterated Pareto greedy (TIPG) algorithm, its computational results are compared with IPG and existing algorithms on the same benchmark problem set. Experimental results reveal that incorporating the accessible TL can eliminate ineffective job moves, causing the TIPG algorithm to outperform state-of-the-art approaches in the light of five multi-objective performance metrics. This work contributes a useful theoretical and practical optimisation method for solving this problem.     

Minimising total weighted earliness and tardiness penalties on identical parallel machines using a fast ruin-and-recreate algorithm

This paper studies the scheduling problem of minimising total weighted earliness and tardiness penalties on identical parallel machines against a restrictive common due date. This problem is NP-hard in the strong sense and arises in many just-in-time production environments. A fast ruin-and-recreate (FR&R) algorithm is proposed to obtain high-quality solutions to this complex problem. The proposed FR&R algorithm is tested on a well-known set of benchmark test problems that are taken from the literature. Computational results provide evidence of the efficiency of FR&R, which consistently outperform existing algorithms when applied to benchmark instances. This work provides a viable alternative approach for efficiently solving this practical but complex scheduling problem.     

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.     

Robust makespan minimisation in identical parallel machine scheduling problem with interval data

Parallel machine scheduling problems are commonly encountered in a wide variety of manufacturing environments and have been extensively studied. This paper addresses a makespan minimisation scheduling problem on identical parallel machines, in which the specific processing time of each job is uncertain, and its probability distribution is unknown because of limited information. In this case, the deterministic or stochastic scheduling model may be unsuitable. We propose a robust (min–max regret) scheduling model for identifying a robust schedule with minimal maximal deviation from the corresponding optimal schedule across all possible job-processing times (called scenarios). These scenarios are specified as closed intervals. To solve the robust scheduling problem, which is NP-hard, we first prove that a regret-maximising scenario for any schedule belongs to a finite set of extreme point scenarios. We then derive two exact algorithms to optimise this problem using a general iterative relaxation procedure. Moreover, a good initial solution (optimal schedule under a mid-point scenario) for the aforementioned algorithms is discussed. Several heuristics are developed to solve large-scale problems. Finally, computational experiments are conducted to evaluate the performance of the proposed methods.