An approximation algorithm for the m-machine permutation flow shop scheduling problem with controllable processing times

The paper deals with the m-machine permutation flow shop scheduling problem in which job processing times, along with a processing order, are decision variables. It is assumed that the cost of processing a job on each machine is a linear function of its processing time and the overall schedule cost to be minimized is the total processing cost plus maximum completion time cost. A algorithm for the problem with m = 2 is provided; the best approximation algorithm until now has a worst-case performance ratio equal to . An extension to the m-machine (m ≥2) permutation flow shop problem yields an approximation algorithm with a worst-case bound equal to

Full-size image

, where is the worst-case performance ratio of a procedure used, in the proposed algorithm, for solving the (pure) sequencing problem. Moreover, examples which achieve this bound for = 1 are also presented.     

Approximation algorithms for two-machine flow shop scheduling with batch setup times

In many practical situations, batching of similar jobs to avoid setups is performed while constructing a schedule. This paper addresses the problem of non-preemptively scheduling independent jobs in a two-machine flow shop with the objective of minimizing the makespan. Jobs are grouped into batches. A sequence independent batch setup time on each machine is required before the first job is processed, and when a machine switches from processing a job in some batch to a job of another batch. Besides its practical interest, this problem is a direct generalization of the classical two-machine flow shop problem with no grouping of jobs, which can be solved optimally by Johnson's well-known algorithm. The problem under investigation is known to be NP-hard. We propose two O(n logn) time heuristic algorithms. The first heuristic, which creates a schedule with minimum total setup time by forcing all jobs in the same batch to be sequenced in adjacent positions, has a worst-case performance ratio of 3/2. By allowing each batch to be split into at most two sub-batches, a second heuristic is developed which has an improved worst-case performance ratio of 4/3. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.     

The hybrid flow shop scheduling problem

The scheduling of flow shops with multiple parallel machines per stage, usually referred to as the hybrid flow shop (HFS), is a complex combinatorial problem encountered in many real world applications. Given its importance and complexity, the HFS problem has been intensively studied. This paper presents a literature review on exact, heuristic and metaheuristic methods that have been proposed for its solution. The paper briefly discusses and reviews several variants of the HFS problem, each in turn considering different assumptions, constraints and objective functions. Research opportunities in HFS are also discussed.     

A note on the two-stage assembly flow shop scheduling problem with uniform parallel machines

We study the problem of minimizing the makespan in a two-stage assembly flow shop scheduling problem with uniform parallel machines. This problem is a generalization of the assembly flow shop problem with concurrent operations in the first stage and a single assembly operation in the second stage. We propose a heuristic with an absolute performance bound which becomes asymptotically optimal as the number of jobs becomes very large. We show that our results slightly improve earlier results for the simpler assembly flow shop problem (without uniform machines) and for the two-stage hybrid flow shop problem with uniform machines.     

Bounding strategies for the hybrid flow shop scheduling problem

In this paper, we investigate new lower and upper bounds for the multiple-center hybrid flow shop scheduling problem. We propose a family of center-based lower bounds as well as a destructive lower bound that is based on the concept of revised energetic reasoning. Also, we describe an optimization-based heuristic that requires iteratively solving a sequence of parallel machine problems with heads and tails. We present the results of extensive computational experiments that provide evidence that the proposed bounding procedures consistently improve the best existing ones.     

An improved delayed-start LPT algorithm for a partition problem on two identical parallel machines

We propose an off-line delayed-start LPT algorithm that sequences the first (longest) 5 jobs optimally and the remaining jobs according to the LPT principle on two identical parallel machines. We show that this algorithm has a sharper tight worst-case ratio bound than the traditional LPT algorithm for the sum of squares of machine completion times minimization problem.     

可转包两台流水作业机排序的近似算法

研究可转包的两台流水作业机排序问题, 目标是极小化最大完工时间和总外包费用之和. 首先给出最坏情况界为2的近似算法, 接着对工件满足有序化约束的情形给出最坏情况界为\frac{3}{2}的改进算法, 以上算法界均为紧界.     

A note on the proportionate flow shop with a bottleneck machine

Choi, B.-C., Yoon, S.-H., Chung, S.-J., 2007. Minimizing maximum completion time in a proportionate flow shop with one machine of different speed. European Journal of Operational Research 176, 964–974 consider the proportionate flow shop with a slow bottleneck machine and propose the SLDR heuristic for it. Choi et al. (2007) derive a data-dependent worst-case ratio bound for the SLDR heuristic which is then bounded by two. In this note, we show that the tight worst-case ratio bound of the SLDR heuristic is 3/2.     

The flow shop problem with no-idle constraints: A review and approximation

The makespan minimization problem in flow shops with no-idle constraints on machines is considered. The latter means that each machine, once started, must process all its operations without intermediate idle time until all those operations are completed. The problem is known to be strongly NP-hard already for three machines. While being based on a geometrical approach, we propose several polynomial time heuristics (for the general case and for special cases of 3 and 4 machines) which provide asymptotically optimal solutions for the increasing number of jobs. A comprehensive review of relevant results is also presented.     

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.     

Routing open shop and flow shop scheduling problems

We consider a generalization of the classical open shop and flow shop scheduling problems where the jobs are located at the vertices of an undirected graph and the machines, initially located at the same vertex, have to travel along the graph to process the jobs. The objective is to minimize the makespan. In the tour-version the makespan means the time by which each machine has processed all jobs and returned to the initial location. While in the path-version the makespan represents the maximum completion time of the jobs. We present improved approximation algorithms for various cases of the open shop problem on a general graph, and the tour-version of the two-machine flow shop problem on a tree. Also, we prove that both versions of the latter problem are NP-hard, which answers an open question posed in the literature.     

Analysis of some greedy algorithms for the single-sink fixed-charge transportation problem

The single-sink fixed-charge transportation problem (SSFCTP) consists of finding a minimum cost flow from a number of nodes to a single sink. Beside a cost proportional to the amount shipped, the flow cost encompass a fixed charge. The SSFCTP is an important subproblem of the well-known fixed-charge transportation problem. Nevertheless, just a few methods for solving this problem have been proposed in the literature. In this paper, some greedy heuristic solutions methods for the SSFCTP are investigated. It is shown that two greedy approaches for the SSFCTP known from the literature can be arbitrarily bad, whereas an approximation algorithm proposed in the literature for the binary min-knapsack problem has a guaranteed worst case bound if adapted accordingly to the case of the SSFCTP.     

A branch and bound algorithm for hybrid flow shop scheduling problem with setup time and assembly operations

A hybrid flow shop scheduling problem (HFSP) with assembly operations is studied in this paper. In the considered problem, a number of products of the same kind are produced. Each product is assembled using a set of several parts. At first, the parts are produced in a hybrid flow shop and then they are assembled in an assembly stage to produce products. The considered objective is to minimize the completion time of all products (makespan). This problem has been proved strongly NP-hard, so in order to solve it, a hierarchical branch and bound algorithm is presented. Also, some lower and upper bounds are developed to increase the efficiency of the proposed algorithm. The numerical experiments are used to evaluate the performance of the proposed algorithm.     

Approximation algorithms for a vehicle routing problem

In this paper we investigate a vehicle routing problem motivated by a real-world application in cooperation with the German Automobile Association (ADAC). The general task is to assign service requests to service units and to plan tours for the units such as to minimize the overall cost. The characteristics of this large-scale problem due to the data volume involve strict real-time requirements. We show that the problem of finding a feasible dispatch for service units starting at their current position and serving at most k requests is NP-complete for each fixed k ≥ 2. We also present a polynomial time (2k − 1)-approximation algorithm, where again k denotes the maximal number of requests served by a single service unit. For the boundary case when k equals the total number |E| of requests (and thus there are no limitations on the tour length), we provide a -approximation. Finally, we extend our approximation results to include linear and quadratic lateness costs.     

Two-machine flow shop scheduling problem with an outsourcing option

We consider a two-machine flow shop problem in which each job is processed through an in-house system or outsourced to a subcontractor. A schedule is established for the in-house jobs, and performance is measured by the makespan. Jobs processed by subcontractors require paying an outsourcing cost. The objective is to minimize the sum of the makespan and total outsourcing costs. We show that the problem is NP-hard in the ordinary sense. We consider a special case in which each job has a processing requirement, and each machine a characteristic value. In this case, the time a job occupies a machine is equal to the job’s processing requirement plus a setup time equal to the characteristic value of that machine. We introduce some optimality conditions and present a polynomial-time algorithm to solve the special case.     

Approximability of flow shop scheduling

Shop scheduling problems are notorious for their intractability, both in theory and practice. In this paper, we construct a polynomial approximation scheme for the flow shop scheduling problem with an arbitrary fixed number of machines. For the three common shop models (open, flow, and job), this result is the only known approximation scheme. Since none of the three models can be approximated arbitrarily closely in the general case (unless P = NP), the result demonstrates the approximability gap between the models in which the number of machines is fixed, and those in which it is part of the input of the instance. The result can be extended to flow shops with job release dates and delivery times and to flow shops with a fixed number of stages, where the number of machines at any stage is fixed. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.A preliminary version of this paper appeared in theProceedings of the 36th Annual IEEE Symposium on the Foundations of Computer Science, 1995.Research supported by NSF grant DMI-9496153.     

Approximation algorithms for dynamic resource allocation

We consider a problem of allocating limited quantities of M types of resources among N independent activities that evolve over T epochs. In each epoch, we assign to each activity a task which consumes resources, generates utility, and determines the subsequent state of the activity. We study the complexity of, and approximation algorithms for, maximizing average utility.     

Approximation algorithms for UET scheduling problems with exact delays

In this paper we consider coupled-task single-machine and two-machine flow shop scheduling problems with exact delays, unit processing times, and the makespan as an objective function. The main results of the paper are fast 7/4- and 3/2-approximation algorithms for solving the single- and two-machine problems, respectively.     

Approximation algorithms for scheduling problems with a modified total weighted tardiness objective

We study the approximability of minimum total weighted tardiness with a modified objective which includes an additive constant. This ensures the existence of a positive lower bound for the minimum value. Moreover the new objective has a natural interpretation in just-in-time production systems.