An O(n) algorithm for the variable common due date,minimal tardy jobs bicriteria two-machine flow shop problem with ordered machines

We consider the ordinary NP- hard two-machine flow shop problem with the objective of determining simultaneously a minimal common due date and the minimal number of tardy jobs. We present an O(n²) algorithm for the problem when the machines are ordered, that is, when each job has its smaller processing time on the first (second) machine. We also discuss the applicability of the proposed algorithm to the corresponding single-objective problem in which the common due date is given.     

Minimizing maximum completion time in a proportionate flow shop with one machine of different speed

A flow shop with identical machines is called a proportionate flow shop. In this paper, we consider the variant of the n-job, m-machine proportionate flow shop scheduling problem in which only one machine is different and job processing times are inversely proportional to machine speeds. The objective is to minimize maximum completion time. We describe some optimality conditions and show that the problem is NP-complete. We provide two heuristic procedures whose worst-case performance ratio is less than two. Extensive experiments with various sizes are conducted to show the performance of the proposed heuristics.     

The just-in-time scheduling problem in a flow-shop scheduling system

We study the problem of maximizing the weighted number of just-in-time (JIT) jobs in a flow-shop scheduling system under four different scenarios. The first scenario is where the flow-shop includes only two machines and all the jobs have the same gain for being completed JIT. For this scenario, we provide an O(n³) time optimization algorithm which is faster than the best known algorithm in the literature. The second scenario is where the job processing times are machine-independent. For this scenario, the scheduling system is commonly referred to as a proportionate flow-shop. We show that in this case, the problem of maximizing the weighted number of JIT jobs is NP-hard in the ordinary sense for any arbitrary number of machines. Moreover, we provide a fully polynomial time approximation scheme (FPTAS) for its solution and a polynomial time algorithm to solve the special case for which all the jobs have the same gain for being completed JIT. The third scenario is where a set of identical jobs is to be produced for different customers. For this scenario, we provide an O(n³) time optimization algorithm which is independent of the number of machines. We also show that the time complexity can be reduced to O(n log n) if all the jobs have the same gain for being completed JIT. In the last scenario, we study the JIT scheduling problem on m machines with a no-wait restriction and provide an O(mn²) time optimization algorithm.     

Scheduling linearly shortening jobs under precedence constraints

We consider the problem of scheduling a set of dependent jobs on a single machine with the maximum completion time criterion. The processing time of each job is variable and decreases linearly with respect to the starting time of the job. Applying a uniform approach based on the calculation of ratios of expressions that describe total processing times of chains of jobs, we show basic properties of the problem. On the basis of these properties, we prove that if precedence constraints among jobs are in the form of a set of chains, a tree, a forest or a series–parallel digraph, the problem can be solved in O(n log n) time, where n denotes the number of the jobs.     

Single-machine and two-machine flowshop scheduling with general learning functions

We show that the O(n log n) (where n is the number of jobs) shortest processing time (SPT) sequence is optimal for the single-machine makespan and total completion time minimization problems when learning is expressed as a function of the sum of the processing times of the already processed jobs. We then show that the two-machine flowshop makespan and total completion time minimization problems are solvable by the SPT sequencing rule when the job processing times are ordered and job-position-based learning is in effect. Finally, we show that when the more specialized proportional job processing times are in place, then our flowshop results apply also in the more general sum-of-job-processing-times-based learning environment.     

Problem F2∥Cmax with forbidden jobs in the first or last position is easy

Saadani et al. [N.E.H. Saadani, P. Baptiste, M. Moalla, The simple F2∥C_max with forbidden tasks in first or last position: A problem more complex that it seems, European Journal of Operational Research 161 (2005) 21–31] studied the classical n-job flow shop scheduling problem F2∥C_max with an additional constraint that some jobs cannot be placed in the first or last position. There exists an optimal job sequence for this problem, in which at most one job in the first or last position is deferred from its position in Johnson’s [S.M. Johnson, Optimal two- and three-stage production schedules with setup times included, Naval Research Logistics Quarterly 1 (1954) 61–68] permutation. The problem was solved in O(n²) time by enumerating all candidate job sequences. We suggest a simple O(n) algorithm for this problem provided that Johnson’s permutation is given. Since Johnson’s permutation can be obtained in O(n log n) time, the problem in Saadani et al. (2005) can be solved in O(n log n) time as well.     

A note on single-machine scheduling with job-dependent learning effects

Mosheiov and Sidney (2003) showed that the makespan minimization problem with job-dependent learning effects can be formulated as an assignment problem and solved in O(n³) time. We show that this problem can be solved in O(nlog n) time by sequencing the jobs according to the shortest processing time (SPT) order if we utilize the observation that the job-dependent learning rates are correlated with the level of sophistication of the jobs and assume that these rates are bounded from below. The optimality of the SPT sequence is also preserved when the job-dependent learning rates are inversely correlated with the level of sophistication of the jobs and bounded from above.     

A matheuristic approach for the two-machine total completion time flow shop problem

This paper deals with the two-machine total completion time flow shop problem. We present a so-called matheuristic post processing procedure that improves the objective function value with respect to the solutions provided by state of the art procedures. The proposed procedure is based on the positional completion times integer programming formulation of the problem with O(n ²) variables and O(n) constraints.     

A polynomial algorithm for a two-machine no-wait job-shop scheduling problem

This paper considers the no-wait scheduling of n jobs, where each job is a chain of unit processing time operations to be processed alternately on two machines. The objective is to minimize the mean flow time. We propose an O(n⁶)-time algorithm to produce an optimal schedule. It is also shown that if zero processing time operations are allowed, then the problem is NP-hard in the strong sense.     

Generalization of Johnson's and Talwar's scheduling rules in two-machine stochastic flow shops

The paper deals with the classical problem of minimizing the makespan in a two-machine flow shop. When the job processing times are deterministic, the optimal job sequence can be determined by applying Johnson's rule. When they are independent and exponential random variables, Talwar's rule yields a job sequence that minimizes the makespan stochastically. Assuming that the random job processing times are independent and Gompertz distributed, we propose a new scheduling rule that is a generalization of both Johnson's and Talwar's rules. We prove that our rule yields a job sequence that minimizes the makespan stochastically. Extensions to m-machine proportionate stochastic flow shops, two-machine stochastic job shops, and stochastic assembly systems are indicated.     

Scheduling for fabrication and assembly in a two-machine flowshop with a fixed job sequence

This paper studies a problem of scheduling fabrication and assembly operations in a two-machine flowshop, subject to the same predetermined job sequence on each machine. In the manufacturing setting, there are n products, each of which consists of two components: a common component and a unique component which are fabricated on machine 1 and then assembled on machine 2. Common components of all products are processed in batches preceded by a constant setup time. The manufacturing process related to each single product is called a job. We address four regular performance measures: the total job completion time, the maximum job lateness, the total job tardiness, and the number of tardy jobs. Several optimality properties are presented. Based upon the concept of critical path and block schedule, a generic dynamic programming algorithm is developed to find an optimal schedule in O(n ⁷) time.     

Approximability of single machine scheduling with fixed jobs to minimize total completion time

We consider the single machine scheduling problem to minimize total completion time with fixed jobs, precedence constraints and release dates. There are some jobs that are already fixed in the schedule. The remaining jobs are free to be assigned to any free-time intervals on the machine in such a way that they do not overlap with the fixed jobs. Each free job has a release date, and the order of processing the free jobs is restricted by the given precedence constraints. The objective is to minimize the total completion time. This problem is strongly NP-hard. Approximability of this problem is studied in this paper. When the jobs are processed without preemption, we show that the problem has a linear-time n-approximation algorithm, but no pseudopolynomial-time (1 − δ)n-approximation algorithm exists even if all the release dates are zero, for any constant δ > 0, if P ≠ NP, where n is the number of jobs; for the case that the jobs have no precedence constraints and no release dates, we show that the problem has no pseudopolynomial-time (2 − δ)-approximation algorithm, for any constant δ > 0, if P ≠ NP, and for the weighted version, we show that the problem has no polynomial-time 2^q(n)-approximation algorithm and no pseudopolynomial-time q(n)-approximation algorithm, where q(n) is any given polynomial of n. When preemption is allowed, we show that the problem with independent jobs can be solved in O(n log n) time with distinct release dates, but the weighted version is strongly NP-hard even with no release dates; the problems with weighted independent jobs or with jobs under precedence constraints are shown having polynomial-time n-approximation algorithms. We also establish the relationship of the approximability between the fixed job scheduling problem and the bin-packing problem.     

Enumerating K best paths in length order in DAGs

We address the problem of finding the K best paths connecting a given pair of nodes in a directed acyclic graph (DAG) with arbitrary lengths. One of the main results in this paper is the proof that a tree representing the kth shortest path is obtained by an arc exchange in one of the previous (k − 1) trees (each of which contains a previous best path). An O(m + K(n + log K)) time and O(K + m) space algorithm is designed to explicitly determine the K shortest paths in a DAG with n nodes and m arcs. The algorithm runs in O(m + Kn) time using O(K + m) space in DAGs with integer length arcs. Empirical results confirming the superior performance of the algorithm to others found in the literature for randomly generated graphs are reported.     

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.     

Single machine scheduling problems with controllable processing times and total absolute differences penalties

In this paper, we consider single machine scheduling problem in which job processing times are controllable variables with linear costs. We concentrate on two goals separately, namely, minimizing a cost function containing total completion time, total absolute differences in completion times and total compression cost; minimizing a cost function containing total waiting time, total absolute differences in waiting times and total compression cost. The problem is modelled as an assignment problem, and thus can be solved with the well-known algorithms. For the case where all the jobs have a common difference between normal and crash processing time and an equal unit compression penalty, we present an O(n log n) algorithm to obtain the optimal solution.     

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.     

Complexity results and approximation algorithms for the two machine no-wait flow-shop with limited machine availability

The scheduling problems studied in this paper concern a two-machine no-wait flow shop problem with limited machine availability. In this model, we assume that machines may not always be available, for example because of preventive maintenance. We only consider the deterministic case where the unavailable periods are known in advance. The objective function considered is the maximum completion time (C_max). We prove that the problem is NP-hard even if only one non-availability period occurs on one of machines, and NP-hard in the strong sense for arbitrary numbers of non-availability periods. We also provide heuristic algorithms with error bounding analysis.     

A note on two-machine no-wait flow shop scheduling with deteriorating jobs and machine availability constraints

This paper is concerned with two-machine no-wait flow shop scheduling problems in which the actual processing time of each job is a proportional function of its starting time and each machine may have non-availability intervals. The objective is to minimize the makespan. We assume that the non-availability intervals are imposed on only one machine. Moreover, the number of non-availability intervals, the start time and end time of each interval are known in advance. We show that the problem with a single non-availability interval is NP-hard in the ordinary sense and the problem with an arbitrary number of non-availability intervals is NP-hard in the strong sense.     

Preemptive scheduling of two uniform parallel machines to minimize total tardiness

We consider the problem of preemptive scheduling n jobs on two uniform parallel machines. All jobs have equal processing requirements. For each job we are given its due date. The objective is to find a schedule minimizing total tardiness ∑T_i. We suggest an O(n log n) algorithm to solve this problem.