New steps in the amazing world of sequences and schedules

In this paper we consider classical shop problems:n jobs have to be processed onm machines. The processing timep _i,j of jobi on machinej is given for all operations (i, j). Each machine can process at most one job at a time and each job can be processed at most on one machine at a given time. The machine orders are fixed (job-shop) or arbitrary (open-shop). We have to determine a feasible combination of machine and job orders, a so-called sequence, which minimizes the makespan. We introduce a partial order on the set of sequences with the property that there exists at least one optimal sequence in the set of minimal elements of this partial order independent of the given processing times. The set of minimal elements (set of irreducible sequences) can be in detail described in the case of the two machine open-shop problem. The cardinality is calculated. We will show which sequences are generated by the well-known polynomial algorithms for the construction of optimal schedules. Furthermore, we investigate the problemO∥C _max on an operation set with spanning tree structure. Supported by Deutsche Forschungsgemeinschaft, Project ScheMA     

Batching identical jobs

We study the problems of scheduling jobs, with different release dates and equal processing times, on two types of batching machines. All jobs of the same batch start and are completed simultaneously. On a serial batching machine, the length of a batch equals the sum of the processing times of its jobs and, when a new batch starts, a constant setup time s occurs. On a parallel batching machine, there are at most b jobs per batch and the length of a batch is the largest processing time of its jobs. We show that in both environments, for a large class of so called “ordered” objective functions, the problems are polynomially solvable by dynamic programming. This allows us to derive that the problems where the objective is to minimize the weighted number of late jobs, or the weighted flow time, or the total tardiness, or the maximal tardiness are polynomial. In other words, we show that 1|p-batch,b<n, r _i, p _i=p|F and 1|s-batch, r _i, p _i=p|F, are polynomial for F∈{∑w _i U _i,∑w _i C _i,∑T _i, T _max}. The complexity status of these problems was unknown before.     

Single machine scheduling under market uncertainty

This paper considers single machine scheduling problems where job processing times are known and deterministic but where the reward received upon completion of a job changes stochastically over time according to Brownian motion. The objectives of maximizing expected net-present-value (NPV), minimizing the variance of NPV and maximizing the probability of achieving a minimum benchmark NPV are considered. For non-preemptive static list policies complexity results and branch and bound procedures are presented. The branch and bound procedures are shown to be effective for problem instances with 20–25 jobs. For the problem of maximizing NPV with non-preemptive dynamic policies the optimal static schedule is shown through empirical testing to be as good as a greedy heuristic and to be near optimal when the variance is not large.     

Scheduling deteriorating jobs subject to job or machine availability constraints

We consider two problems of scheduling a set of independent, non-preemptable and proportionally deteriorating jobs on a single machine. In the first problem, the machine is not continuously available for processing but the number of non-availability periods, the start time and end time of each period are known in advance. In the second problem, the machine is available all the time but for each job a ready time and a deadline are defined. In both problems the criterion of schedule optimality is the maximum completion time. We show that the decision version of the first (the second) problem is NP-complete in the ordinary or in the strong sense, depending on the number of non-availability periods (the number of ready times and deadlines).     

General scheduling non-approximability results in presence of hierarchical communications

We investigate on the issue of minimizing the makespan (resp. the sum of the completion times) for the multiprocessor scheduling problem in presence of hierarchical communications. We consider a model with two levels of communication: interprocessor and intercluster. The processors are grouped in fully connected clusters. We propose general non-approximability results in the case where all the tasks of the precedence graph have unit execution times, and where the multiprocessor is composed of an unrestricted number of machines with l ? 4 identical processors each.     

A polynomial algorithm for some preemptive multiprocessor task scheduling problems

In this paper we consider a problem of preemptive scheduling of multiprocessor tasks on dedicated processors in order to minimize the sum of completion times. Using a standard notation, our problem can be denoted as P ∣ fix_j, pmtn ∣ ∑C_j. We give a polynomial-time algorithm to solve P ∣ fix_j, G = {P₄, dart}-free, pmtn ∣ ∑C_j problem. This result generalizes the following problems: P2 ∣ fix_j, pmtn ∣ ∑C_j, P ∣ ∣fix_j∣ ∈ {1, m}, pmtn ∣ ∑C_j and P4 ∣ fix_j = 2, pmtn ∣ ∑C_j.     

Planning the production of a fleet of domestic combined heat and power generators

This paper describes a planning problem, arising in the energy supply chain, that deals with the planning of the production runs of micro combined heat and power (microCHP) appliances installed in houses, cooperating in a fleet. Two types of this problem are described. The first one is the Single House Planning Problem (SHPP), where the focus is on supplying heat in the household. The second one combines many microCHPs into a Fleet Planning Problem (FPP) and focuses on the mutual electricity output, while still considering the local heat demand in the individual households. The problem is modeled as an ILP. For practical use a local search method is developed for the FPP, based on a dynamic programming formulation of the SHPP.     

Nonlinear programming methods in the presence of noise

The problem of minimizing a nonlinear function with nonlinear constraints when the values of the objective, the constraints and their gradients have errors, is studied. This noise may be due to the stochastic nature of the problem or to numerical error.Various previously proposed methods are reviewed. Generally, the minimization algorithms involve methods of subgradient optimization, with the constraints introduced through penalty, Lagrange, or extended Lagrange functions. Probabilistic convergence theorems are obtained. Finally, an algorithm to solve the general convex (nondifferentiable) programming problem with noise is proposed.Originally written for presentation at the 1976 Budapest Symposium on Mathematical Programming.     

Diffusion approximation for signaling stochastic networks

This paper introduces an unified approach to diffusion approximations of signaling networks. This is accomplished by the characterization of a broad class of networks that can be described by a set of quantities which suffer exchanges stochastically in time. We call this class stochastic Petri nets with probabilistic transitions, since it is described as a stochastic Petri net but allows a finite set of random outcomes for each transition. This extension permits effects on the network which are commonly interpreted as “routing” in queueing systems. The class is general enough to include, for instance, G-networks with negative customers and triggers as a particular case. With this class at hand, we derive a heavy traffic approximation, where the processes that drive the transitions are given by state-dependent Poisson-type processes and where the probabilities of the random outcomes are also state-dependent. The objective of this approach is to have a diffusion approximation which can be readily applied in several practical problems. We illustrate the use of the results with some numerical experiments.     

“Product Partition” and related problems of scheduling and systems reliability: Computational complexity and approximation

Problem Product Partition differs from the NP-complete problem Partition in that the addition operation is replaced by the multiplication operation. Furthermore it differs from the NP-complete problem Subset Product in that it does not contain the product value B in its input. We prove that problem Product Partition and several of its modifications are NP-complete in the strong sense. Our results imply the strong NP-hardness of a number of scheduling problems with start-time-dependent job processing times and a problem of designing a reliable system with a series–parallel structure. It should be noticed that the strong NP-hardness of the considered optimization problems does not preclude the existence of a fully polynomial time approximation scheme (FPTAS) for them. We present a simple FPTAS for one of these problems.     

Complexity of some parametric integer and network programming problems

Two examples of parametric cost programming problems—one in network programming and one in NP-hard 0-1 programming—are given; in each case, the number of breakpoints in the optimal cost curve is exponential in the square root of the number of variables in the problem. This research is partially supported by the Air Force Office of Scientic Research. Air Force Number AFOSR-78-3646     

Maximizing throughput in queueing networks with limited flexibility

We study a queueing network where customers go through several stages of processing, with the class of a customer used to indicate the stage of processing. The customers are serviced by a set of flexible servers, i.e., a server is capable of serving more than one class of customers and the sets of classes that the servers are capable of serving may overlap. We would like to choose an assignment of servers that achieves the maximal capacity of the given queueing network, where the maximal capacity is λ^∗ if the network can be stabilized for all arrival rates λ < λ^∗ and cannot possibly be stabilized for all λ > λ^∗. We examine the situation where there is a restriction on the number of servers that are able to serve a class, and reduce the maximal capacity objective to a maximum throughput allocation problem of independent interest: the total discrete capacity constrained problem (TDCCP). We prove that solving TDCCP is in general NP-complete, but we also give exact or approximation algorithms for several important special cases and discuss the implications for building limited flexibility into a system.     

Construction of factory schedules using reverse simulation

A real-world, multi-stage, industrial scheduling problem is presented. An algorithm is described that converts a sequence of jobs into a complete schedule. Backward simulation is used to determine minimum storage requirements when scheduling each job, and to calculate the minimum amount of delay required. Combining this algorithm with a metaheuristic, such as simulated annealing, results in an effective algorithm for schedule optimization.     

Searching for multiobjective preventive maintenance schedules: Combining preferences with evolutionary algorithms

Heavy industry maintenance facilities at aircraft service centers or railroad yards must contend with scheduling preventive maintenance tasks to ensure critical equipment remains available. The workforce that performs these tasks are often high-paid, which means the task scheduling should minimize worker idle time. Idle time can always be minimized by reducing the workforce. However, all preventive maintenance tasks should be completed as quickly as possible to make equipment available. This means the completion time should be also minimized. Unfortunately, a small workforce cannot complete many maintenance tasks per hour. Hence, there is a tradeoff: should the workforce be small to reduce idle time or should it be large so more maintenance can be performed each hour? A cost effective schedule should strike some balance between a minimum schedule and a minimum size workforce.     

Scheduling: Agreement graph vs resource constraints

We investigate two scheduling problems. The first is scheduling with agreements (SWA) that consists in scheduling a set of jobs non-preemptively on identical machines in a minimum time, subject to constraints that only some specific jobs can be scheduled concurrently. These constraints are represented by an agreement graph. We extend the NP-hardness of SWA with three distinct values of processing times to only two values and this definitely closes the complexity status of SWA on two machines with two fixed processing times. The second problem is the so-called resource-constrained scheduling. We prove that SWA is polynomially equivalent to a special case of the resource-constrained scheduling and deduce new complexity results of the latter.     

The value of the stochastic solution in stochastic linear programs with fixed recourse

Stochastic linear programs have been rarely used in practical situations largely because of their complexity. In evaluating these problems without finding the exact solution, a common method has been to find bounds on the expected value of perfect information. In this paper, we consider a different method. We present bounds on the value of the stochastic solution, that is, the potential benefit from solving the stochastic program over solving a deterministic program in which expected values have replaced random parameters. These bounds are calculated by solving smaller programs related to the stochastic recourse problem.This paper is an extension of part of the author's dissertation in the Department of Operations Research, Stanford University, Stanford, California. The research was supported at Stanford by the Department of Energy under Contract DE-AC03-76SF00326, PA#DE-AT03-76ER72018, Office of Naval Research under Contract N00014-75-C-0267 and the National Science Foundation under Grants MCS76-81259, MCS-7926009 and ECS-8012974 (formerly ENG77-06761).