Abstract The order scheduling and rack sequencing problem deals with the order picking process in robotic mobile fulfillment systems: automated guided vehicles lift and transport movable storage racks to picking stations to supply items requested by customer orders which are put together in cardboard boxes on a workbench of limited capacity. To efficiently operate the station, the sequence in which racks visit the station one after another and the intervals at which customer orders are scheduled must be coordinated. We present a dynamic programming algorithm for the order scheduling and rack sequencing problem at a single picking station minimizing the number of rack visits. Despite monolithic mixed integer linear programming formulations, our approach appears to be the first combinatorial solution method for the problem in literature. A computational study demonstrates the effectiveness of the approach.

Abstract We study a problem of scheduling n jobs on machines of two types: in‐house machines and third‐party machines. Scheduling on in‐house machines incurs no additional costs, while using third‐party machines implies costs depending on their number and the time of usage. Each job has a fixed time interval for being processed which can be divided and allocated among several machines, as long as there is only one machine processing the job at any time. No machine can process more than one job at a time. Jobs can be rejected, and they are of different importance that is reflected in the weight of each job. The objective is to find a subset of the jobs and the number of third‐party machines for any period of time so that the accepted jobs can be feasibly scheduled, the total weight of the accepted jobs is maximized, and the total machine usage costs does not exceed a given upper bound. We also study a similar problem in which the objective is to maximize the total time at which at least one job is processed. Both problems are encountered in situations in which certain activities with given start and completion times have to be serviced by human operators. Examples are air traffic control and the monitoring safe vehicle unloading. Other examples are the employment of subcontractors in agriculture, construction or transportation. We will present NP‐hardness proofs, polynomial and pseudo‐polynomial optimal algorithms and an approximation algorithm for these problems and their special cases. These problems admit graph‐theoretical interpretations associated with finding independent sets and a proper vertex coloring in interval graphs.

We study a scheduling problem for a container block, in which there are incoming containers only. Container placement is served by two non‐passing stacking cranes based at the opposite sides of the container block. The same time is required for any crane to move between two adjacent bays of the container block and the same different time is required for any crane to perform any down‐and‐up operation related to container lifting at the pick‐up point or container lowering at the storage point. Containers are assigned to the cranes according to one of the following policies: (1) two fixed sequences policy where a container processing sequence is given for each crane, (2) dedicated crane policy where containers are preassigned to the cranes, (3) one fixed, one arbitrary sequence policy where a container processing sequence is given for one crane and it can be arbitrary for the other crane, (4) flexible policy where any container can be assigned to any crane at any time, and (5) global fixed sequence policy where the container sequence is given and the relative processing order of containers in this sequence must be preserved by any crane. The objective is to minimize the completion time of the latest operation. We show that the problem is polynomially solvable for policy 1 and, if the number of containers to be placed in the same bay is no more than a half of all containers, for policy 4. It is NP‐hard in the strong sense for policies 2 and 3. Approximation algorithms with guaranteed absolute and relative deviations from the optimum are devised for policies 4 and 5. The results translate for the case of outgoing containers only.

Unmanned aerial vehicles (UAVs), or aerial drones, are an emerging technology with significant market potential. UAVs may lead to substantial cost savings in, for instance, monitoring of difficult‐to‐access infrastructure, spraying fields and performing surveillance in precision agriculture, as well as in deliveries of packages. In some applications, like disaster management, transport of medical supplies, or environmental monitoring, aerial drones may even help save lives. In this article, we provide a literature survey on optimization approaches to civil applications of UAVs. Our goal is to provide a fast point of entry into the topic for interested researchers and operations planning specialists. We describe the most promising aerial drone applications and outline characteristics of aerial drones relevant to operations planning. In this review of more than 200 articles, we provide insights into widespread and emerging modeling approaches. We conclude by suggesting promising directions for future research.

BACKGROUND: Pairwise sequence alignment methods are widely used in biological research. The increasing number of sequences is perceived as one of the upcoming challenges for sequence alignment methods in the nearest future. To overcome this challenge several GPU (Graphics Processing Unit) computing approaches have been proposed lately. These solutions show a great potential of a GPU platform but in most cases address the problem of sequence database scanning and computing only the alignment score whereas the alignment itself is omitted. Thus, the need arose to implement the global and semiglobal Needleman-Wunsch, and Smith-Waterman algorithms with a backtracking procedure which is needed to construct the alignment. RESULTS: In this paper we present the solution that performs the alignment of every given sequence pair, which is a required step for progressive multiple sequence alignment methods, as well as for DNA recognition at the DNA assembly stage. Performed tests show that the implementation, with performance up to 6.3 GCUPS on a single GPU for affine gap penalties, is very efficient in comparison to other CPU and GPU-based solutions. Moreover, multiple GPUs support with load balancing makes the application very scalable. CONCLUSIONS: The article shows that the backtracking procedure of the sequence alignment algorithms may be designed to fit in with the GPU architecture. Therefore, our algorithm, apart from scores, is able to compute pairwise alignments. This opens a wide range of new possibilities, allowing other methods from the area of molecular biology to take advantage of the new computational architecture. Performed tests show that the efficiency of the implementation is excellent. Moreover, the speed of our GPU-based algorithms can be almost linearly increased when using more than one graphics card.

Assuming given production requirements for a set of part types, we examine the question of how these production requirements can be assigned to different, alternative routes through two production systems, a flexible manufacturing system, and a conventional job shop. Several nonlinear optimization models are proposed in order to optimize performance parameters like throughput, work-in-process inventory, utilization, and manufacturing lead time. The models incorporate product form queueing network theory in order to evaluate system performance and extend results based on linear programming formulations. The solution procedures are based on decomposition, fixed point, and classical gradient search techniques.

This paper examines the minimum makespan problem for the job shop from an artificial intelligence point of view. A new solution procedure is presented which combines general learning strategies with special purpose heuristics, i.e., a constraint propagation based procedure is used and by decomposing the whole problem into single machine problems, problem specific knowledge is introduced. Fundamental for this approach is the equivalency between the constraint and the disjunctive graph. Presented comprehensive computational tests show high quality partial solutions, substantially accelerated exact methods, and a gain of deeper insight into the nature of the underlying problem instances. For example, the propagation and decomposition techniques reveal the particular structure underlying the well-known Fisher and Thompson 10 × 10 problem and thus provide an explanation for why this problem was intractable for such a long time.

This paper considers the problem of partitioning the vertices of a weighted complete graph into cliques of unbounded size and number, such that the sum of the edge weights of all cliques is maximized. The problem is known as the clique-partitioning problem and arises as a clustering problem in qualitative data analysis. A simple greedy algorithm is extended to an ejection chain heuristic leading to optimal solutions in all practical test problems known from literature. The heuristic is used to compute an initial lower bound as well as to guide branching in a branch and bound algorithm which is superior to present exact methods. Empirical data for all three algorithms are reported. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.