Unrelated parallel-machine scheduling with aging effects and multi-maintenance activities

Machine maintenance is often performed in manufacturing to prevent premature machine failures with a view to sustaining production efficiency. In this paper we study the parallel-machine scheduling problem with aging effects and multi-maintenance activities simultaneously. We assume that each machine may be subject to several maintenance activities over the scheduling horizon. A machine reverts to its initial condition after maintenance and the aging effects start anew. The objective is to find jointly the optimal maintenance frequencies, the optimal positions of the maintenance activities, and the optimal job sequences such that the total machine load is minimized. We apply the group balance principle to obtain the optimal positions of the maintenance activities and the number of jobs in each group in the scheduling sequence on each machine. We provide an efficient algorithm to solve the problem when the maintenance frequencies on the machines are given.     

Unrelated parallel-machine scheduling with deteriorating maintenance activities

We study the problem of unrelated parallel-machine scheduling with deteriorating maintenance activities. Each machine has at most one maintenance activity, which can be performed at any time throughout the planning horizon. The length of the maintenance activity increases linearly with its starting time. The objective is to minimize the total completion time or the total machine load. We show that both versions of the problem can be optimally solved in polynomial time.     

Note on “Unrelated parallel-machine scheduling with deteriorating maintenance activities”

In this note, we prove that both problems studied by Cheng et al. [Cheng, T. C. E., Hsu, C.-J., & Yang, D.-L. (2011). Unrelated parallel-machine scheduling with deteriorating maintenance activities. Computers and Industrial Engineering, 60, 602–605] can be solved in O(n^m+3) time no matter what the processing time of a job after a maintenance activity is greater or less than its processing time before the maintenance activity, where m is the number of machines and n is the number of jobs.     

Two-agent singe-machine scheduling with release times to minimize the total weighted completion time

In many management situations multiple agents pursuing different objectives compete on the usage of common processing resources. In this paper we study a two-agent single-machine scheduling problem with release times where the objective is to minimize the total weighted completion time of the jobs of one agent with the constraint that the maximum lateness of the jobs of the other agent does not exceed a given limit. We propose a branch-and-bound algorithm to solve the problem, and a primary and a secondary simulated annealing algorithm to find near-optimal solutions. We conduct computational experiments to test the effectiveness of the algorithms. The computational results show that the branch-and-bound algorithm can solve most of the problem instances with up to 24 jobs in a reasonable amount of time and the primary simulated annealing algorithm performs well with an average percentage error of less than 0.5% for all the tested cases.     

Two-agent two-machine flowshop scheduling with learning effects to minimize the total completion time

We study a two-agent scheduling problem in a two-machine permutation flowshop with learning effects. The objective is to minimize the total completion time of the jobs from one agent, given that the maximum tardiness of the jobs from the other agent cannot exceed a bound. We provide a branch-and-bound algorithm for the problem. In addition, we present several genetic algorithms to obtain near-optimal solutions. Computational results indicate that the algorithms perform well in either solving the problem or efficiently generating near-optimal solutions.     

The two-stage assembly scheduling problem to minimize total completion time with setup times

We address the two-stage assembly scheduling problem where there are m machines at the first stage and an assembly machine at the second stage. The objective is to schedule the available n jobs so that total completion time of all n jobs is minimized. Setup times are treated as separate from processing times. This problem is NP-hard, and therefore we present a dominance relation and propose three heuristics. The heuristics are evaluated based on randomly generated data. One of the proposed heuristics is known to be the best heuristic for the case of zero setup times while another heuristic is known to perform well for such problems. A new version of the latter heuristic, which utilizes the dominance relation, is proposed and shown to perform much better than the other two heuristics.     

Three scheduling problems with deteriorating jobs to minimize the total completion time

In this paper, three scheduling problems with deteriorating jobs to minimize the total completion time on a single machine are investigated. By a deteriorating job, we mean that the processing time of the job is a function of its execution start time. The three problems correspond to three different decreasing linear functions, whose increasing counterparts have been studied in the literature. Some basic properties of the three problems are proved. Based on these properties, two of the problems are solved in O(nlogn) time, where n is the number of jobs. A pseudopolynomial time algorithm is constructed to solve the third problem using dynamic programming. Finally, a comparison between the problems with job processing times being decreasing and increasing linear functions of their start times is presented, which shows that the decreasing and increasing linear models of job processing times seem to be closely related to each other.     

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.     

Approximation algorithms for multi-agent scheduling to minimize total weighted completion time

We consider a multi-agent scheduling problem on a single machine in which each agent is responsible for his own set of jobs and wishes to minimize the total weighted completion time of his own set of jobs. It is known that the unweighted problem with two agents is NP-hard in the ordinary sense. For this case, we can reduce our problem to a Multi-Objective Shortest-Path (MOSP) problem and this reduction leads to several results including Fully Polynomial Time Approximation Schemes (FPTAS). We also provide an efficient approximation algorithm with a reasonably good worst-case ratio.     

Scheduling with job-dependent learning effects and multiple rate-modifying activities

We consider a scheduling problem with job-dependent learning effects and multiple rate-modifying activities. The learning effects manifest such that the processing time of a job is a decreasing function of its position in a sequence. By job-dependent learning effects, we mean that the learning of the jobs is different. A rate-modifying activity is an activity that changes the production rate of a machine. So the actual processing time of a job in our problem is a variable, which depends not only on its position in a sequence but also on whether it is scheduled before or after a rate-modifying activity. We assume that each machine may have multiple rate-modifying activities. The objective is to minimize the total completion time. We show that all the cases of the problem are polynomially solvable.     

The two-machine flowshop no-wait scheduling problem with a single server to minimize the total completion time

This work studies the scheduling problem where a set of jobs are available for processing in a no-wait and separate setup two-machine flow shop system with a single server. The no-wait constraint requires that the operations of a job have to be processed continuously without waiting between two machines. The setup time is incurred and attended by a single sever which can perform one setup at a time. The performance measure considered is the total completion time. The problem is strongly NP-hard. Optimal solutions for several restricted cases and some properties for general case are proposed. Both the heuristic and the branch and bound algorithms are established to tackle the problem. Computational experiments indicate that the heuristic and the branch and bound algorithm are superior to the existing ones in term of solution quality and number of branching nodes, respectively.     

Optimizing blocking flow shop scheduling problem with total completion time criterion

The blocking flow shop scheduling problem has found many applications in manufacturing systems. There are a few exact methods for solving this problem with different criteria. In this paper, efforts will be made to optimize the total completion time criterion for this problem. We present two mixed binary integer programming models, one of which is based on the departure times of jobs from machines, and the other is based on the idle and blocking times of jobs. An initial upper bound generator and some lower bounds and dominance rules are also developed to be used in a branch and bound algorithm. The algorithm solves 17 instances of the Taillard's benchmark problem set in less than 20 min.     

Scheduling with tool changes to minimize total completion time under controllable machining conditions

Scheduling under controllable machining conditions has been studied for some time. Scheduling with tool changes, particularly due to tool wear, has just begun to receive attention. Though machining conditions impact tool wear and induce tool change, the two issues have not been considered together. We address for the first time the problem of scheduling a computer numerically controlled (CNC) machine subject to tool changes and controllable machining conditions; our objective is to minimize the total completion time of a given set of jobs. We establish an important result that helps us identify feasible settings of machining parameters such as feed rate and cutting speed. However, the problem at hand remains intractable, even when a single setting is used. In the general case, we are able to solve the problem exactly for up to 30 jobs using a mixed integer linear programming formulation. For larger problems, we turn to approximate solution via heuristics. We examine a number of different schemes. The best of these schemes are used in a problem space genetic algorithm; this produces quality solutions in a time-efficient manner, as is evidenced from an extensive computational study conducted by us.     

Common due date assignment and scheduling with a rate-modifying activity to minimize the due date,earliness, tardiness,holding, and batch delivery cost

e consider a single-machine batch delivery scheduling and common due date assignment problem. In addition to making decisions on sequencing the jobs, determining the common due date, and scheduling job delivery, we consider the option of performing a rate-modifying activity on the machine. The processing time of a job scheduled after the rate-modifying activity decreases depending on a job-dependent factor. Finished jobs are delivered in batches. There is no capacity limit on each delivery batch, and the cost per batch delivery is fixed and independent of the number of jobs in the batch. The objective is to find a common due date for all the jobs, a location of the rate-modifying activity, and a delivery date for each job to minimize the sum of earliness, tardiness, holding, due date, and delivery cost. We provide some properties of the optimal schedule for the problem and present polynomial algorithms for some special cases.     

A new Lagrangian relaxation algorithm for hybrid flowshop scheduling to minimize total weighted completion time

We investigate the problem of scheduling n jobs in s-stage hybrid flowshops with parallel identical machines at each stage. The objective is to find a schedule that minimizes the sum of weighted completion times of the jobs. This problem has been proven to be NP-hard. In this paper, an integer programming formulation is constructed for the problem. A new Lagrangian relaxation algorithm is presented in which precedence constraints are relaxed to the objective function by introducing Lagrangian multipliers, unlike the commonly used method of relaxing capacity constraints. In this way the relaxed problem can be decomposed into machine type subproblems, each of which corresponds to a specific stage. A dynamic programming algorithm is designed for solving parallel identical machine subproblems where jobs may have negative weights. The multipliers are then iteratively updated along a subgradient direction. The new algorithm is computationally compared with the commonly used Lagrangian relaxation algorithms which, after capacity constraints are relaxed, decompose the relaxed problem into job level subproblems and solve the subproblems by using the regular and speed-up dynamic programming algorithms, respectively. Numerical results show that the new Lagrangian relaxation method produces better schedules in much shorter computation time, especially for large-scale problems.     

Two-machine flowshop scheduling with truncated learning to minimize the total completion time

Scheduling with learning effects has received a lot of research attention lately. However, the flowshop setting is relatively unexplored. On the other hand, the actual processing time of a job under an uncontrolled learning effect will drop to zero precipitously as the number of jobs increases. This is rather absurd in reality. Motivated by these observations, we consider a two-machine flowshop scheduling problem in which the actual processing time of a job in a schedule is a function of the job’s position in the schedule and a control parameter of the learning function. The objective is to minimize the total completion time. We develop a branch-and-bound and three simulated annealing algorithms to solve the problem. Computational results show that the proposed algorithms are efficient in producing near-optimal solutions.