Computational complexity and solution algorithms for flowshop scheduling problems with the learning effect

In this paper, we analyze the two-machine flowshop problem with the makespan minimization and the learning effect, which computational complexity was not determined yet. First, we show that an optimal solution of this problem does not have to be the ‘permutation’ schedule if the learning effect is taken into consideration. Furthermore, it is proved that the permutation and non-permutation versions of this problem are NP-hard even if the learning effect, in a form of a step learning curve, characterizes only one machine. However, if both machines have learning ability and the learning curves are stepwise then the permutation version of this problem is strongly NP-hard. Furthermore, we prove the makespan minimization problem in m-machine permutation proportional flowshop environment remains polynomially solvable with identical job processing times on each machine even if they are described by arbitrary functions (learning curves) dependent on a job position in a sequence. Finally, approximation algorithms for the general problem are proposed and analyzed.     

Flow shop scheduling to minimize makespan with decreasing time-dependent job processing times

In this study, we consider an n-job, m-machine flow shop scheduling problem with decreasing time-dependent job processing times. By the decreasing time-dependent job processing times, we mean that the processing time is a decreasing function of its execution starting time. When some dominant relationships between m − 1 machines can be satisfied, we show that the makespan minimization problem can be solved in polynomial time.     

Single machine total completion time minimization scheduling with a time-dependent learning effect and deteriorating jobs

In this article, we consider a single machine scheduling problem with a time-dependent learning effect and deteriorating jobs. By the effects of time-dependent learning and deterioration, we mean that the job processing time is defined by a function of its starting time and total normal processing time of jobs in front of it in the sequence. The objective is to determine an optimal schedule so as to minimize the total completion time. This problem remains open for the case of ?1?a?a denotes the learning index; we show that an optimal schedule of the problem is V-shaped with respect to job normal processing times. Three heuristic algorithms utilising the V-shaped property are proposed, and computational experiments show that the last heuristic algorithm performs effectively and efficiently in obtaining near-optimal solutions.     

Single-machine scheduling jobs with exponential learning functions

In a manufacturing system workers are involved in doing the same job or activity repeatedly. Hence, the workers start learning more about the job or activity. Because of the learning, the time to complete the job or activity starts decreasing, which is known as “learning effect”. In this paper, an exponential sum-of-actual-processing-time based learning effect is introduced into single-machine scheduling. By the exponential sum-of-actual-processing-time based learning effect, we mean that the processing time of a job is defined by an exponential function of the sum-of-the-actual-processing-time of the already processed jobs. Under the proposed learning model, we show that under a sufficient condition, the makespan minimization problem, the sum of the θth (θ > 0) power of completion times minimization problem, and some special cases of the total weighted completion time minimization problem and the maximum lateness minimization problem remain polynomially solvable.     

A two-stage flow shop scheduling problem on a batching machine and a discrete machine with blocking and shared setup times

Motivated by applications in iron and steel industry, we consider a two-stage flow shop scheduling problem where the first machine is a batching machine subject to the blocking constraint and the second machine is a discrete machine with shared setup times. We show that the problem is strongly NP-hard when the objective is to minimize the makespan. When solved with a heuristic priority rule, the worst case ratio with the minimum makespan is 2. For a more general objective, the minimization of a linear combination of the makespan and the total blocking time, a quadratic mixed integer program is presented first. Then we pinpoint two cases with polynomial time algorithms: the case without blocking constraint and the case with a given job sequence. Also for the general objective, we analyze an approximation algorithm. Finally, we evaluate the algorithms, giving experimental results on randomly generated test problems.     

Makespan minimization subject to flowtime optimality on identical parallel machines

We consider the identical parallel machine problem with makespan minimization subject to minimum total flowtime. First, we develop an optimal algorithm to the identical parallel machine problem with the objective of minimizing makespan. To improve the computational efficiency, two implementation techniques, the lower bound calculation and the job replacement rule, are applied. Based on the algorithm, an optimal algorithm, using new lower bounds, to the considered problem is developed. The result of this study can also be used to solve the bicriteria problem of minimizing the weighted sum of makespan and mean flowtime. Computational experiments are conducted up to six machines and 1000 jobs. Although the proposed algorithm has an exponential time complexity, the computational results show that it is efficient to find the optimal solution.     

A new approach to the learning effect: Beyond the learning curve restrictions

In this paper, we bring into the scheduling field a new model of the learning effect, where in two ways the existing approach is generalized. First we relax one of the rigorous constraints, and thus in our model each job can provide different experience to the processor. Second we formulate the job processing time as a non-increasing k-stepwise function, that, in general, is not restricted to a certain learning curve, thereby it can accurately fit every possible shape of a learning function. Furthermore, we prove that the problem of makespan minimization with the considered model is polynomially solvable if every job provides the same experience to the processor, and it becomes NP-hard if the experiences are diversified. The most essential result is a pseudopolynomial time algorithm that solves optimally the makespan minimization problem with any function of an experience-based learning model reduced into the form of the k-stepwise function.     

Scheduling a variable maintenance and linear deteriorating jobs on a single machine

We investigate a single machine scheduling problem in which the processing time of a job is a linear function of its starting time and a variable maintenance on the machine must be performed prior to a given deadline. The goals are to minimize the makespan and the total completion time. We prove that both problems are NP-hard. Furthermore, we show that there exists a fully polynomial time approximation scheme for the makespan minimization problem. For the total completion time minimization problem we point out that there exists a fully polynomial time approximation scheme for a special case.     

Solution algorithms for the makespan minimization problem with the general learning model

Most of the papers devoted to scheduling problems with the learning effect concern the Wright’s learning curve. On the other hand, the study about learning has pointed out that the learning curve in practice is very often an S-shaped function, which has not been considered in scheduling. Thus, in this paper, a single processor makespan minimization problem with an S-shaped learning model is investigated. We prove that this problem is strongly NP-hard even if the experience provided by each job is equal to its normal processing time. Therefore, to solve this problem, we prove some eliminating properties that are used to construct a branch and bound algorithm and some fast heuristic methods. Since the proposed algorithms are dedicated for the general case, i.e., where job processing times are arbitrary non-increasing experience dependent functions, their efficiency is verified numerically for the S-shaped model.     

Scheduling with multiple servers

In this paper, we consider the problem of scheduling a set of jobs on a set of identical parallel machines. Before the processing of a job can start, a setup is required which has to be performed by a given set of servers. We consider the complexity of such problems for the minimization of the makespan. For the problem with equal processing times and equal setup times we give a polynomial algorithm. For the problem with unit setup times, m machines and m − 1 servers, we give a pseudopolynomial algorithm. However, the problem with fixed number of machines and servers in the case of minimizing maximum lateness is proven to be unary NP-hard. In addition, recent algorithms for some parallel machine scheduling problems with constant precessing times are generalized to the corresponding server problems for the case of constant setup times. Moreover, we perform a worst case analysis of two list scheduling algorithms for makespan minimization.     

An unconstrained optimization problem is NP-hard given an oracle representation of its objective function: a technical note

The problem of unconstrained minimization of a piecewise linear function of one variable is shown to be NP-hard given an oracle representation of the function. This result can be applied to establish the NP-hardness of the scheduling problem with controllable job processing times given an oracle representation of the scheduling cost. The computational complexity of this scheduling problem has remained unknown for more than 20 years.Scope and purposeWe consider the problem of unconstrained optimization from the perspective of classifying its computational complexity, and show that it is NP-hard. This result enables us to establish the NP-hardness of the scheduling problem with controllable job processing times, whose computational complexity status has remained unknown for a long time.     

Two-Machine Stochastic Flow Shops With Blocking and the Traveling Salesman Problem

The paper deals with the problem of minimizing the expected makespan in a two-machine flow shop with blocking and random job processing times. It is well known that it reduces to an instance of the traveling salesman problem (TSP). Assuming that the job processing times can be stochastically ordered on both machines, we show that the problem under study is equivalent to TSP on a permuted Monge matrix. This allows us to prove that it is NP-hard for the independently and exponentially distributed job processing times, and identify a new class of efficiently solvable special cases.     

Scheduling with time-dependent discrepancy times

In time-dependent scheduling, various processing time functions are studied, yet absolute value functions have surprisingly been omitted from the discussion. Such a processing time function increases linearly with a job’s discrepancy from its ideal midtime. The objective is to find a schedule that minimizes the makespan, introducing the discrepancy time minimization problem. This single-machine scheduling problem with time-dependent processing times is motivated by optimization of walking times on a car assembly line. Its decision version is NP hard, as we show by reduction of the even–odd partition problem. For the variant with known start time, we develop several heuristics. Further insights form lower bounds and dominance rules for a branch-and-bound search. Numerical experiments show the performance of our algorithms on problem instances of up to 60 jobs. For the variant with common ideal midtime and flexible start time, we present a polynomial-time algorithm.     

Single-machine scheduling with deteriorating jobs

In this article, we study a single-machine scheduling problem in which the processing time of a job is a nonlinear function of its basic processing time and starting time. The objectives are to minimise the makespan, the sum of weighted completion times and the sum of the kth powers of completion times. We show that the makespan minimisation problem can be solved in polynomial time. However, the total completion time and the sum of the kth powers of completion times minimisation problems can be solved in polynomial time in some cases. Besides, some useful properties are also provided for the sum of weighted completion times problem under certain conditions.     

Permutation flowshop problems with bi-criterion makespan and total completion time objective and position-weighted learning effects

In this paper, we study the problem of minimizing the weighted sum of makespan and total completion time in a permutation flowshop where the processing times are supposed to vary according to learning effects. The processing time of a job is a function of the sum of the logarithms of the processing times of the jobs already processed and its position in the sequence. We present heuristic algorithms, which are modified from the optimal schedules for the corresponding single machine scheduling problem and analyze their worst-case error bound. We also adopt an existing algorithm as well as a branch-and-bound algorithm for the general m-machine permutation flowshop problem. For evaluation of the performance of the algorithms, computational experiments are performed on randomly generated test problems.     

瓶颈指向的启发式算法求解混合流水车间调度问题

针对以最小化时间表长为目标的复杂混合流水车间调度问题,提出了一种将机器布局和工件加工时间特征紧密结合的启发式算法.首先,充分利用各阶段平均机器负荷一般不相等的特点确定瓶颈阶段,构建初始工件排序.其次,针对在瓶颈阶段前加工时间较短而瓶颈阶段后加工时间相对较长的工件,在第1阶段优先开始加工.同时,在瓶颈阶段前的每一个阶段,每当有工件等待加工或同时完工时,优先选择瓶颈阶段前剩余加工时间最短的工件加工;在瓶颈阶段以及瓶颈阶段之后,则优先选择这台机器后剩余加工时间最长的工件加工.最后,采用工件交换和插入操作改进初始调度.用Carlier和Neron的Benchmark算例测试提出的启发式算法.将计算结果与NEH启发式算法进行了比较,平均偏差降低了0.0555%,表明这个启发式算法是有效的.     

Scheduling a batching machine with convex resource consumption functions

In various industries jobs undergo a batching, or burn in, process where different tasks are grouped into batches and processed simultaneously. The processing time of each batch is equal to the longest processing time among all jobs contained in the batch. All to date studies dealing with batching machines have considered fixed job processing times. However, in many real life applications job processing times are controllable through the allocation of a limited resource. The most common and realistic model assumes that there exists a non-linear and convex relationship between the amount of resource allocated to a job and its processing time. The scheduler?s task when dealing with controllable processing times is twofold. In addition to solving the sequencing problem, one must establish an optimal resource allocation policy. We combine these two widespread models on a single machine setting, showing that both the makespan and total completion time criteria can be solved in polynomial time. We then show that our proposed approach can be applied to general bi-criteria objective comprising of the makespan and the total completion time.     

Single-machine group scheduling with both learning effects and deteriorating jobs

In the paper two resource constrained single-machine group scheduling problems with both learning effects and deteriorating jobs are considered. By learning effects, deteriorating jobs and group technology assumption, we mean that the processing time of a job is defined by the function of its starting time and position in the group, and the group setup times of a group is a positive strictly decreasing continuous function of the amount of consumed resource. We present polynomial solutions for the makespan minimization problem under the constraint that the total resource consumption does not exceed a given limit, and the total resource consumption minimization problem under the constraint that the makespan does not exceed a given limit, respectively.     

Minimizing makespan on a three-machine flowshop batch scheduling problem with transportation using genetic algorithm

This paper studies the minimization of makespan in a three-machine flowshop scheduling problem in which a batch processing machine is located between two single processing machines on first and third stages. In this study also transportation capacity and transportation among machines times are explicitly considered.We establish a mixed integer programming model and propose a heuristic algorithm based on the basic idea of Johnson's algorithm. Since the problem under study is NP-hard, a genetic algorithm is also proposed to minimize makespan. The effectiveness of our solution procedures is evaluated through computational experiments. The results obtained from the computational study have shown that the genetic algorithm is a viable and effective approach that is capable to produce consistently good results.     

A branch and bound algorithm for minimizing makespan on a single machine with unequal release times under learning effect and deteriorating jobs

We present a single-machine problem with the unequal release times under learning effect and deteriorating jobs when the objective is minimizing the makespan. In this study, we introduced a scheduling model with unequal release times in which both job deterioration and learning exist simultaneously. By the effects of learning and deterioration, we mean that the processing time of a job is defined by increasing function of its execution start time and position in the sequence. A branch-and-bound algorithm incorporating with several dominance properties and lower bounds is developed to derive the optimal solution. A heuristic algorithm is proposed to obtain a near-optimal solution. The computational experiments show that the branch-and-bound algorithm can solve instances up to 30 jobs, and the average error percentage of the proposed heuristic is less than 0.16%.