Heuristic and stochastic methods in optimization

The shifting bottleneck (SB) heuristic is among the most successful approximation methods for solving the job shop problem. It is essentially a machine based decomposition procedure where a series of one machine sequencing problems (OMSPs) are solved. However, such a procedure has been reported to be highly ineffective for the flow shop problems. In particular, we show that for the 2-machine flow shop problem, the SB heuristic will deliver the optimal solution in only a small number of instances. We examine the reason behind the failure of the machine based decomposition method for the flow shop. An optimal machine based decomposition procedure is formulated for the 2-machine flow shop, the time complexity of which is worse than that of the celebrated Johnson’s rule. The contribution of the present study lies in showing that the same machine based decomposition procedures which are so successful in solving complex job shops can also be suitably modified to optimally solve the simpler flow shops.     

A contribution to the stochastic flow shop scheduling problem

This paper deals with performance evaluation and scheduling problems in m machine stochastic flow shop with unlimited buffers. The processing time of each job on each machine is a random variable exponentially distributed with a known rate. We consider permutation flow shop. The objective is to find a job schedule which minimizes the expected makespan. A classification of works about stochastic flow shop with random processing times is first given. In order to solve the performance evaluation problem, we propose a recursive algorithm based on a Markov chain to compute the expected makespan and a discrete event simulation model to evaluate the expected makespan. The recursive algorithm is a generalization of a method proposed in the literature for the two machine flow shop problem to the m machine flow shop problem with unlimited buffers. In deterministic context, heuristics (like CDS [Management Science 16 (10) (1970) B630] and Rapid Access [Management Science 23 (11) (1977) 1174]) and metaheuristics (like simulated annealing) provide good results. We propose to adapt and to test this kind of methods for the stochastic scheduling problem. Combinations between heuristics or metaheuristics and the performance evaluation models are proposed. One of the objectives of this paper is to compare the methods together. Our methods are tested on problems from the OR-Library and give good results: for the two machine problems, we obtain the optimal solution and for the m machine problems, the methods are mutually validated.     

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.     

Maximization of solution flexibility for robust shop scheduling

We consider the problem of introducing flexibility in the schedule determination phase, for shop scheduling problems with release dates and deadlines. The flexibility is provided by generating a family of schedules, instead of a unique one. We represent a family of schedules by an ordered group assignment defining for each machine a sequence of groups where the operations within a group are totally permutable. We propose a polynomial time algorithm to evaluate the worst case completion time of operations in an ordered group assignment. We then consider the single machine problem with heads and deadlines associated to operations, as a sub-problem of the job shop problem. We propose polynomial time dynamic programming algorithms for minimizing the number of groups and for maximizing the number of characterized sequences, under specific constraints. Finally, computational experiences on job shop benchmarks, show the impact of grouping operations on the solution makespan value.     

安装、加工和拆卸时间分离的两台机器混合作业问题

混合作业是经典的自由作业和异序作业的一种综合,其中一些工件可以按任意的机器顺序进行处理,而另一些工件必须遵守预先指定的机器顺序.本文研究安装、加工和拆卸时间分离的两台机器混合作业排序问题,该问题已经被知道是强NP困难的,本文把流水作业中的同顺序作业概念推广到混合作业,并得到这个混合作业问题在同顺序意义下的最优解,这个解对于一般情形是3/2近似解,但对于一些有意义的特殊情形是整体最优的.     

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 two-machine no-wait general and proportionate open shop makespan problem

We consider the two-machine no-wait open shop minimum makespan problem in which the determination of an optimal solution requires an optimal pairing of the jobs followed by the optimal sequencing of the job pairs. We show that the required enumeration can be curtailed by reducing the pair sequencing problem for a given pair set to a traveling salesman problem which is equivalent to a two-machine no-wait flow shop problem solvable in O(n log n) time. We then propose an optimal O(n log n) algorithm for the proportionate problem with equal machine speeds in which each job has the same processing time on both machines. We show that our O(n log n) algorithm also applies to the more general proportionate problem with equal machine speeds and machine-specific setup times. We also analyze the proportionate problem with unequal machine speeds and conclude that the required enumeration can be further curtailed (compared to the problem with arbitrary job processing times) by eliminating certain job pairs from consideration.     

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.     

最后完工机器至多两个空闲的自由作业稠密时间表(英文)

对于自由作业问题,在安排工件时避免不必要空闲所得的时间表称为稠密时间表.稠密时间表的加工总长不超过最优值的2-1/m倍,是一个在机器数m6时尚未被证明的猜想.本文通过引入工件与机器特征函数及机器关于工件非间断等概念,研究当最后完工机器至多有两个空闲区间时,性能比猜想成立的充分条件.     

Application of an optimization problem in Max-Plus algebra to scheduling problems

The problem tackled in this paper deals with products of a finite number of triangular matrices in Max-Plus algebra, and more precisely with an optimization problem related to the product order. We propose a polynomial time optimization algorithm for 2×2 matrices products. We show that the problem under consideration generalizes numerous scheduling problems, like single machine problems or two-machine flow shop problems. Then, we show that for 3×3 matrices, the problem is NP-hard and we propose a branch-and-bound algorithm, lower bounds and upper bounds to solve it. We show that an important number of results in the literature can be obtained by solving the presented problem, which is a generalization of single machine problems, two- and three-machine flow shop scheduling problems. The branch-and-bound algorithm is tested in the general case and for a particular case and some computational experiments are presented and discussed.     

Analysis of flow shop scheduling anomalies

Anomalies in flow shop scheduling are rare; only two anomalies have been reported. We present five new anomalies for the permutation flow shop models with the minimum makespan objective and seven more anomalies for the minimum total flow time objective. These anomalies (including the existing ones) are divided into three types corresponding to an increased processing time of a single operation, the addition of a job and the addition of a machine. We derive two properties which, when satisfied, eliminate the possibility of certain anomalies. We conclude that restrictions such as no-delay schedules, no job waiting or no machine idle time (after it starts processing) often result in anomalies. We also show that anomalies can also occur in non-permutation flow shops (four new anomalies presented).     

On a single-machine optimal constant due-date assignment and sequencing problem

This paper considers the problem of optimal constant due-date assignment and sequencing of jobs in a single-machine shop. We formulate the problem as a general constrained optimization problem and apply the Kuhn-Tucker conditions to find the optimal solution which is shown to be independent of the job sequence.     

具有退化工件和工期窗口安排的排序问题

针对具有退化工件的排序模型,考虑了单机排序和两台机器流水作业的工期窗口安排问题,在这一模型中,工件的加工时间是与其开工时间和退化率有关的一个线性函数。目标是找到一个最优排序和确定工期窗口的开始时间及大小以便最小化所有工件的费用函数,费用函数由四部分组成:提前、延误、工期窗口开始时间和工期窗口大小。对所研究的单机问题,详细地讨论了符合现实情况的几种类型问题,并得到了问题的最优解;对两台机器流水作业问题,给出了多项式算法。     

Two-machine shop scheduling: Compromise between flexibility and makespan value

In this paper, we consider the problem of providing flexibility to solutions of two-machine shop scheduling problems. We use the concept of group-scheduling to characterize a whole set of schedules so as to provide more choice to the decision-maker at any decision point. A group-schedule is a sequence of groups of permutable operations defined on each machine where each group is such that any permutation of the operations inside the group leads to a feasible schedule. Flexibility of a solution and its makespan are often conflicting, thus we search for a compromise between a low number of groups and a small value of makespan. We resolve the complexity status of the relevant problems for the two-machine flow shop, job shop and open shop. A number of approximation algorithms are developed and their worst-case performance is analyzed. For the flow shop, an effective heuristic algorithm is proposed and the results of computational experiments are reported.     

An Ant Colony Optimization Algorithm for Shop Scheduling Problems

We deal with the application of ant colony optimization to group shop scheduling, which is a general shop scheduling problem that includes, among others, the open shop scheduling problem and the job shop scheduling problem as special cases. The contributions of this paper are twofold. First, we propose a neighborhood structure for this problem by extending the well-known neighborhood structure derived by Nowicki and Smutnicki for the job shop scheduling problem. Then, we develop an ant colony optimization approach, which uses a strong non-delay guidance for constructing solutions and which employs black-box local search procedures to improve the constructed solutions. We compare this algorithm to an adaptation of the tabu search by Nowicki and Smutnicki to group shop scheduling. Despite its general nature, our algorithm works particularly well when applied to open shop scheduling instances, where it improves the best known solutions for 15 of the 28 tested instances. Moreover, our algorithm is the first competitive ant colony optimization approach for job shop scheduling instances.     

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.     

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     

A new neighborhood and tabu search for the Blocking Job Shop

The Blocking Job Shop is a version of the job shop scheduling problem with no intermediate buffers, where a job has to wait on a machine until being processed on the next machine. We study a generalization of this problem which takes into account transfer operations between machines and sequence-dependent setup times. After formulating the problem in a generalized disjunctive graph, we develop a neighborhood for local search. In contrast to the classical job shop, there is no easy mechanism for generating feasible neighbor solutions. We establish two structural properties of the underlying disjunctive graph, the concept of closures and a key result on short cycles, which enable us to construct feasible neighbors by exchanging critical arcs together with some other arcs. Based on this neighborhood, we devise a tabu search algorithm and report on extensive computational experience, showing that our solutions improve most of the benchmark results found in the literature.     

On some properties of optimal schedules in the job shop problem with preemption and an arbitrary regular criterion

Optimal schedules in the job shop problem with preemption and with the objective of minimizing an arbitrary regular function of operation completion times are studied. It is shown that for any instance of the problem there always exists an optimal schedule that meets several remarkable properties. Firstly, each changeover date coincides with the completion time of some operation, and so, the number of changeover dates is not greater than the total number of operations, while the total number of interruptions of the operations is no more than the number of operations minus the number of jobs. Secondly, every changeover date is “super-integral”, which means that it is equal to the total processing time of some subset of operations. And thirdly, the optimal schedule with these properties can be found by a simple greedy algorithm under properly defined priorities of operations on machines. It is also shown that for any instance of the job shop problem with preemption allowed there exists a finite set of its feasible schedules which contains at least one optimal schedule for any regular objective function (from the continuum set of regular functions).