Single machine scheduling with past-sequence-dependent setup times and deteriorating jobs

This paper considers single machine scheduling problems with setup times and deteriorating jobs. The setup times are proportional to the length of the already processed jobs, that is, the setup times are past-sequence-dependent (p-s-d). It is assumed that the job processing times are defined by functions dependent on their starting times. The following objectives are considered: the makespan, the total completion time, and the sum of earliness, tardiness, and due-window starting time and size penalties. We propose polynomial time algorithms to solve these problems.     

One-machine scheduling problems with deteriorating jobs and position-dependent learning effects under group technology considerations

In this paper, we introduce a group scheduling model with general deteriorating jobs and learning effects in which deteriorating jobs and learning effects are both considered simultaneously. This means that the actual processing time of a job depends not only on the processing time of the jobs already processed, but also on its scheduled position. In our model, the group setup times are general linear functions of their starting times and the jobs in the same group have general position-dependent learning effects and time-dependent deterioration. The objective of scheduling problems is to minimise the makespan and the sum of completion times, respectively. We show that the problems remain solvable in polynomial time under the proposed model.     

A robust hybrid approach based on particle swarm optimization and genetic algorithm to minimize the total machine load on unrelated parallel machines

This paper dealt with an unrelated parallel machines scheduling problem with past-sequence-dependent setup times, release dates, deteriorating jobs and learning effects, in which the actual processing time of a job on each machine is given as a function of its starting time, release time and position on the corresponding machine. In addition, the setup time of a job on each machine is proportional to the actual processing times of the already processed jobs on the corresponding machine, i.e., the setup times are past-sequence-dependent (p-s-d). The objective is to determine jointly the jobs assigned to each machine and the order of jobs such that the total machine load is minimized. Since the problem is NP-hard, optimal solution for the instances of realistic size cannot be obtained within a reasonable amount of computational time using exact solution approaches. Hence, an efficient method based on the hybrid particle swarm optimization (PSO) and genetic algorithm (GA), denoted by HPSOGA, is proposed to solve the given problem. In view of the fact that efficiency of the meta-heuristic algorithms is significantly depends on the appropriate design of parameters, the Taguchi method is employed to calibrate and select the optimal levels of parameters. The performance of the proposed method is appraised by comparing its results with GA and PSO with and without local search through computational experiments. The computational results for small sized problems show that the mentioned algorithms are fully effective and viable to generate optimal/near optimal solutions, but when the size of the problem is increased, the HPSOGA obtains better results in comparison with other algorithms.     

Single machine scheduling with batch-dependent setup times

We address a single-machine batch scheduling problem. The setup times (incurred whenever starting a new batch) are assumed to be a function of the number of batches processed previously, i.e., batch-dependent. The objective is minimum total flow-time. We focus on the case of identical processing time jobs. Given the number of jobs and the setup times, we have to determine the optimal number of batches and their (integer) size. An efficient (O(n)) solution procedure is introduced.     

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.     

Scheduling problems with deteriorating jobs and learning effects including proportional setup times

Recently, interest in scheduling with deteriorating jobs and learning effects has kept growing. However, research in this area has seldom considered setup times. We introduce a new scheduling model in which job deterioration and learning, and setup times are considered simultaneously. In the proposed model, the actual processing time of a job is defined as a function of the setup and processing times of the jobs already processed and the job’s own scheduled position in a sequence. In addition, the setup times are assumed to be proportional to the actual processing times of the already scheduled jobs. We derive polynomial-time optimal solutions for some single-machine problems with or without the presence of certain conditions.     

Deteriorating job scheduling to minimize the number of late jobs with setup times

Deteriorating jobs scheduling problems have been widely studied recently. However, research on scheduling problems with deteriorating jobs has rarely considered explicit setup times. With the current emphasis on customer service and meeting the promised delivery dates, we consider a single-machine scheduling problem to minimize the number of late jobs with deteriorating jobs and setup times in this paper. We derive some dominance properties, a lower bound, and an initial upper bound by using a heuristic algorithm to speed up the search process of the branch-and-bound algorithm. Computational experiments show that the algorithm can solve instances up to 1000 jobs in a reasonable amount of time.     

Single-machine scheduling with deteriorating jobs and setup times to minimize the maximum tardiness

In many realistic production situations, a job processed later consumes more time than the same job when it is processed earlier. Production scheduling in such an environment is known as scheduling with deteriorating jobs. However, research on scheduling problems with deteriorating jobs has rarely considered explicit (separable) setup time (cost). In this paper, we consider a single-machine scheduling problem with deteriorating jobs and setup times to minimize the maximum tardiness. We provide a branch-and-bound algorithm to solve this problem. Computational experiments show that the algorithm can solve instances up to 1000 jobs in reasonable time.     

Single machine batch scheduling problem with fuzzy batch size

In a batch scheduling problem, jobs are grouped (group is called batch) and scheduled in batches, and a setup time is incurred when starting a new batch. Processing times are assumed to be identical for all jobs. Setup times are assumed to be identical for all batches. Though all batch sizes cannot exceed a common upper bound, the upper bound is flexible and satisfaction degree with respect to the upper limit to be maximized is given. Also the other two objectives, i.e., the maximum completion time and the flow-time are to be minimized. Usually there exists no solution optimizing three objectives at a time. Therefore we define non-dominated solutions consisting of batch size, batch number and allocation of jobs to batches. First we propose an efficient algorithm for a sub-problem with fixed upper limit of batch size, fixed batch number based on a Lagrange relaxation procedure. Based on the properties of non-dominated solutions clarified in this paper, we propose an efficient algorithm to find some non-dominated solutions. Finally we summarize the results in this paper and discuss further research problems.     

Flowshop scheduling of deteriorating jobs on dominating machines

In this paper we consider the general, no-wait and no-idle permutation flowshop scheduling problem with deteriorating jobs, i.e., jobs whose processing times are increasing functions of their starting times. We assume a linear deterioration function with identical increasing rates for all the jobs and there are some dominating relationships between the machines. We show that the problems to minimize the makespan and the total completion time remain polynomially solvable when deterioration is considered, although these problems are more complicated than their classical counterparts without deterioration.     

Scheduling in a manufacturing shop with sequence-dependent setups

In this paper, the problem of scheduling multiple jobs in a flexible manufacturing cell with multiple machine stations is addressed. Due to the large capital investments that usually characterize flexible manufacturing systems (FMS), an area of control of great interest to system users is that of maximizing the system performance through the minimization of machine idle and setup times. The magnitude of total time spent on machine setups and idle times is influenced by the availability of jobs, job mix, similarities of jobs and job scheduling procedure used. Similar jobs on the same machine require less setup times. Similarly, the use of an adequate scheduling method also reduces total idle and setup times. Such reduction improves the flow times of jobs. In this paper, a heuristic algoritm for scheduling jobs with sequence dependent setup times in a FMS is presented. The measure of performance for evaluating schedule adequacy is the production makespan.     

Single-machine scheduling with deteriorating jobs under a series–parallel graph constraint

This paper considers single-machine scheduling problems with deteriorating jobs, i.e., jobs whose processing times are an increasing function of their starting times. In addition, the jobs are related by a series–parallel graph. It is shown that for the general linear problem to minimize the makespan, polynomial algorithms exist. It is also shown that for the proportional linear problem of minimization of the total weighted completion time, polynomial algorithms exist, too.     

Algorithms for job scheduling problems with distinct time windows and general earliness/tardiness penalties

This paper addresses the single machine scheduling problem with distinct time windows and sequence-dependent setup times. The objective is to minimize the total weighted earliness and tardiness. The problem involves determining the job execution sequence and the starting time for each job in the sequence. An implicit enumeration algorithm denoted IE and a general variable neighborhood search algorithm denoted GVNS are proposed to determine the job scheduling. IE is an exact algorithm, whereas GVNS is a heuristic algorithm. In order to define the starting times, an O(n²) idle time insertion algorithm (ITIA) is proposed. IE and GVNS use the ITIA algorithm to determine the starting time for each job. However, the IE algorithm is only valid for instances with sequence-independent setup times, and takes advantage of theoretical results generated for this problem. Computational experiments show that the ITIA algorithm is more efficient than the only other equivalent algorithm found in the literature. The IE algorithm allows the optimal solutions of all instances with up to 15 jobs to be determined within a feasible computational time. For larger instances, GVNS produces better-quality solutions requiring less computational time compared with the other algorithm from the literature.     

A note on optimal policies for two group scheduling problems with deteriorating setup and processing times

Conventionally, job processing times are known and fixed. However, there are many situations where the job processing time deteriorates as time passes. In this note, we consider the makespan problems under the group technology with deteriorating setup and processing times. That is, the job processing times and group setup times are linearly increasing (or decreasing) functions of their starting times. For both linear functions, we show that the makespan problems remain polynomially solvable. In addition, the constructive algorithms are also provided.     

Complexity Results for Single-Machine Problems with Positive Finish-Start Time-Lags

In a single-machine problem with time-lags a set of jobs has to be processed on a single machine in such a way that certain timing restrictions between the finishing and starting times of the jobs are satisfied and a given objective function is minimized. We consider the case of positive finish-start time-lags which mean that between the finishing time of job i and the starting time of job j the minimal distance has to be respected. New complexity results are derived for single-machine problems with constant positive time-lags which also lead to new results for flow-shop problems with unit processing times and job precedences. Received: May 13, 1998; revised November 23, 1998     

A branch-and-cut algorithm for a production scheduling problem with sequence-dependent and time-dependent setup times

This paper introduces and compares three different formulations of a production scheduling problem with sequence-dependent and time-dependent setup times on a single machine. The setup is divided into two parts: one that can be performed at any time and another one that is restricted to be performed outside of a given time interval. As a result, the setup time between two jobs is a function of the completion time of the first job. The problem can be formulated as a time-dependent traveling salesman problem, where the travel time between two nodes is a function of the departure time from the first node. We show that the resulting formulation can be strengthened to provide better linear programming relaxation lower bounds. We also introduce several families of valid inequalities which are used within a branch-and-cut algorithm. Computational experiments show that this algorithm can solve some instances with up to 50 jobs within reasonable computing times.     

Heuristics for the Unrelated Parallel Machine Scheduling Problem with Setup Times

The problem addressed in this paper is the non-preemptive unrelated parallel machine scheduling problem with the objective of minimizing the makespan. Machine-dependent and job sequence-dependent setup times are considered, all jobs are available at time zero, and all times are deterministic. This is a NP-hard problem and in this paper, optimal solutions are found for small problems only. For larger problems, a new meta-heuristic, Meta-RaPS, is introduced and its performance is evaluated by comparing its solutions to the solutions of an existing heuristic for the same problem. The results show that Meta-RaPS found all optimal solutions for the small problems and outperformed the solutions obtained by the existing heuristic for larger problems.     

Branch and Bound Algorithms for Single Machine Scheduling with Batching to Minimize the Number of Late Jobs

This paper considers the problem of scheduling a single machine to minimize the number of late jobs in the presence of sequence-independent family set-up times. The jobs are partitioned into families, and a set-up time is required at the start of each batch, where a batch is a maximal set of jobs in the same family that are processed consecutively. We design branch and bound algorithms that have several alternative features. Lower bounds can be derived by relaxing either the set-up times or the due dates. A first branching scheme uses a forward branching rule with a depth-first search strategy. Dominance criteria, which determine the order of the early jobs within each family and the order of the batches containing early jobs, can be fully exploited in this scheme. A second scheme uses a ternary branching rule in which the next job is fixed to be early and starting a batch, to be early and not starting a batch, or to be late. The different features are compared on a large set of test problems, where the number of jobs ranges from 30 to 50 and the number of families ranges from 4 to 10.     

Heuristics for minimizing total completion time and maximum lateness on identical parallel machines with setup times

This paper aims at minimizing the total completion time together with the maximum lateness. Jobs are processed by parallel machines in batches. A setup is required before processing a batch, which is common for all jobs in the batch. Jobs are continuously processed after the setup time. The processing length of a batch is the sum of the setup time and processing times of the jobs it contains. Due to the availability constraint, the completion time of a job is the time when a batch is totally processed. Considering due dates, the jobs need to be processed in a way that the total completion time and the maximum lateness are minimized. This problem is a kind of NP-hard so first we present a constructive heuristic to solve the problem. Then we propose a genetic algorithm whose initial population is formed by using the heuristic approach. Computational experiments are carried out to evaluate the performance of the proposed algorithms.     

Single machine scheduling with past-sequence-dependent setup times and learning effects

This paper studies a single machine scheduling problem with setup times and learning considerations. The setup times are proportional to the length of the already scheduled jobs. That is, the setup times are past-sequence-dependent. It is assumed that the learning process reflects a decrease in the process time as a function of the number of repetitions, i.e., as a function of the job position in the sequence. The following objectives are considered: the makespan, the total completion time, the total absolute differences in completion times and the sum of earliness, tardiness and common due-date penalty. Polynomial time algorithms are proposed to optimally solve the above objective functions.