Flowshop scheduling with a general exponential learning effect

This paper investigates flowshop scheduling problems with a general exponential learning effect, i.e., the actual processing time of a job is defined by an exponent function of the total weighted normal processing time of the already processed jobs and its position in a sequence, where the weight is a position-dependent weight. The objective is to minimize the makespan, the total (weighted) completion time, the total weighted discounted completion time, and the sum of the quadratic job completion times, respectively. Several simple heuristic algorithms are proposed in this paper by using the optimal schedules for the corresponding single machine problems. The tight worst-case bound of these heuristic algorithms is also given. Two well-known heuristics are also proposed for the flowshop scheduling with a general exponential learning effect.     

The three-stage assembly flowshop scheduling problem

We consider the three-stage assembly flowshop scheduling problem with the objective of minimizing the makespan. The three-stage assembly problem generalizes both the serial three machine flowshop problem and the two-stage assembly flowshop scheduling problem and is therefore strongly NP-hard. We analyze the worst-case ratio bound for several heuristics for this problem. We also analyze the worst-case absolute bound for a heuristic based on compact vector summation techniques and we point out that, for a large number of jobs, this heuristic becomes asymptotically optimal.Scope and purposeThe three-stage assembly flowshop scheduling problem models situations which arise frequently in manufacturing when various fabrication operations are performed concurrently and then collected and transported into an assembly area for a final assembly operation. The main criterion for this problem is the minimization of the maximum job completion time (makespan). The objective of this paper is to derive algorithms for minimizing the makespan. In doing so, we also demonstrate the reduction of assembly flowshop problems to their embedded serial flowshop problems.     

Worst-case and numerical analysis of heuristic algorithms for flowshop scheduling problems with a time-dependent learning effect

In this paper, we investigate a time-dependent learning effect in a flowshop scheduling problem. We assume that the time-dependent learning effect of a job was a function of the total normal processing time of jobs scheduled before the job. The following objective functions are explored: the makespan, the total flowtime, the sum of weighted completion times, the sum of the kth power of completion times, and the maximum lateness. Some heuristic algorithms with worst-case analysis for the objective functions are given. Moreover, a polynomial algorithm is proposed for the special case with identical processing time on each machine and that with an increasing series of dominating machines, respectively. Finally, the computational results to evaluate the performance of the heuristics are provided.     

Ordinal algorithms for parallel machine scheduling with nonsimultaneous machine available times

This paper considers ordinal algorithms for parallel machine scheduling with nonsimultaneous machine available times. Two objects of minimizing the latest job completion time and minimizing the latest machine completion time are studied. For the first objective, we present the optimal algorithms for m = 2, 3, 4 machine cases. For m ≥ 5, we propose an algorithm with competitive ratio 2 - 1/(m - 1) while the lower bound is 5/3. For the second objective, the optimal algorithm is also given. Furthermore, for a special case, an algorithm with significantly improved competitive ratio is given.     

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.     

Bi-criteria minimization for the permutation flowshop scheduling problem with machine-based learning effects

In traditional scheduling problems, the processing time for the given job is assumed to be a constant regardless of whether the job is scheduled earlier or later. However, the phenomenon named “learning effect” has extensively been studied recently, in which job processing times decline as workers gain more experience. This paper discusses a bi-criteria scheduling problem in an m-machine permutation flowshop environment with varied learning effects on different machines. The objective of this paper is to minimize the weighted sum of the total completion time and the makespan. A dominance criterion and a lower bound are proposed to accelerate the branch-and-bound algorithm for deriving the optimal solution. In addition, the near-optimal solutions are derived by adapting two well-known heuristic algorithms. The computational experiments reveal that the proposed branch-and-bound algorithm can effectively deal with problems with up to 16 jobs, and the proposed heuristic algorithms can yield accurate near-optimal solutions.     

A computer simulation model for job shop scheduling problems minimizing makespan

One of the basic and significant problems, that a shop or a factory manager is encountered, is a suitable scheduling and sequencing of jobs on machines. One type of scheduling problem is job shop scheduling. There are different machines in a shop of which a job may require some or all these machines in some specific sequence. For solving this problem, the objective may be to minimize the makespan. After optimizing the makespan, the jobs sequencing must be carried out for each machine. The above problem can be solved by a number of different methods such as branch and bound, cutting plane, heuristic methods, etc. In recent years, researches have used genetic algorithms, simulated annealing, and machine learning methods for solving such problems. In this paper, a simulation model is presented to work out job shop scheduling problems with the objective of minimizing makespan. The model has been coded by Visual SLAM which is a special simulation language. The structure of this language is based on the network modeling. After modeling the scheduling problem, the model is verified and validated. Then the computational results are presented and compared with other results reported in the literature. Finally, the model output is analyzed.     

Makespan minimization flowshop with position dependent job processing times—computational complexity and solution algorithms

This paper considers flowshop scheduling problems where job processing times are described by position dependent functions, i.e., dependent on the number of processed jobs, that model learning or aging effects. We prove that the two-machine flowshop problem to minimize the maximum completion time (makespan) is NP-hard if job processing times are described by non-decreasing position dependent functions (aging effect) on at least one machine and strongly NP-hard if job processing times are varying on both machines. Furthermore, we construct fast NEH, tabu search with a fast neighborhood search and simulated annealing algorithms that solve the problem with processing times described by arbitrary position dependent functions that model both learning and aging effects. The efficiency of the proposed methods is numerically analyzed.     

Hybrid genetic algorithms with dispatching rules for unrelated parallel machine scheduling with setup time and production availability

This article considers the unrelated parallel machine scheduling problem with sequence- and machine-dependent setup times and machine-dependent processing times. Furthermore, the machine has a production availability constraint to each job. The objective of this problem is to determine the allocation policy of jobs and the scheduling policy of machines to minimize the total completion time. To solve the problem, a mathematical model for the optimal solution is derived, and hybrid genetic algorithms with three dispatching rules are proposed for large-sized problems. To assess the performance of the algorithms, computational experiments are conducted and evaluated using several randomly generated examples.     

Single machine scheduling with interfering job sets

We consider two single machine bicriteria scheduling problems in which jobs belong to either of two different disjoint sets, each set having its own performance measure. The problem has been referred to as interfering job sets in the scheduling literature and also been called multi-agent scheduling where each agent's objective function is to be minimized. In the first problem (P1) we look at minimizing total completion time and number of tardy jobs for the two sets of jobs and present a forward SPT-EDD heuristic that attempts to generate the set of non-dominated solutions. The complexity of this specific problem is NP-hard; however some pseudo-polynomial algorithms have been suggested by earlier researchers and they have been used to compare the results from the proposed heuristic. In the second problem (P2) we look at minimizing total weighted completion time and maximum lateness. This is an established NP-hard problem for which we propose a forward WSPT-EDD heuristic that attempts to generate the set of supported points and compare our solution quality with MIP formulations. For both of these problems, we assume that all jobs are available at time zero and the jobs are not allowed to be preempted.     

Scheduling Parallel Machines for the Customer Order Problem

This paper considers scheduling problems where jobs are dispatched in batches. The objective is to minimize the sum of the completion times of the batches. While a machine can process only one job at a time, multiple machines can simultaneously process jobs in a batch. This simple environment has a variety of real world applications such as part kitting and customer order scheduling.A heuristic is presented for the parallel machine version of the problem. Also, a tight worst case bound on the relative error is found. For the case of two parallel machines, we examine two heuristics, which are based on simple scheduling rules. We find tight worst case bounds of 6/5 and 9/7 on the relative error and show that neither procedure is superior for all instances. Finally, we empirically evaluate these two heuristics. For large problems, the methods find solutions that are close to optimal.     

A new heuristic for scheduling the two-stage flowshop with additional resources

This paper deals with the problem of preemptive scheduling in a two-stage flowshop with parallel unrelated machines at the first stage and a single machine at the second stage. At the first stage, jobs use some additional resources which are available in limited quantities at any time. The resource requirements are of 0–1 type. The objective is the minimization of makespan. The problem is NP-hard. Heuristic algorithms are proposed which solve to optimality the resource constrained scheduling problem at the first stage of the flowshop, and at the same time, minimize the makespan in the flowshop by selecting appropriate jobs for simultaneous processing. Several rules of job selection are considered. The performance of the proposed heuristic algorithms is analyzed by comparing solutions with the lower bound on the optimal makespan. The extensive computational experiment shows that the proposed heuristic algorithms are able to produce near-optimal solutions in short computational time.     

A two-machine flowshop problem with two agents

The multiple-agent scheduling problems have received increasing attention recently. However, most of the research focuses on deriving feasible/optimal solutions or examining the computational complexity of the intractable cases in a single machine. Often a number of operations have to be done on every job in many manufacturing and assembly facilities (Pinedo, 2002 [1]). In this paper, we consider a two-machine flowshop problem where the objective is to minimize the total completion time of the first agent with no tardy jobs for the second agent. We develop a branch-and-bound algorithm and simulated annealing heuristic algorithms to search for the optimal solution and near-optimal solutions for the problem, respectively.     

带运输考虑的多阶段动态可重入混合流水车间调度

可重入混合流水车间调度允许一个工件多次进入某些加工阶段,它广泛出现在许多工业制造过程中,如半导体制造、印刷电路板制造等.本文研究了带运输时间的多阶段动态可重入混合流水车间问题,目标是最小化总加权完成时间.针对该问题,建立了整数规划模型,进而基于工件解耦方式提出了两种改进的拉格朗日松弛(LR)算法.在这些算法中,设计了动态规划的改进策略以加速工件级子问题的求解,提出了异步次梯度法以得到有效的乘子更新方向.测试结果说明了所提出的两种改进算法在解的质量和运行时间方面均优于常规LR算法,两种算法都能在可接受的计算时间内得到较好的近优解.     

A two-stage hybrid flowshop scheduling problem with a function constraint and unrelated alternative machines

This article addresses a two-stage hybrid flowshop scheduling problem with unrelated alternative machines. The problem to be studied has m unrelated alternative machines at the first machine center followed by a second machine center with a common processing machine in the system. The objective is to minimize the makespan of the system. For the processing of any job, it is assumed that the operation can be partially substituted by other machines in the first center, depending on its machining constraints. Such scheduling problems occur in certain practical applications such as semiconductors, electronics manufacturing, airplane engine production, and petrochemical production. We demonstrate that the addressed problem is NP-hard and then provide some heuristic algorithms to solve the problem efficiently. The experimental results show that the combination of the modified Johnson's rule and the First-Fit rule provides the best solutions within all proposed heuristics.Scope and purpose     

A two-machine flowshop scheduling problem with a separated maintenance constraint

This paper considers a two-machine flowshop scheduling problem with a separated maintenance constraint. This means that the machine may not always be available during the scheduling period. It needs a constant time to maintain the machine after completing a fixed number of jobs at most. The objective is to find the optimal job combinations and the optimal job schedule such that the makespan is minimized. The proposed problem has some practical applications, for example, in electroplating process, the electrolytic cell needs to be cleaned and made up a deficiency of medicine. In this paper, we propose a heuristic algorithm to solve this problem. Some polynomially solvable cases and computational experiments are also provided.     

A hybrid flowshop scheduling model considering dedicated machines and lot-splitting for the solar cell industry

This paper studies a solar cell industry scheduling problem, which is similar to traditional hybrid flowshop scheduling (HFS). In a typical HFS problem, the allocation of machine resources for each order should be scheduled in advance. However, the challenge in solar cell manufacturing is the number of machines that can be adjusted dynamically to complete the job. An optimal production scheduling model is developed to explore these issues, considering the practical characteristics, such as hybrid flowshop, parallel machine system, dedicated machines, sequence independent job setup times and sequence dependent job setup times. The objective of this model is to minimise the makespan and to decide the processing sequence of the orders/lots in each stage, lot-splitting decisions for the orders and the number of machines used to satisfy the demands in each stage. From the experimental results, lot-splitting has significant effect on shortening the makespan, and the improvement effect is influenced by the processing time and the setup time of orders. Therefore, the threshold point to improve the makespan can be identified. In addition, the model also indicates that more lot-splitting approaches, that is, the flexibility of allocating orders/lots to machines is larger, will result in a better scheduling performance.     

Dispatching rule selection using artificial neural networks for dynamic planning and scheduling

To schedule a job shop, the first task is to select an appropriate scheduling algorithm or rule. Because of the complexity of scheduling problems, no general algorithm sufficient for solving all scheduling problems has yet been developed. Most job-shop scheduling systems offer alternative algorithms for different situations, and experienced human schedulers are needed to select the best dispatching rule in these systems. This paper proposes a new algorithm for job-shop scheduling problems. This algorithm consists of three stages. First, computer simulation techniques are used to evaluate the efficiency of heuristic rules in different scheduling situations. Second, the simulation results are used to train a neural network in order to capture the knowledge which can be used to select the most efficient heuristic rule for each scheduling situation. Finally, the trained neural network is used as a dispatching rule selector in the real-time scheduling process. Research results have shown great potential in using a neural network to replace human schedulers in selecting an appropriate approach for real-time scheduling. This research is part of an ongoing project of developing a real-time planning and scheduling system.     

A two-machine flowshop makespan scheduling problem with deteriorating jobs

In traditional scheduling problems, the job processing times are assumed to be known and fixed from the first job to be processed to the last job to be completed. However, in many realistic situations, a job will consume more time than it would have consumed if it had begun earlier. This phenomenon is known as deteriorating jobs. In the science literature, the deteriorating job scheduling problems are relatively unexplored in the flowshop settings. In this paper, we study a two-machine flowshop makespan scheduling problem in which job processing times vary as time passes, i.e. they are assumed as increasing functions of their starting times. First, an exact algorithm is established to solve most of the problems of up to 32 jobs in a reasonable amount of time. Then, three heuristic algorithms are provided to derive the near-optimal solutions. A simulation study is conducted to evaluate the performances of the proposed algorithms. In addition, the impact of the deterioration rate is also investigated.     

Algorithms for a two‐machine flowshop problem with jobs of two classes

We consider a problem of scheduling jobs of two classes of urgencies in a two‐machine flowshop with the objective of minimizing total tardiness of one class for urgent jobs and the maximum completion time of the other class for non‐urgent jobs. Urgent jobs are an important consideration in the real manufacturing systems, but it has not been studied due to the difficulty of the problem. In this research, a branch‐and‐bound (B&B) algorithm is proposed through developing lower bounds, dominance properties, and heuristic algorithms for obtaining an initial feasible solution. To evaluate the performance of the proposed algorithms, computational experiments on randomly generated instances are performed. Results of the experiments show that the suggested B&B algorithm can solve problems with up to 20 jobs in a reasonable amount of CPU time.