Jorge Valente

Abstract
This paper considers the single machine total weighted tardiness problem. A thorough computational evaluation of new and existing dispatching rules is performed. We considered several existing heuristics and proposed new backward rules. These procedures are analyzed together for the first time and coded in the same programming language. We also created a new and much larger dataset, which allows a more detailed comparison and provides a useful benchmark for future work.We first conducted preliminary tests to determine appropriate parameter values and to choose between three versions of the new rules. These tests showed a need to use instance characteristics to make better choices. We then analyzed the heuristics and identified the non-dominated procedures, considering solution quality and computational time. One of the new backward rules is non-dominated, achieving the best solution quality. The non-dominated set allows decision-makers to choose a procedure depending on problem size and available time.

Abstract
Traditionally, scheduling literature has focused mainly on solving problems related to processing jobs with non- assembly operations. Despite the growing interest in the assembly literature in recent years, knowledge of the problem is still in its early stages in many aspects. In this regard, we are not aware of any previous contributions that address the assembly scheduling problem with just-in-time objectives. To fill this gap, this paper studies the 2-stage assembly scheduling problem minimising the sum of total earliness and total tardiness. We first analyse the relationship between the decision problem and the generation of the due dates of the jobs, and identify the equivalences with different related decision problems depending on the instances. The properties and conclusions obtained in the analysis are applied to design two constructive heuristics and a composite heuristic. To evaluate our proposals, different heuristics from the state-of-the-art of related scheduling problems are adapted, and a computational evaluation is carried out. The excellent behaviour of the proposed algorithms is demonstrated by an extensive computational evaluation.

Abstract
In this paper, we consider a permutation flowshop problem, with a weighted squared tardiness objective function, which addresses an important criterion for many customers. Our objective is to find metaheuristics that can, within acceptable computational times, provide sizeable improvements in solution quality over the best existing procedure (a dispatching rule followed by an improvement method). We consider four metaheuristics, namely iterated local search (ILS), iterated greedy (IG), variable greedy (VG) and steady-state genetic algorithms (SSGA). These are known for performing well on permutation flowshops and/or on tardiness criteria. For each metaheuristic, four versions are developed, differing on the choice of initial sequence and/or local search. Additionally, four different time limits are considered. Therefore, a total of 64 sets of results are obtained. The results show that all procedures greatly outperform the best existing method. The IG procedures provide the best results, followed by the SSGA procedures. The VG methods are usually inferior to SSGA, while the ILS metaheuristics tend to be the worst performers. The four metaheuristics prove to be robust in what regards initial solution and local search method, since both have little effect on the performance of the metaheuristics. Increasing the time limit does improve the performance of all procedures. Still, a sizeable improvement is obtained even for the lowest time limit. Therefore, even under restrictive time limits, the metaheuristics greatly outperform the best existing procedure.

Abstract
Scheduling jobs in a no-wait flow shop with the objective of minimising total earliness and tardiness is the problem addressed in this paper. Idle time may be needed on the first machine due to the no-wait restriction. A model is developed that shows additional idle can be inserted on the first machine to help reduce earliness. Several dispatching heuristics previously used in other environments were modified and tested. A two-phased procedure was also developed, estimating additional idle in the first phase, and applying dispatching heuristics in the second phase. Several versions of an insertion improvement procedure were also developed. The procedures are tested on instances of various sizes and due date tightness and range. The results show the two-phase heuristics are more effective than the simple rules, and the insertion search improvement procedure can provide considerable improvements.

Abstract
This paper considers the problem of scheduling jobs in a no-wait flow shop with the objective of minimizing total earliness and tardiness. An exact branch-and-bound algorithm is developed for the problem. Several dispatching heuristics used previously for other environments and two new heuristics were tested under a variety of conditions. It was found that one of the new heuristics consistently performed well compared to the others. An insertion search improvement procedure with speed up methods based on the structure of the problem was proposed and was found to deliver much improved solutions in a reasonable amount of time.