Minimization of maximum lateness on parallel machines with sequence-dependent setup times and job release dates

In this paper, we consider an identical parallel machine scheduling problem with sequence-dependent setup times and job release dates. An improved iterated greedy heuristic with a sinking temperature is presented to minimize the maximum lateness. To verify the developed heuristic, computational experiments are conducted on a well-known benchmark problem data set. The experimental results show that the proposed heuristic outperforms the basic iterated greedy heuristic and the state-of-art algorithms on the same benchmark problem data set. It is believed that this improved approach will also be helpful for other applications.     

Heuristics for minimizing maximum lateness on a single machine with family-dependent set-up times

We address the problem of scheduling a single machine subject to family-dependent set-up times in order to minimize maximum lateness. We present a number of local improvement heuristics based on the work of previous researchers, a rolling horizon heuristic, and an incomplete dynamic programming heuristic. Extensive computational experiments on randomly generated test problems compare the performance of these heuristics. The rolling horizon procedures perform particularly well but require their parameters to be set based on problem characteristics to obtain their best performance.     

Scheduling identical jobs with unequal ready times on uniform parallel machines to minimize the maximum lateness

We consider the problem of scheduling n identical jobs with unequal ready times on m parallel uniform machines to minimize the maximum lateness. This paper develops a branch-and-bound procedure that optimally solves the problem and introduces six simple single-pass heuristic procedures that approximate the optimal solution. The branch-and-bound procedure uses the heuristics to establish an initial upper bound. On sample problems, the branch-and-bound procedure in most instances was able to find an optimal solution within 100,000 iterations with n≤80 and m≤3. For larger values of m, the heuristics provided approximate solutions close to the optimal values.     

A genetic algorithm for minimizing maximum lateness on parallel identical batch processing machines with dynamic job arrivals and incompatible job families

We consider the problem of minimizing maximum lateness on parallel identical batch processing machines with dynamic job arrivals. We propose a family of iterative improvement heuristics based on previous work by Potts [Analysis of a heuristic for one machine sequencing with release dates and delivery times. Operations Research 1980;28:1436–41] and Uzsoy [Scheduling batch processing machines with incompatible job families. International Journal for Production Research 1995;33(10):2685–708] and combine them with a genetic algorithm (GA) based on the random keys encoding of Bean [Genetic algorithms and random keys for sequencing and optimization. ORSA Journal on Computing 1994;6(2):154–60]. Extensive computational experiments show that one of the proposed GAs runs significantly faster than the other, providing a good tradeoff between solution time and quality. The combination of iterative heuristics with GAs consistently outperforms the iterative heuristics on their own.     

Minimizing job completion time variance for service stability on identical parallel machines

This paper addresses a job scheduling problem on multiple identical parallel machines so as to minimize job completion time variance (CTV). CTV minimization is closely related to the Just-In-Time philosophy and the service stability concept since it penalizes both earliness and tardiness. Its applications can be found in many real-life areas such as Internet data packet dispatching and production planning. This paper focuses on the unrestricted case of the problem where idle times are allowed to exist before machines start to process jobs. We prove several dominant properties about the optimal solution to the problem. For instance, we prove that the mean completion time (MCT) on each machine should be the same under an optimal schedule. Based on these properties, an efficient heuristic algorithm is proposed. Computational experiments are conducted to test the performance of the proposed algorithm. The outputs demonstrate that the proposed algorithm is near optimal for small problem instances and greatly outperforms some existing algorithms for large problem instances.     

A branch-and-bound algorithm to minimize total weighted completion time on identical parallel machines with job release dates

In this paper, we consider an identical parallel machine scheduling problem with release dates. The objective is to minimize the total weighted completion time. This problem is known to be strongly NP-hard. We propose some dominance properties and two lower bounds. We also present an efficient heuristic. A branch-and-bound algorithm, in which the heuristic, the lower bounds and the dominance properties are incorporated, is proposed and tested on a large set of randomly generated instances.     

Scheduling jobs on parallel machines with setup times and ready times

In this research we are interested in scheduling jobs with ready times on identical parallel machines with sequence dependent setups. Our objective is to minimize the total weighted tardiness. As this problem is NP-Hard, we develop a heuristic to solve this problem in reasonable time. Our approach is an extension of the apparent tardiness cost with setups (ATCS) approach by [Lee, Y. H., Pinedo, M. (1997). Scheduling jobs on parallel machines with sequence dependent setup times. European Journal of Operational Research, 100, 464–474.] to allow non-ready jobs to be scheduled – meaning we allow a machine to remain idle for a high priority job arriving at a later time. To determine the scaling parameters for our composite dispatching rule (called ATCSR), we first develop a ‘grid approach’ that considers multiple values for the scaling parameters, generates multiple schedules, and chooses the best schedule for the solution. This experimentation was then used to develop regression equations to predict the values of the scaling parameters that would yield the highest quality solution. The grid and regression versions of ATCSR provide better performance than grid and empirically based formula versions of ATCS, BATCS, and X-RM which are the prominent algorithms in the literature.     

On-line scheduling of parallel machines to minimize total completion times

In this paper, we consider the scheduling problem on identical parallel machines, in which jobs are arriving over time and preemption is not allowed. The goal is to minimize the total completion times. According to the idea of the Delayed-SPT Algorithm proposed by Hoogeven and Vestjens [Optimal on-line algorithms for single-machine scheduling. In: Proceedings 5th international conference on integer programming and combinatorial optimization (IPCO). Lecture notes in computer science, vol. 1084. Berlin: Springer; 1996. p. 404–14], we give an on-line algorithm for the scheduling problem on m$m$ identical parallel machines. We show that this algorithm is 2-competitive and the bound is tight.     

Minimizing maximum earliness on parallel identical machines

This paper addresses the scheduling problem of minimizing maximum earliness (or more generally — maximizing minimum lateness) on parallel identical machines. We prove that the two-machine case is NP-hard in the ordinary sense, and introduce a pseudo-polynomial dynamic programming algorithm for this case. When the number of machines is arbitrary, the problem is shown to be NP-hard in the strong sense. Then we introduce an efficient heuristic and two simple upper bounds on the optimal minimum lateness value. Finally we provide an extensive numerical study which indicates that the heuristic performs well in various job and machine settings.Scope and purposeIn recent years many researchers have focused on minimizing both earliness and tardiness costs. Only a few studies have considered problems with (maximum or total) earliness as the sole performance measure. We believe that the earliness measure is appropriate for many real-life settings, where the main cost component is the earliness (inventory) cost, and the tardiness (positive lateness) cost component is negligible. Our paper studies the scheduling problem of minmax earliness on parallel identical machines: we analyze the complexity of the problem, and introduce an efficient heuristic and simple bounds on the optimal cost.     

成组加工中有主从调整时间的最大延迟问题

针对钢管生产过程具有多产品和主从调整时间特性的实际批组调度问题,以最小化工件的最大延迟为目标函数,建立了问题的0-1混合整数规划模型;进而分析了问题的优化特性,提出了基于优化特性的禁忌搜索算法.仿真结果表明该算法是可行而有效的.     

Makespan minimization for scheduling unrelated parallel machines with setup times

This study considers the problem of scheduling jobs on unrelated parallel machines with machine-dependent and job sequence-dependent setup times. In this study, a restricted simulated annealing (RSA) algorithm which incorporates a restricted search strategy is presented to minimize the makespan. The proposed RSA algorithm can effective reduce the search effort required to find the best neighborhood solution by eliminating ineffective job moves. The effectiveness and efficiency of the proposed RSA algorithm is compared with the basic simulated annealing and existing meta-heuristics on a benchmark problem dataset used in earlier studies. Computational results indicate that the proposed RSA algorithm compares well with the state-of-the-art meta-heuristic for small-sized problems, and significantly outperforms basic simulated annealing algorithm and existing algorithms for large-sized problems.     

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.     

Online scheduling on batching machines to minimise the total weighted completion time of jobs with precedence constraints and identical processing times

This article studies online scheduling of equal length jobs with precedence constraints on m parallel batching machines. The jobs arrive over time. The objective is to minimise the total weighted completion time of jobs. Denote the size of each batch by b with b?=?∞ in the unbounded batching and b? m , where ρ _m is the positive solution of ρ ^m+1???ρ?=?1. The algorithm is also best possible when the jobs have identical weights. For the bounded batching version with identical weights of jobs, we provide an online algorithm with a competitive ratio of 2.     

Rescheduling of parallel machines with stochastic processing and setup times

This paper tackles rescheduling for the unrelated parallel machine problem with sequence dependent setup times and different rates of breakdowns or urgent jobs arrivals. The jobs’ processing and setup times are stochastic for better depiction of the real world. A new repair rule which will be referred to as Minimum Weighted C_max Difference (MWCD) is developed and compared to existing algorithms using simulation.     

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

Scheduling on parallel identical machines with job-rejection and position-dependent processing times

We solve scheduling problems which combine the option of job-rejection and general position-dependent processing times. The option of rejection reflects a very common scenario, where the scheduler may decide not to process a job if it is not profitable. The assumption of position-dependent processing time is a common generalization of classical settings, and contains the well-known and extensively studied special cases of “learning” and “aging”. The machine setting is parallel identical machines, and two scheduling measures are considered: total flow-time and total load. When the number of jobs is given, both problems are shown to be solved in polynomial time in the number of jobs. The special case of non-decreasing job-position processing times (“aging”) is shown to be solved much faster.     

Dynamic programming algorithms for scheduling parallel machines with family setup times

We address the problem of scheduling jobs with family setup times on identical parallel machines to minimize total weighted flowtime. We present two dynamic programming algorithms — a backward algorithm and a forward algorithm — and we identify characteristics of problems where each algorithm is best suited. We also derive two properties that improve the computational efficiency of the algorithms.Scope and purposeWhile most production schedulers must balance conflicting goals of high system efficiency and timely completion of individual jobs, consideration of this conflict is underdeveloped in the scheduling literature. This paper examines a model that incorporates a fundamental cause of the efficiency/timeliness conflict in practice. We propose solution methodologies and properties of an optimal solution for the purpose of exposing insights that may ultimately be useful in research on more complex models.