关于机器随机故障完工时间方差最小化单机调度问题

讨论了机器随机故障时,工件完工时间方差的期望最小化单机调度问题,其中描述机器故障的计数过程为广义泊松过程.推导出了目标函数等价的确定形式,而后进一步给出了工件加工时间相同时问题的最优解.     

A new neighborhood and tabu search for the Blocking Job Shop

The Blocking Job Shop is a version of the job shop scheduling problem with no intermediate buffers, where a job has to wait on a machine until being processed on the next machine. We study a generalization of this problem which takes into account transfer operations between machines and sequence-dependent setup times. After formulating the problem in a generalized disjunctive graph, we develop a neighborhood for local search. In contrast to the classical job shop, there is no easy mechanism for generating feasible neighbor solutions. We establish two structural properties of the underlying disjunctive graph, the concept of closures and a key result on short cycles, which enable us to construct feasible neighbors by exchanging critical arcs together with some other arcs. Based on this neighborhood, we devise a tabu search algorithm and report on extensive computational experience, showing that our solutions improve most of the benchmark results found in the literature.     

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

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

需要安装时间的两台多功能机排序问题的计算复杂性

提出需要安装时间的多功能机排序问题,一般情况下,这是NP-困难的;主要研究只有两台机器时一些特殊情况下的计算复杂性.根据加工集合为机器全集的工件组数的不同,分别给出多项式时间算法和分枝定界算法.对各工件组的工件数和加工时间都相等的情况,给出一个多项式时间的最优算法-奇偶算法,从而证明此问题是多项式时间可解的.     

A contribution to the stochastic flow shop scheduling problem

This paper deals with performance evaluation and scheduling problems in m machine stochastic flow shop with unlimited buffers. The processing time of each job on each machine is a random variable exponentially distributed with a known rate. We consider permutation flow shop. The objective is to find a job schedule which minimizes the expected makespan. A classification of works about stochastic flow shop with random processing times is first given. In order to solve the performance evaluation problem, we propose a recursive algorithm based on a Markov chain to compute the expected makespan and a discrete event simulation model to evaluate the expected makespan. The recursive algorithm is a generalization of a method proposed in the literature for the two machine flow shop problem to the m machine flow shop problem with unlimited buffers. In deterministic context, heuristics (like CDS [Management Science 16 (10) (1970) B630] and Rapid Access [Management Science 23 (11) (1977) 1174]) and metaheuristics (like simulated annealing) provide good results. We propose to adapt and to test this kind of methods for the stochastic scheduling problem. Combinations between heuristics or metaheuristics and the performance evaluation models are proposed. One of the objectives of this paper is to compare the methods together. Our methods are tested on problems from the OR-Library and give good results: for the two machine problems, we obtain the optimal solution and for the m machine problems, the methods are mutually validated.     

Sequencing and due-date determination in the stochastic single machine problem with earliness and tardiness costs

This paper studies the problem of simultaneous due-date determination and sequencing of a set of n jobs on a single machine where processing times are random variables and job earliness and tardiness costs are distinct. The objective is to determine the optimal sequence and the optimal due-dates which jointly minimize the expected total earliness and tardiness cost. We present an analytical approach to determine optimal due-dates, and propose two efficient heuristics of order O(n log n) to find candidates for the optimal sequence. It is demonstrated that variations in processing times increase cost and affect sequencing and due-date determination decisions. Our illustrative examples as well as computational results show that the proposed model produces optimal sequences and optimal due-dates that are significantly different from those provided by the classical deterministic single machine models. Furthermore, our computational experiments reveal that the proposed heuristics perform well in providing either optimal sequences or good candidates with low overcosts.     

A polynomial time heuristic for the two-machine flowshop scheduling problem with setup times and random processing times

The two-machine flowshop scheduling problem to minimize makespan is addressed. Jobs have random processing times which are bounded within certain intervals. The distributions of job processing times are not known. This problem has been addressed in the literature with the assumption that setup times are included in processing times or are zero. In this paper, we relax this assumption and treat setup times as separate from processing times. We propose a polynomial time heuristic algorithm. Both Johnson algorithm and Yoshida and Hitomi algorithm, both of which developed for the deterministic problem, are special cases of the proposed algorithm. The heuristic algorithm uses a weighted average of lower and upper bounds for processing times. For different weights, the results of the proposed algorithm are compared based on randomly generated data. The computational analysis has shown that the proposed algorithm, with equal weights given to the lower and upper bounds, performs considerably well with an overall average error of 0.36%. The analysis has also shown that the proposed algorithm can safely be used regardless of processing time distributions and the range between lower and upper bounds.     

Learning and forgetting effects on a group scheduling problem

This paper proposes to investigate learning and forgetting effects on the problem of scheduling families of jobs on a single machine to minimize total completion time of jobs. A setup time is incurred whenever the single machine transfers job processing from a family to another family. To analyze the impact of learning and forgetting on this group scheduling problem, we structure three basic models and make some comparisons through computational experiments. The three models, including no forgetting, total forgetting and partial forgetting, assume that the processing time of a job is dependent on its position in a schedule. Some scheduling rules and a lower bound are derived in order to constitute our branch-and-bound algorithm for searching an optimal sequence. In addition, an efficient and simply-structured heuristic is also built to find a near-optimal schedule.     

Batch scheduling with controllable setup and processing times to minimize total completion time

We study a problem of scheduling n jobs on a single machine in batches. A batch is a set of jobs processed contiguously and completed together when the processing of all jobs in the batch is finished. Processing of a batch requires a machine setup time dependent on the position of this batch in the batch sequence. Setup times and job processing times are continuously controllable, that is, they are real-valued variables within their lower and upper bounds. A deviation of a setup time or job processing time from its upper bound is called a compression. The problem is to find a job sequence, its partition into batches, and the values for setup times and job processing times such that (a) total job completion time is minimized, subject to an upper bound on total weighted setup time and job processing time compression, or (b) a linear combination of total job completion time, total setup time compression, and total job processing time compression is minimized. Properties of optimal solutions are established. If the lower and upper bounds on job processing times can be similarly ordered or the job sequence is fixed, then O(n³ log n) and O(n⁵) time algorithms are developed to solve cases (a) and (b), respectively. If all job processing times are fixed or all setup times are fixed, then more efficient algorithms can be devised to solve the problems.     

An adaptive TS approach to JIT sequencing with variable processing times and sequence-dependent setups

This paper addresses a single machine sequencing problem with variable processing times and sequence-dependent setups. The objective is to find the best trade-off between the JIT goal and the processing time compression and extension costs by simultaneously determining the job sequence and processing times for concerned jobs. Due to the combinatorial nature of the problem, it cannot be optimally solved in polynomial time. A tabu search approach is used to provide good and quick solutions. To improve the computational efficiency, an adaptive neighbourhood generation method is proposed and used in the tabu search algorithm. A total of 100 problems of different sizes have been solved to test the proposed approach. Our computational experience shows that the adaptive approach outperforms several other neighbourhood generation methods in terms of both convergence rate and solution quality. The effects of the search parameters are also discussed.     

A multi-stage stochastic programming approach in master production scheduling

Master Production Schedules (MPS) are widely used in industry, especially within Enterprise Resource Planning (ERP) software. The classical approach for generating MPS assumes infinite capacity, fixed processing times, and a single scenario for demand forecasts. In this paper, we question these assumptions and consider a problem with finite capacity, controllable processing times, and several demand scenarios instead of just one. We use a multi-stage stochastic programming approach in order to come up with the maximum expected profit given the demand scenarios. Controllable processing times enlarge the solution space so that the limited capacity of production resources are utilized more effectively. We propose an effective formulation that enables an extensive computational study. Our computational results clearly indicate that instead of relying on relatively simple heuristic methods, multi-stage stochastic programming can be used effectively to solve MPS problems, and that controllability increases the performance of multi-stage solutions.     

The museum visitor routing problem

In the museum visitor routing problem (MVRP), each visitor group has some exhibit rooms of interest. The visiting route of a certain visitor group requires going through all the exhibit rooms that the group wants to visit. Routes need to be scheduled based on certain criteria to avoid congestion and/or prolonged touring time. In this study, the MVRP is formulated as a mixed integer program which is an extension of the open shop scheduling (OSS) problem in which visitor groups and exhibit rooms are treated as jobs and machines, respectively. The time each visitor group spends in an exhibit room is analogous to the processing time required for each job on a particular machine. The travel time required from one exhibit room to another is modeled as the sequence-dependent setup time on a machine, which is not considered in the OSS problem. Due to the intrinsic complexity of the MVRP, a simulated annealing (SA) approach is proposed to solve the problem. Computational results indicate that the proposed SA approach is capable of obtaining high quality MVRP solutions within a reasonable amount of computational time and enables the approach to be used in practice.     

Minimizing sum of completion times on a single machine with sequence-dependent family setup times

This paper presents a branch-and-bound (B&B) algorithm for minimizing the sum of completion times in a single-machine scheduling setting with sequence-dependent family setup times. The main feature of the B&B algorithm is a new lower bounding scheme that is based on a network formulation of the problem. With extensive computational tests, we demonstrate that the B&B algorithm can solve problems with up to 60 jobs and 12 families, where setup and processing times are uniformly distributed in various combinations of the [1,50] and [1,100] ranges.     

Stochastic single machine scheduling subject to machines breakdowns with quadratic early-tardy penalties for the preemptive-repeat model

In this paper we research the problem in which the objective is to minimize the sum of squared deviations of job expected completion times from the due date, and the job processing times are stochastic. In the problem the machine is subject to stochastic breakdowns and all jobs are preempt-repeat. In order to show that the replacing ESSD by SSDE is reasonable, we discuss difference between ESSD function and SSDE function. We first give an express of the expected completion times for both cases without resampling and with resampling. Then we show that the optimal sequence of the problem V-shaped with respect to expected occupying time. A dynamic programming algorithm based on the V-shape property of the optimal sequence is suggested. The time complexity of the algorithm is pseudopolynomial.     

Scheduling in bicriteria single machine systems with past-sequence-dependent setup times and learning effects

Scheduling with setup times and learning plays a crucial role in today's manufacturing and service environments where scheduling decisions are made with respect to multiple performance criteria rather than a single criterion. In this paper, we address a bicriteria single machine scheduling problem with job-dependent past-sequence-dependent setup times and job-dependent position-based learning effects. The setup time and actual processing time of a job are respectively unique functions of the actual processing times of the already processed jobs and the position of the job in a schedule. The objective is to derive the schedule that minimizes a linear composite function of a pair of performance criteria consisting of the makespan, the total completion time, the total lateness, the total absolute differences in completion times, and the sum of earliness, tardiness, and common due date penalty. We show that the resulting problems cannot be solved in polynomial time; thus, branch-and-bound (B&B) methods are proposed to obtain the optimal schedules. Our computational results demonstrate that the B&B can solve instances of various size problems with attractive times.     

The interface of buffer design and cyclic scheduling decisions in deterministic flow lines

In this paper, we address some issues on the interface of buffer design and cyclic scheduling decisions in a multi-product deterministic flow line. We demonstrate the importance of the above interface for the throughput performance of the flow line. In particular, we point out that the use of sequence-independent information, such as workload distribution and variability in processing times among stations, is not adequate to decide the optimal buffer configuration of the flow line. We formulate the buffer design problem for a fixed sequence of jobs as a general resource allocation problem, and suggest two effective heuristics for its solution. For the simultaneous buffer design and cyclic scheduling problem, we suggest an iterative scheme that builds on the effectiveness of the above heuristics. One of the side results of our extensive computational studies on this problem is that the general guidelines of buffer design in single-product flow lines with stochastic processing times are not directly transferable to the multiproduct deterministic flow line environment.     

Generalization of Johnson's and Talwar's scheduling rules in two-machine stochastic flow shops

The paper deals with the classical problem of minimizing the makespan in a two-machine flow shop. When the job processing times are deterministic, the optimal job sequence can be determined by applying Johnson's rule. When they are independent and exponential random variables, Talwar's rule yields a job sequence that minimizes the makespan stochastically. Assuming that the random job processing times are independent and Gompertz distributed, we propose a new scheduling rule that is a generalization of both Johnson's and Talwar's rules. We prove that our rule yields a job sequence that minimizes the makespan stochastically. Extensions to m-machine proportionate stochastic flow shops, two-machine stochastic job shops, and stochastic assembly systems are indicated.     

A hybrid approach for single-machine tardiness problems with sequence-dependent setup times

Scheduling problems in real systems often require sequence-dependent setup times. The topic of sequence-dependent setup times has not been addressed adequately, and improved competitiveness is thus not achieved. This study proposes a hybrid approach that takes advantage of simulated annealing (SA) and tabu search (TS) to solve single-machine tardiness problems with sequence-dependent setup times. To verify the proposed approach, experiments were conducted on benchmark problem sets that included both the weighted and un-weighted tardiness problems. The results show that the performance of the hybrid approach is superior to that of the SA, genetic algorithm, TS and ant colony optimization approaches, and is comparable with the Tabu-VNS approach. And the proposed approach found new upper bound values for many benchmark problems with an acceptable computational time.     

Single machine group scheduling with resource dependent setup and processing times

A single machine scheduling problem is studied. There is a partition of the set of n jobs into g groups on the basis of group technology. Jobs of the same group are processed contiguously. A sequence independent setup time precedes the processing of each group. Two external renewable resources can be used to linearly compress setup and job processing times. The setup times are jointly compressible by one resource, the job processing times are jointly compressible by another resource and the level of the resource is the same for all setups and all jobs. Polynomial time algorithms are presented to find an optimal job sequence and resource values such that the total weighted resource consumption is minimum, subject to meeting job deadlines. The algorithms are based on solving linear programming problems with two variables by geometric techniques.     

Vehicle scheduling with combinable delivery and pickup operations

Motivated by the logistics operations in an express delivery company, we develop and study a new scheduling model. The problem seems similar to scheduling with sequence-dependent setup times and scheduling with release times, however, the ability to combine or separate the job operations makes our problem unique.