Two-agent group scheduling with deteriorating jobs on a single machine

This paper considers the two-agent scheduling problems with deteriorating jobs and group technology on a single machine, where the objective is to minimize the total completion time of the first agent with the restriction that the maximum cost of the second agent cannot exceed a given upper bound. Two agents compete to perform their respective jobs on a common single machine, and each agent has his own criterion to optimize. We introduce deteriorating jobs and group technology into the two-agent single-machine scheduling where the job processing times and group setup times are both functions of their starting times. There are two different linear deterioration functions. We propose the optimal properties and present the optimal polynomial time algorithms for two different scheduling problems, respectively.     

Two-machine flowshop scheduling to minimize mean flow time under simple linear deterioration

A real industrial production phenomenon, referred to as deteriorating jobs, has drawn increasing attention. However, most research on this issue considers only single-machine problems. Motivated by this limitation, this paper considers a simple linear deterioration model in a two-machine flowshop where the objective is to minimize the mean flow time. Several dominance rules and three lower bounds are proposed to speed up the search for an optimal solution, and several heuristic algorithms are provided to derive near-optimal solutions. In addition, a computational experiment is conducted to evaluate their performances. Results indicate that the algorithms perform well, and a combined heuristic algorithm is recommended for practitioners.     

Minimizing the earliness/tardiness costs on parallel machine with learning effects and deteriorating jobs: a mixed nonlinear integer programming approach

In this study, we introduce a mixed nonlinear integer programming formulation for parallel machine earliness/tardiness (ET) scheduling with simultaneous effects of learning and linear deterioration, sequence-dependent setups, and a common due-date for all jobs. By the effects of learning and linear deterioration, we propose that the processing time of a job is defined by increasing function of its execution start time and position in the sequence. The developed model allows sequence-dependent setups and sequence-dependent early/tardy penalties. The model can easily provide the optimal solution to problems involving about eleven jobs and two machines.     

Bottleneck identification procedures for the job shop scheduling problem with applications to genetic algorithms

Two bottleneck identification algorithms (one for bottleneck machines and the other for bottleneck jobs) are presented for the job shop scheduling problem in which the total weighted tardiness must be minimized. The scheduling policies on bottleneck machines can have significant impact on the final scheduling performance, and therefore, they need to be optimized with more computational effort. Meanwhile, bottleneck jobs that can cause considerable deterioration to the solution quality also need to be considered with higher priority. In order to describe the characteristic information concerning such bottleneck machines and bottleneck jobs, a statistical approach is devised to obtain the bottleneck characteristic values for each machine, and, in addition, a fuzzy inference system is employed to transform human knowledge into the bottleneck characteristic values for each job. These bottleneck characteristic values reflect the features of both the objective function and the current optimization stage. Finally, the effectiveness of the two procedures is verified by specifically designed genetic algorithms.     

Minimizing the total weighted completion time on a single machine under linear deterioration

This paper investigates a single-machine problem in which processing times of jobs are start time dependent and the aim is to minimize the total weighted completion time. Recent research has shown the complexity of this problem to be NP-hard; however, no optimal or heuristic algorithms have been proposed. In this paper, we explore the exact solution and propose several heuristic algorithms derived based on the impacts of model parameters. The effects of normal processing times and deterioration rates are also studied.     

Single machine group scheduling with general linear deterioration to minimize the makespan

In this paper, we consider a single machine scheduling problem with deteriorating jobs and group technology assumption. By deteriorating jobs and group technology assumption, we mean that the group setup times and job processing times are both increasing functions of their starting times, i.e., group setup times and job processing times are both described by function, which is a general linear function of time. The objective of the scheduling problem is to minimize the makespan. We show that the problem remains solvable in polynomial time when general linear deterioration and group technology are considered simultaneously.     

A generalization for single-machine scheduling with deteriorating jobs to minimize earliness penalties

We consider a single-machine scheduling problem with deteriorating jobs in which the due dates are determined by the equal slack (SLK) method. By a deteriorating job, we mean that the job’s processing time is an increasing function of its starting time. We model job deterioration as a function that is proportional to a linear function of time. The objective is to minimize the total weighted earliness penalty subject to no tardy jobs. We prove that two special cases of the problem remain polynomially solvable. The first case is the problem with equally weighted monotonous penalty objective function and the other case is the problem with weighted linear penalty objective function.     

Flow shop scheduling with deteriorating jobs under dominating machines to minimize makespan

In this paper, we consider an n-job, m-machine flow shop scheduling problem with deteriorating jobs. By deteriorating jobs, we mean jobs whose processing times are an increasing function of their execution starting time. A simple linear deterioration function is assumed. 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 group scheduling problems with deteriorating jobs

This paper investigates single-machine scheduling problems with deteriorating jobs and the group technology (GT) assumption. By deteriorating jobs and the group technology assumption, we mean that the group setup times and job processing times are both increasing functions of their starting times, i.e., the group setup times and job processing times are both described by a function which is proportional to a linear function of time. The two objectives of scheduling problems are to minimize the makespan and the total weighted completion time, respectively. We show that these problems remain solvable in polynomial time when deterioration and group technology are considered simultaneously.     

Solution algorithms for the total weighted completion time minimization flow shop scheduling with decreasing linear deterioration

In this paper, we consider a two-machine flow shop scheduling problem with decreasing linear deterioration. By decreasing linear deterioration, we mean that the processing time is a decreasing function of its execution start time. The objective is to find a sequence that minimizes the total weighted completion time. Several dominance properties and some lower bounds are derived to speed up the elimination process of a branch-and-bound algorithm. Two heuristic algorithms are also proposed to overcome the inefficiency of the branch-and-bound algorithm. Computational results for randomly generated problem instances are presented.     

A genetic algorithm for solving no-wait flexible flow lines with due window and job rejection

This paper addresses a no-wait multi-stage flexible flow shop problem. There are n jobs to complete in a predetermined due window; hence, some jobs may be rejected. A mixed integer linear programming model with the objective of maximizing the total profit gained from scheduled jobs is introduced. Since the problem is NP-hard and difficult to find an optimal solution in a reasonable computational time, an efficient genetic algorithm is presented as the solution procedure. A heuristic mechanism is proposed to use in each generation of the genetic algorithms to assure the feasibility and superior quality of the obtained solutions. Computational results show that the presented approach performs considerably in terms of both quality of solutions and required runtimes.     

Minimizing total weighted tardiness on a batch-processing machine with non-agreeable release times and due dates

This study considers the scheduling problem observed in the burn-in operation of semiconductor final testing, where jobs are associated with release times, due dates, processing times, sizes, and non-agreeable release times and due dates. The burn-in oven is modeled as a batch-processing machine which can process a batch of several jobs as long as the total sizes of the jobs do not exceed the machine capacity and the processing time of a batch is equal to the longest time among all the jobs in the batch. Due to the importance of on-time delivery in semiconductor manufacturing, the objective measure of this problem is to minimize total weighted tardiness. We have formulated the scheduling problem into an integer linear programming model and empirically show its computational intractability. Due to the computational intractability, we propose a few simple greedy heuristic algorithms and meta-heuristic algorithm, simulated annealing (SA). A series of computational experiments are conducted to evaluate the performance of the proposed heuristic algorithms in comparison with exact solution on various small-size problem instances and in comparison with estimated optimal solution on various real-life large size problem instances. The computational results show that the SA algorithm, with initial solution obtained using our own proposed greedy heuristic algorithm, consistently finds a robust solution in a reasonable amount of computation time.     

Note on “A unique integer mathematical model for scheduling deteriorating jobs with rate-modifying activities on a single machine”

In this note, we study scheduling problems with simultaneous considerations of deteriorating jobs and rate-modifying activities on a single machine. The job-dependent deterioration effect and the job-independent deterioration effect models are examined with the objective of minimizing the makespan. We propose polynomial time solutions for all the studied problems.     

Algorithms for flexible flow shop problems with unrelated parallel machines, setup times, and dual criteria

In textile industries, production facilities are established as multi-stage production flow shop facilities, where a production stage may be made up of parallel machines. This known as a flexible or hybrid flow shop environment. This paper considers the problem of scheduling n independent jobs in such an environment. In addition, we also consider the general case in which parallel machines at each stage may be unrelated. Each job is processed in ordered operations on a machine at each stage. Its release date and due date are given. The preemption of jobs is not permitted. We consider both sequence- and machine-dependent setup times. The problem is to determine a schedule that minimizes a convex combination of makespan and the number of tardy jobs. A 0–1 mixed integer program of the problem is formulated. Since this problem is NP-hard in the strong sense, we develop heuristic algorithms to solve it approximately. Firstly, several basic dispatching rules and well-known constructive heuristics for flow shop makespan scheduling problems are generalized to the problem under consideration. We sketch how, from a job sequence, a complete schedule for the flexible flow shop problem with unrelated parallel machines can be constructed. To improve the solutions, polynomial heuristic improvement methods based on shift moves of jobs are applied. Then, genetic algorithms are suggested. We discuss the components of these algorithms and test their parameters. The performance of the heuristics is compared relative to each other on a set of test problems with up to 50 jobs and 20 stages.     

Single-machine scheduling with a sum-of-processing-time based learning effect and deteriorating jobs

The paper deals with the single-machine scheduling problem with a sum-of-processing-time- based learning effect and deteriorating jobs. By the effects of sum-of-processing-time-based learning and deterioration, we mean that the processing time of a job is defined by function of its starting time and total normal processing time of jobs in front of it in the sequence. It is shown that, even with the introduction of the effects of sum-of-processing-time-based learning and deterioration to job processing times, the single-machine makespan minimization problem remains polynomially solvable.     

Permutation flowshops with transportation times: mathematical models and solution methods

This paper deals with permutation flowshops with considering transportation times of carrying semi-finished jobs from a machine to another one. The transportation between machines can be done using two types of transportation systems: multi-transporter and single-transporter systems. We formulate the problem with both systems as six different mixed integer linear programs. We also provide solution methods including heuristics and metaheuristics in order to solve large-sized problems. The heuristics are the adaptations of well-known heuristics and the proposed metaheuristics are based on artificial immune systems incorporating an effective local search heuristic and simulated annealing. A comprehensive experiment is conducted to compare and evaluate the performance of the models as well as the algorithms. All the results show the effectiveness of the proposed models and algorithms.     

Development and analysis of constructive heuristic algorithms for flow shop scheduling problems with sequence-dependent setup times

This paper focuses on the problem of determining a permutation schedule for n jobs in an m-machine flow shop that operates in a sequence-dependent setup time (SDST) environment. Two constructive heuristic algorithms are developed with the minimisation of makespan as the objective. The first heuristic algorithm termed as setup ranking algorithm obtains the sequence using the setup times of jobs only. The second heuristic algorithm, fictitious job setup ranking algorithm (FJSRA), is developed using the concept of fictitious jobs. Pairs of jobs with minimum setup time between them constitute the fictitious jobs. Both these algorithms are compared with an existing constructive algorithm. For the purpose of experimentation, Taillard benchmark problems are used to develop SDST benchmark problems at eight different levels of sequence-dependent setup times. Graphical analysis, relative performance index analysis and statistical analysis are carried out on the results obtained for all the eight sets of benchmark problems. The analysis reveals that FJSRA emerges as the better algorithm for larger problems and for smaller problems with higher level of setup time. The results of statistical analysis are used to develop setup time dominance matrix for deciding upon the algorithm to be used for a particular size of problem.     

Iterated hybrid metaheuristic algorithms for unrelated parallel machines problem with unequal ready times and sequence-dependent setup times

The problem considered in this paper involves a set of independent jobs on unrelated parallel machines with sequence-dependent setup times and unequal ready times, and the objective is to minimize the weighted number of tardy jobs. Iterated hybrid metaheuristic algorithms are proposed to address this problem. The algorithms begin with effective initial solution generators to generate initial feasible solutions; then, hybrid metaheuristics are applied to improve the initial solutions, integrating the principles of the variable neighborhood descent approach and tabu search. If the search becomes trapped at a local optimum, a perturbation operator is developed to help the search escape. To evaluate the performance of the suggested algorithms, heuristic rules and iterated local search algorithms are examined and compared. Computational experimental results show that the proposed algorithms outperform the other heuristics.     

Scheduling jobs on parallel machines: a restricted tabu search approach

Many real scheduling problems are often much more complex than problems that are analytically tractable. The main difficulty in obtaining optimal job schedules arises from the existence of sequence dependent setup times among jobs and job release times. In this paper, we present a restricted tabu search algorithm that schedules jobs on parallel machines in order to minimise the maximum lateness of the jobs. The jobs have release times and due dates, and sequence-dependent setup times exist between the jobs. The parallel machines are either identical or non-identical in terms of the processing times of the jobs. The restricted tabu search algorithm employs a restricted search with the elimination of non-effective job moves, for finding the best neighbourhood schedule. The restricted search algorithm reduces search effort significantly while obtaining good quality final schedule. The experimental results show that the proposed algorithm obtains much better solutions more quickly than other heuristic algorithms such as the Rolling Horizon Procedure (RHP) heuristic, the basic tabu search and simulated annealing.     

Single-machine scheduling with controllable processing times and learning effect

In this paper, we consider single-machine scheduling problem with controllable processing times and learning effect, i.e., processing times of jobs are controllable variables with linear costs and also are defined as functions of positions in a schedule. We concentrate on two goals separately, namely minimizing a cost function containing makespan, total completion time, total absolute differences in completion times, and total compression cost and minimizing a cost function containing makespan, total waiting time, total absolute differences in waiting times, and total compression cost. The problem is modeled as an assignment problem and thus can be solved with the well-known algorithms.