Two-stage assembly-type flowshop batch scheduling problem subject to a fixed job sequence

This paper discusses a two-stage assembly-type flowshop scheduling problem with batching considerations subject to a fixed job sequence. The two-stage assembly flowshop consists of m stage-1 parallel dedicated machines and a stage-2 assembly machine which processes the jobs in batches. Four regular performance metrics, namely, the total completion time, maximum lateness, total tardiness, and number of tardy jobs, are considered. The goal is to obtain an optimal batching decision for the predetermined job sequence at stage 2. This study presents a two-phase algorithm, which is developed by coupling a problem-transformation procedure with a dynamic program. The running time of the proposed algorithm is O(mn+n⁵), where n is the number of jobs.     

Minimizing total completion time in a no-wait flowshop with sequence-dependent additive changeover times

This paper addresses the problem of minimizing total completion time in a two-machine no-wait flowshop where setup times of the jobs are sequence-dependent. Optimal solutions are obtained for two special flowshops and a dominance relation is developed for the general problem. Several heuristic algorithms with the computational complexity of O(n²) and O(n³) are constructed. The heuristics consist of two phases: in the first phase a starting list is developed and in the second a repeated insertion technique is applied. Computational experience demonstrates that the concept of repeated insertion application is quite useful for any starting list and that solutions for all starting lists converge to about the same value of less than 1% after a few iterations.     

Minimizing the number of early jobs on a proportionate flowshop

A proportionate flowshop is a special case of the classical flowshop, where the job processing times are machine-independent. We study the problem of minimizing the number of early jobs in this machine setting. This objective function has hardly been investigated on a single machine, and never on a flowshop. We introduce an efficient iterative solution algorithm. In each iteration, a single job is moved to the first position (and is added to the set of early jobs), and the remaining jobs are rescheduled such that the maximum earliness is minimized. The algorithm guarantees an optimal solution in O(n³) time, where n is the number of jobs.     

No-wait flowshops with bicriteria of makespan and total completion time

We consider the m-machine no-wait flowshop scheduling problem with the objective of minimizing a weighted sum of makespan and total completion time. For the two-machine problem, we develop a dominance relation and embed it within a proposed branch-and-bound algorithm. For the m-machine problem, we propose a heuristic. Computational experiments show that the proposed heuristic outperforms the best existing multi-criteria heuristics and the best single criterion heuristics for makespan and total completion time. The efficiency of the dominance relation and branch-and-bound algorithm is also investigated and shown to be effective.     

NP-hard cases in scheduling deteriorating jobs on dedicated machines

In this paper problems of time-dependent scheduling on dedicated machines are considered. The processing time of each job is described by a function which is dependent on the starting time of the job. The objective is to minimise the maximum completion time (makespan). We prove that under linear deterioration the two-machine flow shop problem is strongly NP-hard and the two-machine open shop problem is ordinarily NP-hard. We show that for the three-machine flow shop and simple linear deterioration there does not exist a polynomial-time approximation algorithm with the worst case ratio bounded by a constant, unless P=NP. We also prove that the three-machine open shop problem with simple linear deterioration is ordinarily NP-hard, even if the jobs have got equal deterioration rates on the third machine.     

Solutions to the Constrained Flowshop Sequencing Problem

If the flowshop sequencing problem is constrained so that job profiles are maintained independently of other work on the shop, then a range of new problem solutions are possible. Using geometrical relationships between the cumulative process times, a slope matching method has been devised which generally provides better results than Palmer's method and Gupta's algorithm. Secondly, it has been possible to reformulate the flowshop sequencing problem in terms of the travelling salesman problem. This has enabled the performance of the slope matching, Palmer and Gupta methods to be compared against a non-heuristic solution. Finally, provided that expressing a job in terms of the slopes of the cumulative start and end times is satisfactory, this enables in n-job, M-machine flowshop to be converted into an equivalent n-job 2 machine flowshop to which the use of Johnson's method will provide optimal sequences.     

The Systems Approach to Hospitals

By exploiting the relationship between scheduling and sorting, this paper describes a functional heuristic algorithm for seeking a quick and approximate solution to the n-job, M-machine flowshop scheduling problem under the assumption that all jobs are processed on all machines in the same order and no passing of jobs is permitted. The proposed functional heuristic algorithm can be executed by hand for reasonably large size problems and yields solutions which are closer to optimal solutions than those obtained by Palmer's slope index algorithm.     

Two-stage flexible flow shop scheduling subject to fixed job sequences

This paper investigates the scheduling problem in a two-stage flexible flow shop, which consists of m stage-1 parallel dedicated machines and a stage-2 bottleneck machine, subject to the condition that n _l jobs per type l∈{1, …, m} are processed in a fixed sequence. Four regular performance metrics, including the total completion time, the maximum lateness, the total tardiness, and the number of tardy jobs, are considered. For each considered objective function, we aim to determine an optimal interleaving processing sequence of all jobs coupled with their starting times on the stage-2 bottleneck machine. The problem under study is proved to be strongly NP-hard. An O(m²Π_l=1 ^m n _l ²) dynamic programming algorithm coupled with numerical experiments is presented.     

Mappings of preserving <Emphasis Type="Italic">n</Emphasis>-distance one in <Emphasis Type="Italic">n</Emphasis>-normed spaces

We give a positive answer to the Aleksandrov problem in n-normed spaces under the surjectivity assumption. Namely, we show that every surjective mapping preserving n-distance one is affine, and thus is an n-isometry. This is the first time the Aleksandrov problem is solved in n-normed spaces with only the surjectivity assumption even in the usual case \(n=2\). Finally, when the target space is n-strictly convex, we prove that every mapping preserving two n-distances with an integer ratio is an affine n-isometry.     

Specially Structured Precedence Constraints in Three-Dimensional Bottleneck Assignment Problems

A three-dimensional, time-minimizing (bottleneck) assignment problem consists of assigning n jobs to n workers to be performed on n machines under different forms of feasibility conditions so that the different functions of the individual times taken by a worker to finish a job on a given machine are minimized. The usual assumption made in such a problem is that all the jobs can be commenced simultaneously. In this paper, two specially structured precedence constraints on jobs are considered, which necessitate modifications in this assumption. Further, the main purpose here is to develop branch-and-bound-type algorithms for solving the corresponding problems and to illustrate them by a numerical example.     

Scheduling jobs with release dates,equal processing times,and inclusive processing set restrictions

We consider the problem of scheduling a given set of n jobs with equal processing times on m parallel machines so as to minimize the makespan. Each job has a given release date and is compatible to only a subset of the machines. The machines are ordered and indexed in such a way that a higher-indexed machine can process all the jobs that a lower-indexed machine can process. We present a solution procedure to solve this problem in O(n²+mnlogn) time. We also extend our results to the tree-hierarchical processing sets case and the uniform machine case.     

Two-machine flowshop scheduling to minimize the number of tardy jobs

We consider the two-machine flowshop problem with the objective of minimizing the total number of tardy jobs. Since this problem is known to be strongly NP-hard, algorithms are described for four polynomially solvable special cases. In addition, several heuristic algorithms are developed to find optimal or near optimal schedules. Results of computational tests in solving problems up to 60 jobs are reported and directions for future research are provided.     

Due-date assignment with asymmetric earliness–tardiness cost

The problem of minimizing the maximal weighted absolute lateness (MWAL) is known to be NP-hard. The due-date assignment part of MWAL for a given sequence has been shown in the literature to be solved on a single machine in O(n²) time. In this paper, we study a more general version of the problem with asymmetric cost (nonidentical earliness and tardiness weights). We introduce a linear-programming-based O(n) solution for this case. We also extend our proposed solution procedure to other machine settings such as flow-shop and parallel machines.     

Two-machine open shop scheduling with special transportation times

The paper considers a problem of scheduling n jobs in a two-machine open shop to minimise the makespan, provided that preemption is not allowed and the interstage transportation times are involved. In general, this problem is known to be NP-hard. We present a linear time algorithm that finds an optimal schedule if no transportation time exceeds the smallest of the processing times. We also describe an algorithm that creates a heuristic solution to the problem with job-independent transportation times. Our algorithm provides a worst-case performance ratio of 8/5 if the transportation time of a job depends on the assigned processing route. The ratio reduces to 3/2 if all transportation times are equal.     

New MILP models for the permutation flowshop problem

Two new mixed-integer linear programming (MILP) models for the regular permutation flowshop problem, called TBA and TS3, are derived using a combination of JAML (job-adjacency, machine-linkage) diagrams and variable substitution techniques. These new models are then compared to the incumbent best MILP models (Wilson, WST2, and TS2) for this problem found in the flowshop sequencing literature. We define the term best to mean that a particular model or set of models can solve a common set of test flowshop problems in significantly less time than other competing models. In other words, the two new MILP models (TBA and TS3) become the challengers to the current incumbent best models (Wilson, WST2, TS2.). Both new models are shown to require less time, on average, than the current best models for solving this set of problems; and the TS3 model is shown to solve these problems in statistically significantly less time than the other four models combined.     

Balancing Workloads and Minimizing Set-up Costs in the Parallel Processing Shop

This paper presents an optimal scheduling algorithm for minimizing set-up costs in the parallel processing shop while meeting workload balancing restrictions.There are M independent batch type jobs which have sequence dependent set-up costs and N parallel processing machines. Each of the M jobs must be processed on exactly one of the N available machines. It is desirable to minimize total changeover costs with the restriction that each machine workload assignment T _n be within P units of the average machine assignment. The paper describes a static problem in which all jobs are available at time zero. The sequence dependent change over costs are identical for each machine. An extension of the algorithm handles nonidentical processor problems.A combinatorial programming approach to the problem is used. For the special case of identical processors, the problem can be treated as a multi-salesman travelling salesman problem. A general branch and bound algorithm and numerical results are given.     

Stochastically minimizing total flowtime in flowshops with no waiting space

The problem of scheduling n jobs in a two-machine flowshop with constant and known processing times is considered with the total flowtime performance measure. The machines are subject to random breakdowns and there is no waiting space between them. The problem is formulated and an expression for the completion time of the jobs is obtained in terms of the processing times and the breakdown elements. Provided that the counting processes associated with both machines have stationary increments property, a sequence that stochastically minimizes the performance criterion is established for the cases when only the first or the second machine suffers breakdowns.     

Complexity of scheduling of coupled tasks with chains precedence constraints and any constant length of gap

Coupled tasks scheduling was originally introduced for modelling complex radar devices. It is still used for controlling such devices and applied in similar applications. This paper considers a problem of coupled tasks scheduling on one processor, under the assumptions that all processing times are equal to 1, the gap has a constant exact length and the precedence constraints are strict. Although it is proven that the problem stated above is NP-hard in the strong sense if the precedence constraints have a form of a general graph, it is possible to solve some of its relaxed versions in polynomial time. This paper contains a solution for the problem of coupled tasks scheduling with an assumption that the precedence constraints graph has a form of chains and it presents an algorithm that can solve the problem with such assumption in time O(n?log?n).     

Lower Bounds for the Degree of a Branched Covering of a Manifold

The problem of finding new lower bounds for the degree of a branched covering of a manifold in terms of the cohomology rings of this manifold is considered. This problem is close to M. Gromov’s problem on the domination of manifolds, but it is more delicate. Any branched (finite-sheeted) covering of manifolds is a domination, but not vice versa (even up to homotopy). The theory and applications of the classical notion of the group transfer and of the notion of transfer for branched coverings are developed on the basis of the theory of n-homomorphisms of graded algebras.The main result is a lemma imposing conditions on a relationship between the multiplicative cohomology structures of the total space and the base of n-sheeted branched coverings of manifolds and, more generally, of Smith–Dold n-fold branched coverings. As a corollary, it is shown that the least degree n of a branched covering of the N-torus T ^N over the product of k 2-spheres and one (N ? 2k)-sphere for N ≥ 4k + 2 satisfies the inequality n ≥ N ? 2k, while the Berstein–Edmonds well-known 1978 estimate gives only n ≥ N/(k + 1).     

Batch scheduling with controllable setup and processing times to minimize total completion time

We study a problem of scheduling n jobs on a single machine in batches. A batch is a set of jobs processed contiguously and completed together when the processing of all jobs in the batch is finished. Processing of a batch requires a machine setup time dependent on the position of this batch in the batch sequence. Setup times and job processing times are continuously controllable, that is, they are real-valued variables within their lower and upper bounds. A deviation of a setup time or job processing time from its upper bound is called a compression. The problem is to find a job sequence, its partition into batches, and the values for setup times and job processing times such that (a) total job completion time is minimized, subject to an upper bound on total weighted setup time and job processing time compression, or (b) a linear combination of total job completion time, total setup time compression, and total job processing time compression is minimized. Properties of optimal solutions are established. If the lower and upper bounds on job processing times can be similarly ordered or the job sequence is fixed, then O(n³ log n) and O(n⁵) time algorithms are developed to solve cases (a) and (b), respectively. If all job processing times are fixed or all setup times are fixed, then more efficient algorithms can be devised to solve the problems.