机器具有准备时间的双目标平行机排序问题

本文讨论机器具有准备时间的双目标平行机排序问题，目标函数为完工时间和最优条件下极小化最大完工时间．通过对SPT排序的性质的分析，给出了最优排序的下界．在此基础上证明了SPT排序的误差界为3／2，并且是紧界．     

A branch and bound based heuristic for makespan minimization of washing operations in hospital sterilization services

In this paper, we address the problem of parallel batching of jobs on identical machines to minimize makespan. The problem is motivated from the washing step of hospital sterilization services where jobs have different sizes, different release dates and equal processing times. Machines can process more than one job at the same time as long as the total size of jobs in a batch does not exceed the machine capacity. We present a branch and bound based heuristic method and compare it to a linear model and two other heuristics from the literature. Computational experiments show that our method can find high quality solutions within short computation time.     

Scheduling interfering job sets on parallel machines

We consider bicriteria scheduling on identical parallel machines in a nontraditional context: jobs belong to two disjoint sets, and each set has a different criterion to be minimized. The jobs are all available at time zero and have to be scheduled (non-preemptively) on m parallel machines. The goal is to generate the set of all non-dominated solutions, so the decision maker can evaluate the tradeoffs and choose the schedule to be implemented. We consider the case where, for one of the two sets, the criterion to be minimized is makespan while for the other the total completion time needs to be minimized. Given that the problem is NP-hard, we propose an iterative SPT–LPT–SPT heuristic and a bicriteria genetic algorithm for the problem. Both approaches are designed to exploit the problem structure and generate a set of non-dominated solutions. In the genetic algorithm we use a special encoding scheme and also a unique strategy – based on the properties of a non-dominated solution – to ensure that all parts of the non-dominated front are explored. The heuristic and the genetic algorithm are compared with a time-indexed integer programming formulation for small and large instances. Results indicate that the both the heuristic and the genetic algorithm provide high solution quality and are computationally efficient. The heuristics proposed also have the potential to be generalized for the problem of interfering job sets involving other bicriteria pairs.     

Single-machine scheduling to minimize total absolute differences in waiting times with deteriorating jobs

In this paper we consider a single-machine scheduling problem with simple linear deterioration. By simple linear deterioration, we mean that the processing time of a job is a simple linear function of its execution starting time and its deterioration rate. The objective is to find a schedule that minimizes total absolute differences in waiting times. We show that the optimal schedule is V-shaped: jobs are arranged in descending order of their deterioration rates if they are placed before the job with the smallest deterioration rate, but in ascending order of their deterioration rates if placed after it. We prove other several properties of an optimal schedule, and introduce two efficient heuristic algorithms that are tested against a lower bound. We also provide computational results to evaluate the performance of the heuristic algorithms.     

A branch and bound algorithm for the one-machine scheduling problem with minimum and maximum time lags

We consider the one-machine scheduling problem with minimum and maximum time lags while minimizing the makespan. This problem typically arises in a manufacturing environment where the next job has to be carried out within a specific time range after the completion of the immediately preceding job. We describe a branch and bound algorithm, based on the input and output of a clique and the relevant propositions, for finding the optimal waiting times. The computational experiments give promising results, showing whether a given instance is feasible or infeasible. With the proposed branch and bound algorithm we can either find an optimal schedule or establish the infeasibility within an acceptable run time.     

On-line two-machine open shop scheduling with time lags

We analyze the performance of the greedy algorithm for the on-line two-machine open shop scheduling problem of minimizing makespan, in which time lags exist between the completion time of the first and the start time of the second operation of any job. The competitive ratio for the greedy algorithm is 2, and it can be reduced to 5/3 if the maximum time lag is less than the minimum positive processing time of any operation. These ratios are tight. We also prove that no on-line non-delay algorithm can have a better competitive ratio.     

Two-Machine Flowshop Batching and Scheduling

We consider in this paper a two-machine flowshop scheduling problem in which the first machine processes jobs individually while the second machine processes jobs in batches. The forming of each batch on the second machine incurs a constant setup time. The objective is to minimize the makespan. This problem was previously shown to be NP-hard in the ordinary sense. In this paper, we first present a strong NP-hardness result of the problem. We also identify a polynomially solvable case with either anticipatory or non-anticipatory setups. We then establish a property that an optimal solution for the special case is a lower bound for the general problem. To obtain near-optimal solutions for the general problem, we devise some heuristics. The lower bound is used to evaluate the quality of the heuristic solutions. Results of computational experiments reveal that the heuristics produce solutions with small error ratios. They also suggest that the lower bound is close to the optimal solution.     

Minimizing makespan with multiple-orders-per-job in a two-machine flowshop

We investigate a new scheduling problem, multiple-orders-per-job (MOJ), in the context of a two-machine flowshop. Lower bounds for the makespan performance measure are provided for combinations of lot-processing and item-processing machines. An optimization model is presented that addresses both job formation and job sequencing. We define a heuristic to minimize the makespan for the MOJ problem for two-machine item-processing flowshops. The heuristic obtains solutions within 2% of a tight lower bound and runs in O(HF) time, where H is the number of orders and F is the restricted number of jobs.     

Heuristics for the flow line problem with setup costs

This paper presents two new heuristics for the flowshop scheduling problem with sequence-dependent setup times (SDSTs) and makespan minimization objective. The first is an extension of a procedure that has been very successful for the general flowshop scheduling problem. The other is a greedy randomized adaptive search procedure (GRASP) which is a technique that has achieved good results on a variety of combinatorial optimization problems. Both heuristics are compared to a previously proposed algorithm based on the traveling salesman problem (TSP). In addition, local search procedures are developed and adapted to each of the heuristics. A two-phase lower bounding scheme is presented as well. The first phase finds a lower bound based on the assignment relaxation for the asymmetric TSP. In phase two, attempts are made to improve the bound by inserting idle time. All procedures are compared for two different classes of randomly generated instances. In the first case where setup times are an order of magnitude smaller than the processing times, the new approaches prove superior to the TSP-based heuristic; for the case where both processing and setup times are identically distributed, the TSP-based heuristic outperforms the proposed procedures.     

Single-machine scheduling problems with time and position dependent processing times

We consider single-machine scheduling problems with time and position dependent job processing times. In many industrial settings, the processing time of a job changes due to either job deterioration over time or machine/worker’s learning through experiences. In the models we study, each job has its normal processing time. However, a job’s actual processing time depends on when its processing starts and how many jobs have completed before its start. We prove that the classical SPT (Shortest Processing Time) rule remains optimal when we minimize the makespan or the total completion time. For problems of minimizing the total weighted completion time, the maximum lateness, and the discounted total weighted completion time, we present heuristic sequencing rules and analyze the worst-case bounds for performance ratios. We also show that these heuristic rules can be optimal under some agreeable conditions between the normal processing times and job due dates or weights.     

Minimizing makespan in parallel flowshops

In this study, a new class of proportional parallel flow shop problems with the objective of minimizing the makespan has been addressed. A special case for this problem in which jobs are processed on only one machine as opposed to two or more machines in a flow shop, is the well-known multiple processor problem which is NP-complete. The parallel processor problem is a restricted version of the problems addressed in this paper and hence are NP-complete. We develop and test heuristic and simulation approaches to solve large scale problems, while using exact procedures for smaller problems. The performance of the heuristics relative to the LP lower bound as well as a comparison with the truncated integer programming solution are reported. The performance of the heuristics and the simulation results were encouraging.     

Scheduling batches in flowshop with limited buffers in the shampoo industry

In this paper we address the problem of planning a temporary storage area in a real production system. This temporary storage area is composed of parallel temporary storage units with distinct capacities. The storage operation of a job, also called a batch, has to answer time restrictions such as release dates, due dates, restricted family dependent setup times and time lags, and also a space constraint which is the capacity of the temporary storage unit. The goal is to schedule the batches on the storage units in order to minimize the total setup times and the maximum lateness. First, we model the problem on a single storage unit as a two-machine flowshop problem with a limited buffer capacity and we show that it is NP-hard. We also show that the particular case in which no lateness is allowed is solvable in polynomial time under special conditions on the buffer capacity, both for single or parallel temporary storage units. Next we provide three heuristics: a greedy algorithm, a hybrid heuristic based on Ant Colony Optimization and Simulated Annealing and finally a dedicated heuristic. The latter strongly exploits the structural properties shown in this paper. We provide experimental results which highlight the efficiency of the dedicated heuristic in comparison with the two other heuristics.     

工件具有子工件工期的排序问题

研究了工件具有子工件工期的排序问题.需要在一台单机上加工若干个给定的工件.每个工件由若干个子工件组成,每个子工件都有各自的工期.只有当工件的每个子工件都按时完成,才能称该工件是按时完工工件,否则,称该工件产生延误.目标是最大化按时完工的工件个数.证明当每个工件都被分成两个子工件时,该问题是NP-难的,而且不存在完全多项式时间近似方案(fully polynomial time approximation scheme,简记为FPTAS).提出两个启发式算法,利用数值模拟比较它们的性能,并且将这两个启发式算法的解与最优解的上界进行比较.     

需要安装时间的平行多功能机排序问题的启发式算法

考虑需要安装时间的平行多功能机排序问题。在该模型中,每个工件对应机器集合的一个子集,其只能在这个子集中的任一台机器上加工,称这个子集为该工件的加工集合;工件分组,同组工件具有相同的加工时间和加工集合,不同组中的工件在同一台机器上连续加工需要安装时间,目标函数为极小化最大完工时间。对该问题NP-难的一般情况设计启发式算法:首先按照特定的规则将所有工件组都整组地安排到各台机器上,然后通过在各机器间转移工件不断改进当前最大完工时间。通过与下界的比较检验算法的性能,大量的计算实验表明,算法是实用而有效的。     

An empirical analysis of the optimality rate of flow shop heuristics

If a certain optimization problem is NP-hard or even harder, one could expect that the chances of solving it optimally should rather decrease with an increase of the problem size. We reveal, however, that the opposite occurs for a strongly NP-hard problem, which requires sequencing n jobs through an m machine flow shop so as to minimize the makespan. In particular, we empirically examine optimality rates (the probability of being optimal) of the famous NEH heuristic of Nawaz et al. [Nawaz, M., Enscore, Jr., E., Ham, I., 1983. A heuristic algorithm for the m-machine, n-job flow-shop sequencing problem. Omega, The International Journal of Management Science 11, 91–95] and two improved versions of NEH. By using millions of simulation trials and a new effective lower bound on the shortest makespan, we observe relatively high optimality rates of the three heuristics for small values of m. Rather surprisingly, for larger values of n, the heuristics become more frequently optimal as n increases. Neither theoretical nor empirical studies of optimality rates of flow shop heuristics have been conducted so far, and – to the best of our knowledge – no similar studies are known in the field of operations research.     

Two-machine open shop scheduling with special transportation times

The paper considers a problem of scheduling n jobs in a two-machine open shop to minimise the makespan, provided that preemption is not allowed and the interstage transportation times are involved. In general, this problem is known to be NP-hard. We present a linear time algorithm that finds an optimal schedule if no transportation time exceeds the smallest of the processing times. We also describe an algorithm that creates a heuristic solution to the problem with job-independent transportation times. Our algorithm provides a worst-case performance ratio of 8/5 if the transportation time of a job depends on the assigned processing route. The ratio reduces to 3/2 if all transportation times are equal.     

A Worst-case Performance of the Shortest-processing-time Heuristic for Single Machine Scheduling

This paper analyses a worst-case performance of the shortest-processing-time (SPT) heuristic in minimizing a quadratic function of job lateness for single machine scheduling. A sufficient condition on processing-plus-wait due dates is found for the SPT sequence to be optimal. A worst-case lower bound to the optimal solution is derived from the SPT sequence. It is then shown that the SPT sequence is asymptotically optimal. Extensive computational experiments suggest that the SPT heuristic may be a good choice for just-in-time production.     

Performance of scheduling algorithms for no-wait flowshops with parallel machines

We study the performance of scheduling algorithms for a manufacturing system, called the ‘no-wait flowshop’, which consists of a certain number of machine centers. Each center has one or more identical parallel machines. Each job is processed by at most one machine in each center. The problem of finding the minimum finish time schedule is considered here in a flowshop consisting of two machine centers. Heuristic algorithms are presented and are analyzed in the worst case performance context. For the case of two centers, one with a single machine and the other with m, two heuristics are presented with tight performance guarantees of 3 − (1/m) and 2. When both centers have m machines, a heuristic is presented with an upper bound performance guarantee of . It is also shown that this bound can be reduced to 2(1 + ε). For the flowshop with any number of machines in each center, we provide a heuristic algorithm with an upper bound performance guarantee that depends on the relative number of machines in the centers.     

Two-stage open shop scheduling with a bottleneck machine

It is known that for the open shop scheduling problem to minimize the makespan there exists no polynomial-time heuristic algorithm that guarantees a worst-case performance ratio better than 5/4, unless P≠NP. However, this result holds only if the instance of the problem contains jobs consisting of at least three operations. This paper considers the open shop scheduling problem, provided that each job consists of at most two operations, one of which is to be processed on one of the m⩾2 machines, while the other operation must be performed on the bottleneck machine, the same for all jobs. For this NP-hard problem we present a heuristic algorithm and show that its worst-case performance ratio is 5/4.     

Efficient heuristics for flowshop sequencing with the objectives of makespan and flowtime minimisation

In this paper we analyse the performance of flowshop sequencing heuristics with respect to the objectives of makespan and flowtime minimisation. For flowtime minimisation, we propose the strategy employed by the NEH heuristic to construct partial solutions. Results show that this approach outperforms the common fast heuristics for flowtime minimisation while performing similarly or slightly worse than others which, on reward, prove to be much more CPU time-consuming. Additionally, the suggested approach is well balanced with respect to makespan and flowtime minimisation. Based on the previous results, two algorithms are proposed for the sequencing problem with multiple objectives – makespan and flowtime minimisation. These algorithms provide the decision maker with a set of heuristically efficient solutions such that he/she may choose the most suitable sequence for a given ratio between costs associated with makespan and those assigned to flowtime. Computational experience shows both algorithms to perform better than the current heuristics designed for the two-criteria problem.