Crane scheduling in container yards with inter-crane interference

This paper examines the problem of scheduling multiple yard cranes to perform a given set of jobs with different ready times in a yard zone with only one bi-directional travelling lane. Due to sharing of the travelling lane among two or more yard cranes, inter-crane interference, a planned move of a yard crane blocked by the other yard cranes, may happen. The scheduling problem is formulated as an integer program. It is noted that the scheduling problem is NP-complete. This research develops a dynamic programming-based heuristic to solve the scheduling problem and an algorithm to find lower bounds for benchmarking the schedules found by the heuristic. Computational experiments are carried out to evaluate the performance of the heuristic and the results show that the heuristic can indeed find effective solutions for the scheduling problem, with the heuristic solutions on average 7.3% above their lower bounds.     

The Orienteering Problem with Time Windows

The orienteering problem with time windows, denoted by OPTW, belongs to a class of routeing and scheduling problems that arise in physical distribution. It may be modelled as a problem on a graph. It considers a set of nodes (customers), each with an associated profit and service duration (time window), and a set of arcs, each with an associated travel time. The objective of the problem is to construct an acyclic path beginning at a specified origin and ending at a specified destination that maximizes the total profit while observing time window constraints on all nodes and not exceeding a designated time limit. The problem is classified as NP-hard and, thus, an exact algorithm that executes in reasonable computational time is unlikely to exist. Since the problem is highly-constrained, we were able to develop a heuristic (referred to as the ‘tree’ heuristic) based upon an exhaustive search of the feasible solution space. The tree heuristic systematically generates a list of feasible paths and then selects the most profitable path from the list. In comparison with an insertion heuristic, the tree heuristic was found to produce improved values of total profit for heavily-constrained, modest-sized problems with reasonable computational effort.     

A mathematical model and two-stage heuristic for hot rolling scheduling in compact strip production

This paper addresses a new hot rolling scheduling problem from the compact strip production process, which is the mainstream production technology that is used worldwide for sheet strips. The problem is modeled as a combination of two coupled sub-problems. One sub-problem is a sheet strip assignment problem that assigns sheet strips to rolling turns with the constraints of safe values of different gauge levels, and the other is a sheet strip sequencing problem that decides the rolling sequence for all of the sheet strips in a rolling turn to form a particular parabolic shape in thickness. To solve this hot rolling scheduling problem, we present a novel approach that consists of a sheet strip assignment heuristic and a sheet strip sequencing heuristic. The sheet strip assignment heuristic minimizes the number of virtual sheet strips by generating rolling turns according to the ordered sheet strips with maximum gauge level and their safe values. The sheet strip sequencing heuristic minimizes the average change of the thickness of adjacent sheet strips by arranging a certain number of duplicate sheet strips to the increasing stage of a rolling turn. Extensive experiments based on both synthetic and real-world instances from a compact strip production process show the effectiveness of the proposed two-stage heuristic in solving the hot rolling scheduling problem.     

An Heuristic Method for Solving Time-Sensitive Routeing Problems

Many vehicle scheduling situations require careful monitoring and control of the time a vehicle is on the road. Setting time limits as rigid constraints on a vehicle scheduling problem is usually not appropriate since minor violations of such constraints do not really imply that a solution is infeasible. An heuristic method for solving vehicle scheduling problems in which time is an important factor has been developed. The heuristic creates routes based on a "time density function" which identifies clusters of stops and chooses stops from these clusters to form a route. Important considerations balancing overtime costs, overnight route costs and travel costs to and from far clusters of stops are part of the heuristic. The method has been tested on 10 days of data from a large food distributor in the midwestern United States and found to affect significantly both variable and fixed costs in these commercial problems. The smallest of these problems had 110 stops, while the largest had 223. A modest amount of computer time (under 15 seconds in every case) was required to generate the assignment of stops to trucks and produce routes for the vehicles.     

A penalty-based heuristic algorithm for the permutation flowshop scheduling problem with sequence-dependent set-up times

This paper considers the permutation flowshop scheduling problem with sequence-dependent set-up times and develops a penalty-based heuristic algorithm to find an approximately minimum makespan schedule. The proposed algorithm determines the penalty in time associated with a particular sequence and selects the sequence with the minimum time penalty as the best heuristic solution. Computational results comparing the effectiveness and efficiency of the proposed penalty-based heuristic algorithm with an existing savings index heuristic algorithm are reported and discussed.     

A constructive heuristic for staff scheduling in the glass industry

In this paper a constructive heuristic for solving the staff scheduling problem of a glass manufacture unit is proposed. Based on simple calculations and algorithms, the developed procedure assigns working shifts and days-off to teams of employees, ensuring the satisfaction of a mandatory sequence of working shifts and the balance of the workload between employees. The computational times for the experiments with the case study company, with three eight-hour working shifts and five teams of employees, fell consistently below 5 seconds for a set of different planning periods. Results are compared with the ones achieved with an optimization model (MIP), demonstrating the good performance of the heuristic, also in terms of the quality of the achieved solutions. The heuristic rarely fails to produce a feasible solution and whenever the solution is feasible then it is also optimal. When tackling problems with a large number of teams, the heuristic maintains the good performance while the MIP model is not able to find any solution within 16 hours of running time. Although it was designed for a particular problem of the glass industry, tests show that the heuristic is flexible enough to be applied to problems with different features, from other activity sectors, encouraging further extensions of this work.     

An adaptive search for the response time variability problem

The Response Time Variability Problem (RTVP) is an NP-hard combinatorial scheduling problem, which has recently been reported and formalised in the literature. This problem has a wide range of real-world applications in mixed-model assembly lines, multi-threaded computer systems, broadcast of commercial videotapes and others. The RTVP arises whenever products, clients or jobs need to be sequenced in such a way that the variability in the time between the points at which they receive the necessary resources is minimised. We propose a greedy but adaptive heuristic that avoids being trapped into a poor solution by incorporating a look ahead strategy suitable for this particular scheduling problem. The proposed heuristic outperforms the best existing methods, while being much faster and easier to understand and to implement.     

A Simulated Annealing Approach to the Solution of Flexible Labour Scheduling Problems

This paper presents a new solution approach to the discontinuous labour tour scheduling problem where the objective is to minimize the number of full-time employees required to satisfy forecast demand. Previous heuristic approaches have often limited the number of allowable tours by restricting labour scheduling flexibility in terms of shift length, shift start-times, days-off, meal-break placement, and other factors. These restrictions were essential to the tractability of the heuristic approaches but often resulted in solutions that contained a substantial amount of excess labour. In this study, we relaxed many of the restrictions on scheduling flexibility assumed in previous studies. The resulting problem environment contained more than two billion allowable tours, precluding the use of previous heuristic methods. Consequently, we developed a simulated annealing heuristic for solving the problem. An important facet of this new approach is an ‘intelligent’ improvement routine which eliminates the need for long run-times typically associated with simulated annealing algorithms. The simulated annealing framework does not rely on a special problem structure and our implementation rapidly converged to near-optimal solutions for all problems in the test environment.     

A Savings Index Heuristic Algorithm for Flowshop Scheduling with Sequence Dependent Set-up Times

This paper considers the permutation flowshop scheduling problem with significant sequence dependent set-up times and develops a savings index heuristic algorithm to find an approximately minimum makespan schedule. The proposed algorithm determines the savings in time associated with a particular sequence and selects the sequence with the maximum time savings as the best heuristic solution. Computational experience indicating the effectiveness and efficiency of the proposed savings index heuristic algorithm are reported and discussed.     

Using a Hybrid Evolutionary Algorithm to Minimize Variance in Response Time for Multimedia Object Requests

This research addresses the scheduling problem of multimedia object requests, which is an important problem in information systems, in particular, for World Wide Web applications. The performance measure considered is the variance of response time which is crucial as end users expect fair treatment to their service requests. This problem is known to be NP-hard. The literature survey indicates that two heuristics have been proposed to solve the problem. In this paper, we present a new heuristic, a hybrid evolutionary heuristic, which is shown to perform much better than the two existing ones, e.g., the overall average errors of the existing ones are 1.012 and 2.042 while the error of the proposed hybrid evolutionary heuristic is 0.154.     

Learning heuristics for basic block instruction scheduling

Instruction scheduling is an important step for improving the performance of object code produced by a compiler. A fundamental problem that arises in instruction scheduling is to find a minimum length schedule for a basic block—a straight-line sequence of code with a single entry point and a single exit point—subject to precedence, latency, and resource constraints. Solving the problem exactly is known to be difficult, and most compilers use a greedy list scheduling algorithm coupled with a heuristic. The heuristic is usually hand-crafted, a potentially time-consuming process. In contrast, we present a study on automatically learning good heuristics using techniques from machine learning. In our study, a recently proposed optimal basic block scheduler was used to generate the machine learning training data. A decision tree learning algorithm was then used to induce a simple heuristic from the training data. The automatically constructed decision tree heuristic was compared against a popular critical-path heuristic on the SPEC 2000 benchmarks. On this benchmark suite, the decision tree heuristic reduced the number of basic blocks that were not optimally scheduled by up to 55% compared to the critical-path heuristic, and gave improved performance guarantees in terms of the worst-case factor from optimality.     

A production scheduling heuristic for an electronics manufacturer with sequence-dependent setup costs

In this paper, we develop a three-step heuristic to address a production scheduling problem at a high volume assemble-to-order electronics manufacturer. The heuristic provides a solution for scheduling multiple product families on parallel, identical production lines so as to minimize setup costs. The heuristic involves assignment, sequencing, and time scheduling steps, with an optimization approach developed for each step. For the most complex step, the sequencing step, we develop a greedy randomized adaptive search procedure (GRASP). We compare the setup costs resulting from the use of our scheduling heuristic against a heuristic previously developed and implemented at the electronics manufacturer that assumes approximately equal, sequence-independent, setup costs. By explicitly considering the sequence-dependent setup costs and applying GRASP, our empirical results show a reduction in setups costs for an entire factory of 14–21% with a range of single production line reductions from 0% to 49%.     

An Air Force Crew Allocation and Scheduling Problem

This paper considers an airline crew allocation and scheduling problem faced by certain divisions of the United States Air Force. Two variants of the problem under consideration were posed to us by the U.S. Air Force. This paper reports our experience with two heuristic methods developed, each applicable to either variant of the problem. Although the problem described herein is peculiar to this situation, the heuristic scheduling and dispatching rules developed have been found to be very effective and are generally applicable in other related contexts of routeing and crew and vehicle scheduling problems as well. The two algorithms developed have been applied to a coded set of real world data. The results indicate that each one of the two methods is preferable to the other for one of the two variants of the problem. This suggests an overall effective composite technique.     

Different Approaches to Advertising Media Selection

Research groups on both sides of the Atlantic are attempting to use the power of mathematics to aid the decision-maker in dealing with the complex media scheduling problem. This paper reviews, compares and critiques several possible approaches. The approaches reviewed are: linear programming, dynamic programming, marginal analysis, heuristic programming and simulation. At least one particular model of each approach is discussed in detail.     

Minimizing makespan in a two-machine flowshop scheduling with batching and release time

This paper studies two-machine flowshop scheduling with batching and release time, whose objective is to minimize the makespan. We formulate the scheduling problem as a mixed integer programming model and show that it is a strongly NP-hard problem. We derive a lower bound and develop dynamic programming-based heuristic algorithms to solve the scheduling problem. Computational experiments are carried out to evaluate the performance of the heuristic algorithms. The numerical results show that some of the heuristic algorithms can indeed find effective solutions for the scheduling problem.     

A self-adaptive differential evolution heuristic for two-stage assembly scheduling problem to minimize maximum lateness with setup times

The two-stage assembly flowshop scheduling problem has been addressed with respect to different criteria in the literature where setup times are ignored. For some applications, setup times are essential to be explicitly considered since they may take considerable amount of time. We address the two-stage assembly flowshop scheduling problem with respect to maximum lateness criterion where setup times are treated as separate from processing times. We formulate the problem and obtain a dominance relation. Moreover, we propose a self-adaptive differential evolution heuristic. To the best of our knowledge, this is the first attempt to use a self-adaptive differential evolution heuristic to a scheduling problem. We conduct extensive computational experiments to compare the performance of the proposed heuristic with those of particle swarm optimization (PSO), tabu search, and EDD heuristics. The computational analysis indicates that PSO performs much better than tabu and EDD. Moreover, the analysis indicates that the proposed self-adaptive differential evolution heuristic performs as good as PSO in terms of the average error while only taking one-third of CPU time of PSO.     

An exact branch-and-price algorithm for scheduling rescue units during disaster response

In disaster operations management, a challenging task for rescue organizations occurs when they have to assign and schedule their rescue units to emerging incidents under time pressure in order to reduce the overall resulting harm. Of particular importance in practical scenarios is the need to consider collaboration of rescue units. This task has hardly been addressed in the literature. We contribute to both modeling and solving this problem by (1) conceptualizing the situation as a type of scheduling problem, (2) modeling it as a binary linear minimization problem, (3) suggesting a branch-and-price algorithm, which can serve as both an exact and heuristic solution procedure, and (4) conducting computational experiments – including a sensitivity analysis of the effects of exogenous model parameters on execution times and objective value improvements over a heuristic suggested in the literature – for different practical disaster scenarios. The results of our computational experiments show that most problem instances of practically feasible size can be solved to optimality within ten minutes. Furthermore, even when our algorithm is terminated once the first feasible solution has been found, this solution is in almost all cases competitive to the optimal solution and substantially better than the solution obtained by the best known algorithm from the literature. This performance of our branch-and-price algorithm enables rescue organizations to apply our procedure in practice, even when the time for decision making is limited to a few minutes. By addressing a very general type of scheduling problem, our approach applies to various scheduling situations.     

A tabu-search heuristic for the flexible-resource flow shop scheduling problem

This paper presents a tabu-search heuristic for the flexible-resource flow shop scheduling (FRFS) problem [7]. The FRFS problem generalizes the classic flow shop scheduling problem by allowing job-operation processing times to depend on the amount of resource assigned to an operation; the objective is to determine simultaneously the job sequence, resource-allocation policy, and operation start times that optimize system performance. The tabu-search heuristic (TSH) employs a nested-search strategy based on a decomposition of the FRFS problem into these three components. We discuss computational experience with the THS procedure on more than 1600 test problems. The results show that TSH is effective in obtaining near-optimal solutions to the FRFS test problems. In particular, TSH generates optimal solutions for more than 70% of the test problems for which optimal solutions are known; overall, these solutions are within 0.3% of optimality on the average, and within 2.5% of optimality in the worst case.This research was supported in part by National Science Foundation grant SES90-22940.     

求解排课表问题的一个启发式数值算法

为了便于建立与排课表问题有关的决策支持系统,本文给出一个求解排课表问题的启发式数值算法,证明了算法的正确性,并举例说明算法的应用.该算法具有易于编程实现、收敛性好等优点,大量数值实值表明该算法能求得问题的最优解.     

Scatter Search and Bionomic Algorithms for the aircraft landing problem

The problem of deciding how to land aircraft approaching an airport involves assigning each aircraft to an appropriate runway, computing a landing sequence for each runway and scheduling the landing time for each aircraft. Runway allocation, sequencing and scheduling for each aircraft must ensure the scheduled landing time lies within a predefined time window and meet separation time requirements with other aircraft. The objective is to achieve effective runway use.In this paper, the multiple runway case of the static Aircraft Landing Problem is considered. Two heuristic techniques are presented: Scatter Search and the Bionomic Algorithm, population heuristic approaches that have not been applied to this problem before.Computational results are presented for publicly available test problems involving up to 500 aircraft and five runways showing that feasible solutions of good quality can be produced relatively quickly.