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%.     

Simulated-annealing heuristics for the single-machine scheduling problem with learning and unequal job release times

In scheduling of batch processing machines in the diffusion and oxidation areas of a wafer fabrication facility, it can be found that the processing times of these batching operations can be extremely long (10 h) when compared to other operations (1-2 h) in a wafer fab. Moreover, the jobs to be processed may have different priorities/weights, due dates and ready times. In the presence of unequal ready times, it would be better to wait for future job arrivals in order to increase the fullness of the batch. On the other hand, repeated processing of similar tasks improves workers’ skills. Motivated by these observations, we consider a single-machine problem with the sum of processing times based learning effect and release times. The objective is to find a schedule to minimize the total completion times. We first develop a branch-and-bound algorithm for the optimal solution. Then we propose a simulated-annealing heuristic algorithm for a near-optimal solution. Finally, we conduct a computational experiment to evaluate the performances of the proposed algorithms. The results show that the branch-and-bound algorithm can solve instances up to 24 jobs, and the average error percentage of the simulated-annealing algorithm is less than 0.1482%.     

Tabu search heuristic for two-machine flowshop with batch processing machines

Batch processing machines are frequently encountered in many industrial environments. A batch processing machine is one which can process several jobs simultaneously as a batch. The processing time of a batch is equal to the largest processing time of any job in the batch. This study deals with the problem of scheduling jobs in a flowshop with two batch processing machines such that the makespan is minimized. A heuristic based on Tabu search (TS) technique is proposed. The proposed heuristic is compared with a heuristic based on mixed integer linear programming (MILP). Because the complexity of the MILP-based heuristic is depended on the number of job batches, the comparison is under up-to-eight batches problem. In order to measure the proposed TS-based heuristic in larger batch problem, the relative error percentage with the lower bound (REP_LB) is used. The results show that the proposed heuristic is efficient and effective for the problems with relative large job sizes.     

Scheduling of parallel machines with sequence-dependent batches and product incompatibilities in an automotive glass facility

This application is motivated by a complex real-world scheduling problem found in the bottleneck workstation of the production line of an automotive safety glass manufacturing facility. The scheduling problem consists of scheduling jobs (glass parts) on a number of parallel batch processing machines (furnaces), assigning each job to a batch, and sequencing the batches on each machine. The two main objectives are to maximize the utilization of the parallel machines and to minimize the delay in the completion date of each job in relation to a required due date (specific for each job). Aside from the main objectives, the output batches should also produce a balanced workload on the parallel machines, balanced job due dates within each batch, and minimal capacity loss in the batches. The scheduling problem also considers a batch capacity constraint, sequence-dependent processing times, incompatible product families, additional resources, and machine capability. We propose a two-phase heuristic approach that combines exact methods with search heuristics. The first phase comprises a four-stage mixed-integer linear program for building the batches; the second phase is based on a Greedy Randomized Adaptive Search Procedure for sequencing the batches assigned to each machine. We conducted experiments on instances with up to 100 jobs built with real data from the manufacturing facility. The results are encouraging both in terms of computing time—5 min in average—and quality of the solutions—less than 10 % relative gap from the optimal solution in the first phase and less than 5 % in the second phase. Additional experiments were conducted on randomly generated instances of small, medium, and large size.     

The unbounded single machine parallel batch scheduling problem with family jobs and release dates to minimize makespan

In this paper we consider the unbounded single machine parallel batch scheduling problem with family jobs and release dates to minimize makespan. We show that this problem is strongly NP-hard, and give an O(n(n/m+1)^m) time dynamic programming algorithm and an O(mk^k+1P^2k−1) time dynamic programming algorithm, where n is the number of jobs, m is the number of families, k is the number of distinct release dates and P is the sum of the processing times of all families. We further give a heuristic with a performance ratio 2. We also give a polynomial-time approximation scheme for the problem.     

Two-machine flowshop scheduling problem with bounded processing times to minimize total completion time

We consider the two-machine flowshop scheduling problem where jobs have random processing times which are bounded within certain intervals. The objective is to minimize total completion time of all jobs. The decision of finding a solution for the problem has to be made based on the lower and upper bounds on job processing times since this is the only information available. The problem is NP-hard since the special case when the lower and upper bounds are equal, i.e., the deterministic case, is known to be NP-hard. Therefore, a reasonable approach is to come up with well performing heuristics. We propose eleven heuristics which utilize the lower and upper bounds on job processing times based on the Shortest Processing Time (SPT) rule. The proposed heuristics are compared through randomly generated data. The computational analysis has shown that the heuristics using the information on the bounds of job processing times on both machines perform much better than those using the information on one of the two machines. It has also shown that one of the proposed heuristics performs as the best for different distributions with an overall average percentage error of less than one.     

Common due date assignment and scheduling with ready times

We consider the problem of scheduling a set of nonsimultaneously available jobs on one machine. Each job has a ready time only at or after which the job can be processed. All the jobs have a common due date, which needs to be determined. The problem is to determine a due date and a schedule so as to minimize a total penalty depending on the earliness, tardiness and due date. We show that this problem is strongly NP-hard and give an efficient algorithm that finds an optimal due date and schedule when either the job sequence is predetermined or all jobs have the same processing time. We also propose three approximation algorithms for the general and special cases together with their experimental analysis.

Scope and purpose

We consider the single machine due date assignment problem for scheduling jobs which are ready for processing at different times. The problem under consideration arises in production planning and scheduling concerning the setting of appropriate due dates for a number of customer orders arriving over time. Most of the earlier publications on this subject assumed that the jobs are ready for processing simultaneously. This assumption is too restrictive for real-life production systems where jobs arrive at different times. We show that the problem with unequal ready times is NP-hard and develop fast heuristic algorithms for it, and exact algorithms for two special cases.     

Minimizing the makespan on a batch machine with non-identical job sizes: an exact procedure

A batch processing machine can simultaneously process several jobs forming a batch. This paper considers the problem of scheduling jobs with non-identical capacity requirements, on a single-batch processing machine of a given capacity, to minimize the makespan. The processing time of a batch is equal to the largest processing time of any job in the batch. We present some dominance properties for a general enumeration scheme and for the makespan criterion, and provide a branch and bound method. For large-scale problems, we use this enumeration scheme as a heuristic method.Scope and purposeUsually in classical scheduling problems, a machine can perform only one job at a time. Although, one can find machines that can process several jobs simultaneously as a batch. All jobs of a same batch have common starting and ending times. Batch processing machines are encountered in many different environments, such as burn-in operations in semiconductor industries or heat treatment operations in metalworking industries. In the first case, the capacity of the machine is defined by the number of jobs it can hold. In the second case, each job has a certain capacity requirement and the total size of a batch cannot exceed the capacity of the machine. Hence, the number of jobs contained in each batch may be different. In this paper, we consider this second case (which is more difficult) and we provide an exact method for the makespan criterion (minimizing the last ending time).     

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.     

A hybrid genetic heuristic for scheduling parallel batch processing machines with arbitrary job sizes

This paper investigates the scheduling problem of parallel identical batch processing machines in which each machine can process a group of jobs simultaneously as a batch. Each job is characterized by its size and processing time. The processing time of a batch is given by the longest processing time among all jobs in the batch. Based on developing heuristic approaches, we proposed a hybrid genetic heuristic (HGH) to minimize makespan objective. To verify the performance of our algorithm, comparisons are made through using a simulated annealing (SA) approach addressed in the literature as a comparator algorithm. Computational experiments reveal that affording the knowledge of problem through using heuristic procedures, gives HGH the ability of finding optimal or near optimal solutions in a reasonable time.     

Parallel machine match-up scheduling with manufacturing cost considerations

Many scheduling problems in practice involve rescheduling of disrupted schedules. In this study, we show that in contrast to fixed processing times, if we have the flexibility to control the processing times of the jobs, we can generate alternative reactive schedules considering the manufacturing cost implications in response to disruptions. We consider a non-identical parallel machining environment where processing times of the jobs are compressible at a certain manufacturing cost, which is a convex function of the compression on the processing time. In rescheduling it is highly desirable to catch up the original schedule as soon as possible by reassigning the jobs to the machines and compressing their processing times. On the other hand, one must also keep the manufacturing cost due to compression of the jobs low. Thus, one is faced with a tradeoff between match-up time and manufacturing cost criteria. We introduce alternative match-up scheduling problems for finding schedules on the efficient frontier of this time/cost tradeoff. We employ the recent advances in conic mixed-integer programming to model these problems effectively. We further provide a fast heuristic algorithm driven by dual prices of convex subproblems for generating approximate efficient schedules.     

A generalized two-machine flowshop scheduling problem with processing time linearly dependent on job waiting-time

We consider a two-machine flowshop scheduling problem where the processing times are linearly dependent on the waiting times of the jobs. The objective is to minimize the makespan. A 0–1 mixed integer program and a heuristic algorithm are proposed. Some cases solved in polynomial time and computational experiments are also provided.     

Single facility scheduling with nonlinear processing times

This paper considers the static single facility scheduling problem where the processing times of jobs are a monotonically increasing function of their starting (waiting) times and the objective is to minimize the total elapsed time (called the makespan) in which all jobs complete their processing. Based on the combinatorial analysis of the problem, an exact optimization algorithm is developed for the general processing time function which is then specialized for the linear case. In view of the excessive computational burden of the exact optimization algorithm for the nonlinear processing time functions, heuristic algorithms are proposed. The effectiveness of these proposed alogrithms is empirically evaluated and found to indicate that these heuristic algorithms yield optimal or near optimal schedules in many cases.     

Unrelated parallel machine scheduling with setup times and a total weighted tardiness objective

This paper presents several search heuristics and their performance in batch scheduling of parallel, unrelated machines. Identical or similar jobs are typically processed in batches in order to decrease setup times and/or processing times. The problem accounts for allotting batched work parts into unrelated parallel machines, where each batch consists of a fixed number of jobs. Some batches may contain different jobs but all jobs within each batch should have an identical processing time and a common due date. Processing time of each job of a batch is determined according to the machine group as well as the batch group to which the job belongs. Major or minor setup times are required between two subsequent batches depending on batch sequence but are independent of machines. The objective of our study is to minimize the total weighted tardiness for the unrelated parallel machine scheduling. Four search heuristics are proposed to address the problem, namely (1) the earliest weighted due date, (2) the shortest weighted processing time, (3) the two-level batch scheduling heuristic, and (4) the simulated annealing method. These proposed local search heuristics are tested through computational experiments with data from dicing operations of a compound semiconductor manufacturing facility.     

An artificial immune system heuristic for two-stage multi-machine assembly scheduling problem to minimize total completion time

We address the two-stage multi-machine assembly scheduling problem. The first stage consists of m independently working machines where each machine produces its own component. The second stage consists of two independent and identical assembly machines. The objective is to come up with a schedule that minimizes total or mean completion time for all jobs. The problem has been addressed in the scheduling literature and several heuristics have been proposed. In this paper, we propose a new heuristic called artificial immune system (AIS). We conduct experimental analysis for comparing the newly proposed heuristic AIS with the best known heuristic in the literature. Experimental results show that our proposed heuristic AIS performs better than the best known existing heuristic. More specifically, our new heuristic AIS reduces the error of the best known heuristic by 60% while the computational times of both AIS and the best known heuristic are almost the same.     

Minimizing makespan subject to minimum flowtime on two identical parallel machines

We consider the problem of scheduling jobs on two parallel identical machines where an optimal schedule is defined as one that gives the smallest makespan (the completion time of the last job) among the set of schedules with optimal total flowtime (the sum of the completion times of all jobs). We propose an algorithm to determine optimal schedules for the problem, and describe a modified multifit algorithm to find an approximate solution to the problem in polynomial computational time. Results of a computational study to compare the performance of the proposed algorithms with a known heuristic shows that the proposed heuristic and optimization algorithms are quite effective and efficient in solving the problem.Scope and purposeMultiple objective optimization problems are quite common in practice. However, while solving scheduling problems, optimization algorithms often consider only a single objective function. Consideration of multiple objectives makes even the simplest multi-machine scheduling problems NP-hard. Therefore, enumerative optimization techniques and heuristic solution procedures are required to solve multi-objective scheduling problems. This paper illustrates the development of an optimization algorithm and polynomially bounded heuristic solution procedures for the scheduling jobs on two identical parallel machines to hierarchically minimize the makespan subject to the optimality of the total flowtime.     

Genetic algorithm for minimizing the total weighted completion time scheduling problem with learning and release times

This paper considers a single-machine problem with the sum-of-processing time based learning effect and release times. The objective is to minimize the total weighted completion times. First, a branch-and-bound algorithm incorporating with several dominance properties and two lower bounds are developed for the optimal solution. Then a genetic heuristic-based algorithm is proposed for a near-optimal solution. Finally, a computational experiment is conducted to evaluate the performances of the proposed algorithms. The results show that the branch-and-bound algorithm can solve instances up to 15 jobs, and the average error percentage of the genetic heuristic algorithm is less than 0.105%.     

Minimizing the number of tardy jobs in a single-machine scheduling problem with periodic maintenance

This research focuses on the problem of scheduling jobs on a single machine that requires periodic maintenance with the objective of minimizing the number of tardy jobs. We present a two-phase heuristic algorithm in which an initial solution is obtained first with a method modified from Moore's algorithm for the problem without maintenance and then the solution is improved in the second phase. Performance of the proposed heuristic algorithm is evaluated through computational experiments on randomly generated problem instances and results show that the heuristic gives solutions close to those obtained from a commercial integer programming solver in much shorter time and works better than an existing heuristic algorithm in terms of the solution quality.     

Scheduling independent jobs on uniform parallel machines to minimize tardiness criteria

The problem of scheduling N jobs on M uniform parallel machines is studied. The objective is to minimize the mean tardiness or the weighted sum of tardiness with weights based on jobs, on periods or both. For the mean tardiness criteria in the preemptive case, this problem is NP-hard but good solutions can be calculated with a transportation problem algorithm. In the nonpreemptive case the problem is therefore NP-hard, except for the cases with equal job processing times or with job due dates equal to job processing times. No dominant heuristic is known in the general nonpreemptive case. The author has developed a heuristic to solve the nonpreemptive scheduling problem with unrelated job processing times. Initially, the algorithm calculates a basic solution. Next, it considers the interchanges of job subsets to equal processing time sum interchanging resources (i.e. a machine for a given period). This paper models the scheduling problem. It presents the heuristic and its result quality, solving 576 problems for 18 problem sizes. An application of school timetable scheduling illustrates the use of this heuristic.     

Single machine batch scheduling problem with family setup times and release dates to minimize makespan

In this paper we consider the single machine batch scheduling problem with family setup times and release dates to minimize makespan. We show that this problem is strongly NP-hard, and give an time dynamic programming algorithm and an time dynamic programming algorithm for the problem, where n is the number of jobs, m is the number of families, k is the number of distinct release dates and P is the sum of the setup times of all the families and the processing times of all the jobs. We further give a heuristic with a performance ratio 2. We also give a polynomial-time approximation scheme (PTAS) for the problem.