Improved heuristics for the early/tardy scheduling problem with no idle time

A dispatch rule and a greedy procedure are presented for the single machine earliness/tardiness scheduling problem with no idle time and compared with the best of the existing dispatch rules. Both dispatch rules use a lookahead parameter that had previously been set at a fixed value. We develop functions that map some instance statistics into appropriate values for that parameter. We also consider the use of dominance rules to improve the solutions obtained by the heuristics. The computational results show that the function-based versions of the heuristics outperform their fixed value counterparts and that the use of the dominance rules can indeed improve solution quality with little additional computational effort.     

A note on “Beam search heuristics for the single machine early/tardy scheduling problem with no machine idle time”

In a recent paper by Valente “Beam search heuristics for the single machine early/tardy scheduling problem with no machine idle time”’, Computers & Industrial Engineering, 55, 663–675, 2008, several beam search approaches are compared on a large set of instances of the total weighted earliness-tardiness problem on single machine with jobs independent weights and no machine idle time. That problem is denoted 1|nmit|_∑jhEj+_∑jwTj$1|\mathit{nmit}|{\sum }_j{\mathit{hE}}_j+{\sum }_j{\mathit{wT}}_j$. This note points out that the standard iterated dynasearch procedure applied to that problem outperforms all the literature heuristics. Based on these results and others obtained on similar problems, we conclude that dynasearch for its efficiency and simplicity, should be used as a benchmark for future heuristics on those types of single machine no idle time problems.     

Local and global dominance conditions for the weighted earliness scheduling problem with no idle time

In this paper, we present dominance conditions for the single machine weighted earliness scheduling problem with no idle time. We also propose an algorithm that can be used to improve upper bounds for the weighted earliness criterion and lower bounds for an earliness/tardiness problem. The computational tests show that the algorithm is superior to an initial heuristic schedule and an existing adjacency condition.     

Local and global dominance conditions for the weighted earliness scheduling problem with no idle time

In this paper, we present dominance conditions for the single machine weighted earliness scheduling problem with no idle time. We also propose an algorithm that can be used to improve upper bounds for the weighted earliness criterion and lower bounds for an earliness/tardiness problem. The computational tests show that the algorithm is superior to an initial heuristic schedule and an existing adjacency condition.     

Dispatching heuristics for the single machine early/tardy scheduling problem with job-independent penalties

In this paper, we consider the single machine earliness/tardiness scheduling problem with job-independent penalties, and no machine idle time. Several dispatching heuristics are proposed, and their performance is analysed on a wide range of instances. The heuristics include simple scheduling rules, as well as a procedure that takes advantage of the strengths of each of those rules. We also consider early/tardy dispatching procedures, and a heuristic method based on existing adjacent precedence conditions. An improvement procedure that can be used to improve the schedules generated by the heuristics is also proposed.

The computational tests show that the best results are given by the early/tardy dispatching rules. These heuristics are also quite fast, and are capable of quickly solving even very large instances. The use of the improvement procedure is recommended, since it improves the solution quality, with little additional computational effort.     

A differential evolution approach for the common due date early/tardy job scheduling problem

The problem of scheduling multiple jobs on a single machine so that they are completed by a common specified date is addressed in this paper. This type of scheduling set costs depend on whether a job is finished before (earliness) or after (tardiness) the specified due date. The objective is to minimize a summation of earliness and tardiness penalty costs. Minimizing these costs pushes the completion time of each job as close as possible to the due date. The use of differential evolution as the optimization heuristic to solve this problem is investigated in this paper. Computational experiments over multiple (280 in total) public benchmark problems with up to 1000 jobs to be scheduled show the effectiveness of the proposed approach. The results obtained are of high quality putting new upper bounds to 60% of the benchmark instances.     

Exact resolution of the one-machine sequencing problem with no machine idle time

This paper investigates the one-machine sequencing problem in a workshop where the machine has to satisfy the no-idle constraint, that is, the machine must process jobs without interruption. The objective is to minimize the makespan. Each job has a release date for which it is available for processing on the machine and a delivery time during which it must remain in the system after being processed by the machine. This problem has been studied without adding the no-idle constraint. It is solved in polynomial time, when the preemption of jobs is allowed, applying Jackson’s rule. But, when the preemption of jobs is not allowed, it becomes strongly NP-hard. Although, it can be solved in a very short time using Carlier’s branch and bound algorithm. Below, we propose to adapt Carlier’s branch and bound method in order to calculate an optimal nonpreemptive schedule for the problem when adding the no-idle constraint.     

求解批量流水线调度问题的和声算法

针对以最大完工时间和总流经时间为目标的批量流水线调度问题,提出了改进的和声调度算法。该算法采用基于最大位置值(LPV)规则的编码方式,使具有连续性质的和声算法应用于求解调度问题;提出新的初始化方法,应用了多种群进化的思想更新和声库,并结合和声算法和模拟退火算法各自的特点,给出了两种混合调度算法。仿真实验表明所提算法的可行性和有效性。     

Adaptive beam search lookahead algorithms for the circular packing problem

This paper addresses the circular packing problem (CPP), which consists in packing n circles C_i, each of known radius r_i, i∈N={1, …, n}, into the smallest containing circle C. The objective is to determine the radius r of C as well as the coordinates (x_i, y_i) of the center of C_i, i∈N. CPP is solved using two adaptive algorithms that adopt a binary search to determine r, and a beam search to check the feasibility of packing n circles into C when the radius is fixed at r. A node of level ?, ?=1, …, n, of the beam search tree corresponds to a partial packing of ? circles of N into C. The potential of each node of the tree is assessed using a lookahead strategy that, starting with the partial packing of the current node, assigns each unpacked circle to its maximum hole degree position. The beam search stops either when the lookahead strategy identifies a feasible packing or when it has fathomed all nodes. The computational tests on a set of benchmark instances show the effectiveness of the proposed adaptive algorithms.     

Optimal algorithms for the online time series search problem

In the problem of online time series search introduced by El-Yaniv et al. (2001) [1], a player observes prices one by one over time and shall select exactly one of the prices on its arrival without the knowledge of future prices, aiming to maximize the selected price. In this paper, we extend the problem by introducing profit function. Considering two cases where the search duration is either known or unknown beforehand, we propose two optimal deterministic algorithms respectively. The models and results in this paper generalize those of El-Yaniv et al. (2001) [1].     

An exact approach to early/tardy scheduling with release dates

In this paper, we consider the single machine earliness/tardiness scheduling problem with different release dates and no unforced idle time. The problem is decomposed into weighted earliness and weighted tardiness subproblems. Lower bounding procedures are proposed for each of these subproblems, and the lower bound for the original problem is the sum of the lower bounds for the two subproblems. The lower bounds and several versions of a branch-and-bound algorithm are then tested on a set of randomly generated problems, and instances with up to 30 jobs are solved to optimality. To the best of our knowledge, this is the first exact approach for the early/tardy scheduling problem with release dates and no unforced idle time.     

An algorithm for insertion of idle time in the single-machine scheduling problem with convex cost functions

This paper addresses the problem of optimally inserting idle time into a single-machine schedule when the sequence is fixed and the cost of each job is a convex function of its completion time. We propose a pseudo-polynomial time algorithm to find a solution within some tolerance of optimality in the solution space, i.e., each completion time will belong to a small time interval z within which the optimal solution lies. Letting H be the planning horizon and |J| the number of jobs, the proposed algorithm is superior to the current best algorithm in terms of time-complexity when |J|<H/z.     

Beam search algorithms for the single machine total weighted tardiness scheduling problem with sequence-dependent setups

In this paper, we consider the single machine weighted tardiness scheduling problem with sequence-dependent setups. We present heuristic algorithms based on the beam search technique. These algorithms include classic beam search procedures, as well as the filtered and recovering variants. Previous beam search implementations use fixed beam and filter widths. We consider the usual fixed width algorithms, and develop new versions that use variable beam and filter widths.     

Simulated annealing algorithm for solving the single machine early/tardy problem

Recently, several studies have been conducted regarding the application of the simulated annealing (SA) method to solve combinatorial optimization problems. Most of the previous reports have shown that SA has been used to obtain reasonable solutions that are better than some heuristic algorithms and in comparable CPU time. A single machine early/tardy problem is selected in this paper to demonstrate the usefulness of SA. Firstly, based on previous studies, this research uses the factorial experiment to analyse the factors that are critical to the efficiency of SA. Secondly, SA, tuned by the previous step, is compared with branch-and-bound and neighbourhood search methods by solving some test problems. The results show that SA is very sensitive to the cooling schedule, generation mechanism, acceptance criteria and stopping criteria. When SA is used to solve the single machine problem with n ≤ 15, it can converge to the optimal solution quickly. For the single machine problem where n ≥ 30, the branch-and-bound algorithm is not feasible while SA can provide a much better solution than the neighbourhood search method.     

A comparison of lower bounds for the single-machine early/tardy problem

This paper considers the single-machine early/tardy problem. The paper presents a procedure that integrates a timetabling algorithm into a lower bound for jobs not included in a partial sequence. The paper also shows how two lower bounds that were developed previously for the problem can be improved. The lower bounds are tested on problems of various sizes and parameters for the distribution of due dates. The results show that the lower bounds are able to increase the efficiency of a branch-and-bound algorithm.     

New approximate algorithms for the customer order scheduling problem with total completion time objective

In this paper, we study a customer order scheduling problem where a number of orders, composed of several product types, have to be scheduled on a set of parallel machines, each one capable to process a single product type. The objective is to minimise the sum of the completion times of the orders, which is related to the lead time perceived by the customer, and also to the minimisation of the work-in-process. This problem has been previously studied in the literature, and it is known to be NP-hard even for two product types. As a consequence, the interest lies on devising approximate procedures to obtain fast, good performing schedules. Among the different heuristics proposed for the problem, the ECT (Earliest Completion Time) heuristic by Leung et al. [6] has turned to be the most efficient constructive heuristic, yielding excellent results in a wide variety of settings. These authors also propose a tabu search procedure that constitutes the state-of-the-art metaheuristic for the problem. We propose a new constructive heuristic based on a look-ahead mechanism. The computational experience conducted shows that it clearly outperforms ECT, while having both heuristics the same computational complexity. Furthermore, we propose a greedy search algorithm using a specific neighbourhood that outperforms the existing tabu search procedure for different stopping criteria, both in terms of quality of solutions and of required CPU effort.     

A beam search heuristics to solve the parcel hub scheduling problem

In this paper, a beam search scheduling heuristic (BSSH) is presented to solve the parcel hub scheduling problem (PHSP), which is a scheduling problem that is common in the parcel delivery industry (PDI). Companies in the PDI include the United States Postal Service, United Parcel Services, Federal Express, and Deutsche Post. Together, these companies move more than one trillion dollars of the United States’ Gross Domestic Product. The PHSP involves scheduling a set of inbound trailers each containing a set of heterogeneous parcels to a set of unload docks. At the unload docks, the parcels are unloaded, sorted, and moved to the appropriate outbound trailers at the load docks. At the load docks, the parcels are loaded onto the outbound trailers. The objective is to minimize the timespan of the transfer operation at the transshipment terminal. The BSSH is compared to various scheduling approaches: random scheduling algorithm (RSA), genetic-based scheduling algorithm (GBSA), and simulation-based scheduling algorithm (SBSA). While GBSA and SBSA offer solutions that are superior to BSSH for smaller size problems, BSSH outperforms these algorithms on larger size problems requiring much less computational time. The results show that for larger size problems the BSSH is able to produce solutions that are from 4% to 8% of the known optimum solutions. In contrast, GBSA and SBSA, respectively offer solutions from 23% to 38% and from 6% to 47% of the known optimum solutions. The contribution of this paper is a scheduling heuristic to solve the PHSP.     

离散和声求解带启动时间批量流水线调度问题

分别在有等待和无等待的情况下,深入分析了带有启动时间的批量调度问题,以最小化最大完成时间为目标,提出了两种离散和声搜索算法。针对算法本质连续而问题离散的矛盾,对和声搜索算法进行改进。首先提出了基于工序的编码方式,采用inver-over和重组两种离散算子产生候选解的进化机制;并利用改进的NEH(Nawaz-Enscore-Ham)方法进行初始化,产生的高质量和多样化的初始种群有效地指导了算法的进化方向,提高收敛速度;最后将一种简单而有效的局部邻域搜索方法嵌入到和声搜索算法中以增强其局部搜索能力。仿真实验和比较结果表明了所提算法的有效性。     

Efficient heuristic algorithms for the blocking flow shop scheduling problem with total flow time minimization

This paper proposes two constructive heuristics, i.e. HPF1 and HPF2, for the blocking flow shop problem in order to minimize the total flow time. They differ mainly in the criterion used to select the first job in the sequence since, as it is shown, its contribution to the total flow time is not negligible. Both procedures were combined with the insertion phase of NEH to improve the sequence. However, as the insertion procedure does not always improve the solution, in the resulting heuristics, named NHPF1 and NHPF2, the sequence was evaluated before and after the insertion to keep the best of both solutions. The structure of these heuristics was used in Greedy Randomized Adaptive Search Procedures (GRASP) with variable neighborhood search in the improvement phase to generate greedy randomized solutions. The performance of the constructive heuristics and of the proposed GRASPs was evaluated against other heuristics from the literature. Our computational analysis showed that the presented heuristics are very competitive and able to improve 68 out of 120 best known solutions of Taillard’s instances for the blocking flow shop scheduling problem with the total flow time criterion.