1,721,015 research outputs found
Workload balancing and loop layout in the design of a flexible manufacturing system
No full textThis paper considers combined scheduling and machine layout problems in a flexible manufacturing system (FMS). All machines have the capability of performing several different types of operation. However, each operation type is to be assigned to only one of the machines, which are to be positioned around a unidirectional conveyor belt loop. For a known set of products, the primary objective is to maximise the throughput and the secondary objective is to minimise the movement of work between machines. Throughput is maximised by balancing workload, which indicates that the primary objective is equivalent to minimising the bottleneck workload. A three-phase integer programming model is derived. The first phase balances the machine workload by assigning operations to machines. The second phase minimises inter-machine travel, while respecting the workload balance attained in the first phase. In the third phase, machines are assigned to positions in the loop layout so that the total number of circuits made by the products is minimised. It is shown that this phase can be modelled as a linear ordering problem. The three-phase method is applied to a case study
Heuristics for a coupled-operation scheduling problem
No full textIn this paper, we study a strongly NP-hard single machine scheduling problem in which each job consists of two operations that are separated by a time delay which lies within a specified range. The objective is to minimise the makespan. Determining the feasibility and, if applicable, makespan of any proposed permutation of the operations is non-trivial, requiring a longest path algorithm with O(n^2) complexity for each permutation.Several heuristic algorithms are proposed: a deterministic and randomised construction algorithm, three descent algorithms and two reactive tabu search algorithms. The local search algorithms use a first improvement neighbourhood and mainly visit only feasible solutions within the search space. Results of extensive computational tests are reported, showing that the heavy computational burden of testing potential solutions renders the local search algorithms uncompetitive in comparison to the construction algorithms. The iterated descent algorithm performs least well
Batching decisions for assembly production systems
No full textThe two-stage assembly scheduling problem is a model for production processes that involve the assembly of final or intermediate products from basic components. In our model, there are m machines at the first stage that work in parallel, and each produces a component of a job. When all components of a job are ready, an assembly machine at the second stage completes the job by assembling the components. We study problems with the objective of minimizing the makespan, under two different types of batching that occur in some manufacturing environments. For one type, the time to process a batch on a machine is equal to the maximum of the processing times of its operations. For the other type, the batch processing time is defined as the sum of the processing times of its operations, and a setup time is required on a machine before each batch. For both models, we assume a batch availability policy, i.e., the completion times of the operations in a batch are defined to be equal to the batch completion time. We provide a fairly comprehensive complexity classification of the problems under the first type of batching, and we present a heuristic and its worst-case analysis under the second type of batching
Constraint satisfaction problems: algorithms and applications
No full textA constraint satisfaction problem requires a value, selected from a given finite domain, to be assigned to each variable in the problem, so that all constraints relating the variables are satisfied. Many combinatorial problems in operational research, such as scheduling and timetabling, can be formulated as constraint satisfaction problems. Researchers in artificial intelligence usually adopt a constraint satisfaction approach as their preferered method when tackling such problems. However constraint satisfaction approaches are not widely known amongst operational researchers. The aim of this paper is to introduce constraint satisfaction to the operational researchers
Driveable routes: solving shortest path problems in practice
No full textWith the increasing use of geographical information systems (GIS) and route planning software, users have demanded faster, more realistic routes. Traditionally, operational researchers have focused on developing fast exact and heuristic procedures for the point-to-point shortest path problem. To complement these advancements, we extend the functionality of route planning by describing a number of user-driven route planning requirements and an approach for handling them. A linear time graph modifcation technique is used for modelling routing problems within a real-life traffic network. The work facilitates 'driveable' routes. We also provide a simple heuristic for speeding-up Dijkstra's algorithm which does not rely on preprocessing. Our experiments on the UK road network indicate that optimality can be maintained in practice by considering on average only 12% of the search spac
Scheduling batches with sequential job processing for two-machine flow and open shops
No full textn this paper, we study a problem of scheduling and batching on two machines in a flow-shop and open-shop environment. Each machine processes operations in batches, and the processing time of a batch is the sum of the processing times of the operations in that batch. A setup time, which depends only on the machine, is required before a batch is processed on a machine, and all jobs in a batch remain at the machine until the entire batch is processed. The aim is to make batching and sequencing decisions, which specify a partition of the jobs into batches on each machine, and a processing order of the batches on each machine, respectively, so that the makespan is minimized. The flow-shop problem is shown to be strongly NP-hard. We demonstrate that there is an optimal solution with the same batches on the two machines; we refer to these as consistent batches. A heuristic is developed that selects the best schedule among several with one, two, or three consistent batches, and is shown to have a worst-case performance ratio of 4/3. For the open-shop, we show that the problem is NP-hard in the ordinary sense. By proving the existence of an optimal solution with one, two or three consistent batches, a close relationship is established with the problem of scheduling two or three identical parallel machines to minimize the makespan. This allows a pseudo-polynomial algorithm to be derived, and various heuristic methods to be suggested
A genetic algorithm for two-dimensional bin packing with due dates
No full textThis paper considers a new variant of the two-dimensional bin packing problem where each rectangle is assigned a due date and each bin has a fixed processing time. Hence the objective is not only to minimize the number of bins, but also to minimize the lateness of the rectangles. This problem is motivated by the potential increase efficiency that might be gained by mixing orders, while also aiming to ensure a certain level of customer service. We propose a genetic algorithm for searching the solution space, which uses a new placement heuristic for decoding the gene. The genetic algorithm employs an innovative crossover operator that considers a number of different children from each pair of parents. Comprehensive results are presented, and the algorithm is shown to be competitive when compared with other local search methods
Scheduling of customised jobs on a single machine under item availability
No full textWe study a problem of scheduling customized jobs on a single-machine. Each job requires two operations: one standard and one specific. Standard operations are processed in batches under item availability, and each batch requires a set-up time. Based on structural properties of the optimal solution, we introduce a generic dynamic programming scheme that builds an optimal schedule by alternately inserting blocks of operations of two distinct types. Our approach yields efficient algorithms for the sum of completion times problem with agreeable processing times and the maximum lateness problem. The number of late jobs problem is shown to be NP-hard in the ordinary sense, but is pseudo-polynomially solvable. A polynomial algorithm is also given for a special case of this problem. Our results indicate the differences between this problem and its counterpart under batch availability
A 3/2-approximation algorithm for two-machine flow-shop sequencing subject to release dates
No full textThe two-machine flow-shop sequencing problem with arbitrary release dates of jobs and the minimum makespan criterion is considered. The problem is known to be NP-hard, and the best-known approximation algorithms are those of Potts (Math. Oper. Res. 10 (1985) 576) with a worst-case performance ratio of 5/3 and running time O(n3 log n), and a polynomial time approximation scheme of Hall (Proceedings of the 36th Annual Symposium on Foundations of Computer Science, IEEE Comput. Soc. press, Los Alamitos, 1995, pp. 82–91.) that can generate solutions arbitrary close to the optimum but with a high-time requirement. In this paper, we modify Potts’ algorithm so that its worst-case performance ratio is reduced to 3/2, but its running time remains O(n3 log n)
Branch and bound algorithms for single machine scheduling with batching to minimize the number of late jobs
No full textThis paper considers the problem of scheduling a single machine to minimize the number of late jobs in the presence of sequence-independent family set-up times. The jobs are partitioned into families, and a set-up time is required at the start of each batch, where a batch is a maximal set of jobs in the same family that are processed consecutively. We design branch and bound algorithms that have several alternative features. Lower bounds can be derived by relaxing either the set-up times or the due dates. A first branching scheme uses a forward branching rule with a depth-first search strategy. Dominance criteria, which determine the order of the early jobs within each family and the order of the batches containing early jobs, can be fully exploited in this scheme. A second scheme uses a ternary branching rule in which the next job is fixed to be early and starting a batch, to be early and not starting a batch, or to be late. The different features are compared on a large set of test problems, where the number of jobs ranges from 30 to 50 and the number of families ranges from 4 to 10
- …
