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 A min‐sum controllable risk problem, defined on a given set of elements or on combinatorial structures, which are either paths of a directed acyclic graph or spanning trees of an undirected graph, with resource‐dependent risk functions of the elements, is studied. The resource amount is limited, and the objective is to distribute it between the selected elements or elements of the selected structure so that the total risk is minimized. A reduction to a series of easier problems is suggested. Solution approaches based on this reduction are asymptotically faster than the solution approaches suggested in the literature for special cases of this problem.

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 problem of scheduling unit-time jobs with given release dates and deadlines on identical parallel machines. No machine can stand idle between its start and completion times. The objective is to minimize the number of machines in use. A number of properties of this problem is established, and heuristic and optimal algorithms based on these properties are developed. They include optimal exponential algorithms for the general case and optimal polynomial algorithms for special cases. Lower and upper bounds are determined and an integer linear programming formulation is provided.

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.

We study the Simplified Partial Digest Problem (SPDP), which is a mathematical model for a new simplified partial digest method of genome mapping. This method is easy for laboratory implementation and robust with respect to the experimental errors. SPDP is NP-hard in the strong sense. We present an $O(n2;n)$ time enumerative algorithm and an O(n(2q)) time dynamic programming algorithm for the error-free SPDP, where $n$ is the number of restriction sites and n is the number of distinct intersite distances. We also give examples of the problem, in which there are 2(n+2)/(3)-1 non-congruent solutions. These examples partially answer a question recently posed in the literature about the number of solutions of SPDP. We adapt our enumerative algorithm for handling SPDP with imprecise input data. Finally, we describe and discuss the results of the computer experiments with our algorithms.

We study problems of scheduling jobs on identical parallel machines, in which a due window has to be assigned to each job. If a job is completed within its due window, then it incurs no scheduling cost. Otherwise, it incurs earliness or tardiness cost. Two due window models are considered. In both models, the due window size is a decision variable common for all jobs. In the first model, called a constant due window, the due window starting time is a decision variable common for all jobs, and in the second, called a slack due window, the due window starting time is equal to the job processing time plus a decision variable common for all jobs. The objective is to find a job schedule as well as the size and location(s) of the due window(s) such that a weighted maximum or sum of costs associated with job earliness, job tardiness, and due window size is minimized. We establish the properties of optimal solutions of these minmax and minsum problems. For a constant due window model, we prove that the minmax problem with arbitrary weights and the minsum problem with equal weights are polynomially equivalent to the classical parallel machine scheduling problem to minimize the makespan. We further show that the problems for a constant due window model and slack due window model with the same objective function are reversible in the sense that their optimal solutions are mirror images of each other. These results imply O(n) and O(n log n) time algorithms for the considered problems when m=1.

The problem of optimal scheduling n independent malleable tasks in a parallel processor system is studied. It is assumed that an execution of any task can be preempted and the number of processors allocated to the same task can change during its execution. We present a rectangle packing algorithm, which converts an optimal solution for the relaxed problem, in which the number of processors allocated to a task is not required to be integer, into an optimal solution for the original problem in O(n) time.