非同类机极小化最大完工时间的保密排序问题

提出并研究了一类非同类机的极小化最大完工时间的保密排序问题Rm||Cmax.该问题的模型参数分为若干组,每个组都由一个不愿意共享或公开自己数据的单位所拥有.基于随机矩阵变换构造了一个不泄露私有数据且与原问题等价的安全规划模型,求解该安全模型可以获得问题的最优解,而且各单位的隐私数据仍然保持不被泄露.     

A heuristic for minimizing the expected makespan in two-machine flow shops with consistent coefficients of variation

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 job processing times are independently and Weibull distributed random variables, we present a new job sequencing rule that includes both Johnson’s and Talwar’s rules as special cases. The proposed rule is applicable as a heuristic whenever the job processing times are characterized by their means and the same coefficient of variation. Simulation results show that it leads to very encouraging results when the expected makespan is minimized.     

A note on makespan minimization in two-stage flexible flow shops with uniform machines

We consider the two-stage flexible flow shop makespan minimization problem with uniform parallel machines. Soewandi and Elmaghraby [Soewandi, H., Elmaghraby, S., 2003. Sequencing on two-stage hybrid flowshops with uniform machines to minimize makespan. IIE Transaction 35, 467–477] developed a heuristic (S–E) and derived a machine speed-dependent worst-case ratio bound for it. We point out that this bound works well when the uniform machines have approximately equal speeds but is not indicative of the performance of the S–E heuristic when the machine speeds are in a wide range. Motivated by this observation, we propose an alternative tight machine-speed dependent worst-case bound for the S–E heuristic that works well when the machine speeds vary significantly. We then combine the two speed-dependent ratio bounds into a speed-independent bound. Our findings facilitate the narrowing of the gap between experimental performance and worst-case bound for the S–E heuristic.     

Evaluation of the expected makespan of a set of non-resumable jobs on parallel machines with stochastic failures

In this paper we consider a production process at operative level on m$m$ identical parallel machines, which are subject to stochastic machine failures. To avoid long downtime of the machines, caused by unexpected failures, preventive maintenance activities are planned and conducted, but if a failure could not be averted a corrective maintenance has to be performed. Both maintenance activities are assumed to restore the machine to be “as good as new”. The maintenance activities, the number of jobs and their allocation to machines as well as their sequence have a large impact on the performance of the production process and the delivery dates.     

An improved part grouping model for minimizing makespan in FMS

In some flexible manufacturing systems (FMSs), limited tool magazine capacity requires grouping of parts into subsets for production. Although several studies have addressed the part grouping issue, research comparing the performance of models is scanty. Moreover, there is no congruency in the objectives of the present part grouping models and subsequent loading models. Traditionally, part grouping is addressed before machine loading. In this study, we overcome the drawbacks by proposing two models: model LM, which does not require part grouping, and model PGLRM (part grouping, loading and routing model), which requires part grouping. The performance of model LM serves as a benchmark. These two models also address machine loading and part routing issues concurrently. Model PGLRM's performance is then compared with the performance of model LM and few other existing part grouping models in terms of makespan and routing flexibility. Our analysis shows that model PGLRM not only results in a lower value of makespan but also imparts higher routing flexibility as compared to existing part grouping models.     

A simulation analysis of sequencing rules in a flexible flowline

The paper concerns a flexible flowline scheduling problem, which arises in the footwear industry. Flexibility of the line allows for manufacturing simultaneously more products in lower quantities, but it also increases the complexity of the task of balancing the line, specially because the mix of products changes everyday. A simulation model to deal with the flexible line is developed and several job sequencing rules and different part input criteria are implemented. The impact of each rule on the quality of the schedules is measured, namely, according to makespan, productivity and average machine utilisation. Computational results concerning a real application are also presented. SIMPLE++ is the simulation language used.     

Optimal makespan schedule for three jobs on two machines

This paper deals with the problem of scheduling three jobs on two machines in order to minimize the makespan, when operation preemptions are forbidden and routes are fixed and may vary per job. It is shown that this problem can be solved by anO(r ⁴) algorithm, wherer is the maximal number of operations per job. Supported by Belarussian Fundamental Research Found, Project Φ60–242, and Deutsche Forschungsgemeinschaft, Project ScheMA     

A hybrid imperialist competitive algorithm for minimizing makespan in a multi-processor open shop

In this paper a new mixed-integer linear programming (MILP) model is proposed for the multi-processor open shop scheduling (MPOS) problems to minimize the makespan with considering independent setup time and sequence dependent removal time. A hybrid imperialist competitive algorithm (ICA) with genetic algorithm (GA) is presented to solve this problem. The parameters of the proposed algorithm are tuned by response surface methodology (RSM). The performance of the algorithm to solve small, medium and large sized instances of the problem is evaluated by introducing two performance metrics. The quality of obtained solutions is compared with that of the optimal solutions for small sized instances and with the lower bounds for medium sized instances. Also some computational results are presented for large sized instances.     

An effective heuristic for minimising makespan on unrelated parallel machines

Scheduling independent tasks on unrelated machines is a relatively difficult and challenging problem. In this paper, we develop a tabu search based heuristic for minimising makespan for the above problem that can provide good quality solutions for practical size problems within a reasonable amount of computational time. Our adaptation of this tabu search uses hashing to control the tabu restrictions of the search process and requires fewer critical parameters than many of the common tabu search approaches employed for combinatorial optimisation. Hashing is simple to implement and very effective in providing a near-optimal solution. Computational results are presented to demonstrate the effectiveness of the proposed heuristic.     

Analysis and design of sequencing rules for car sequencing

This paper presents novel approaches for generating sequencing rules for the car sequencing (CS) problem in cases of two and multiple processing times per station. The CS problem decides on the succession of different car models launched down a mixed-model assembly line. It aims to avoid work overloads at the stations of the line by applying so-called sequencing rules, which restrict the maximum occurrence of labor-intensive options in a subsequence of a certain length. Thus to successfully avoid work overloads, suitable sequencing rules are essential. The paper shows that the only existing rule generation approach leads to sequencing rules which misclassify feasible sequences. We present a novel procedure which overcomes this drawback by generating multiple sequencing rules. Then, it is shown how to apply both procedures in case of multiple processing times per station. For both cases analytical and empirical results are derived to compare classification quality.     

List scheduling algorithms to minimize the makespan on identical parallel machines

In this paper we present constructive algorithms for the classical deterministic scheduling problem of minimizing the makespan on identical machines. Since the problem is known to beNP-hard in the strong sense, the approximate algorithms play a relevant role when solving this problem. The proposed algorithms are based on list scheduling procedures, but the assignment rule is not the same for the full set of jobs. Computational results show that these algorithms perform very well. This research has been partially supported by the Research Project H015/2000, Universidad de Alcalá. The authors are indebted to Joaquín Pérez and the referees for their helpful remarks and comments. We also wish to thank Paul Alexander Ayres for his help in the correct use of English.     

On minimizing resource consumption with constraints on the makespan and the total completion time

We investigate a single machine scheduling problem where the resource consumed depends on the release times of jobs. The objective is to minimize the total consumption subject to a constraint on the makespan or the total completion time. Results by Li are extended to the case where the consumption function is convex decreasing. A further extension to multiple consumption functions is shown. Conditions for feasibility are developed in each case.     

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.     

An approach to solve the minimum expected makespan flow-shop problem subject to breakdowns

Daily, there are multiple situations where machines or workers must execute certain jobs. During a working day it may be that some workers or machines are not available to perform their activities during some time periods. When scheduling models are used in these situations, workers or machines are simply called “machines”, and the temporal absences of availability are known as “breakdowns”. This paper considers some of these cases studying stochastic scheduling models with several machines to perform activities. Machines are specialized and models are flow-shops where breakdowns are allowed. The paper proposes a general procedure that tries to solve these problems. The proposed approach converts breakdowns scheduling problems into a finite sequence of without-breakdowns problems. Thus, we consider random variables, which measure the length of availability periods and repair times, to study availability intervals of machines. We propose partial feasible schedules in these intervals and combine them to offer a final global solution to optimize the expected makespan. Computational experiences are also reported.     

A branch and bound algorithm for minimizing the expected cost of testing coherent systems

We are interested in the problem of minimizing the expected cost of testing a coherent system. The concept of the Importance of Components is used to develop a branch and bound algorithm which determines the optimal testing policy for any coherent system.     

Drop out monotonic rules for sequencing situations

This note introduces a new monotonicity property for sequencing situations. A sequencing rule is called drop out monotonic if no player will be worse off whenever one of the players decides to drop out of the queue before processing starts. This intuitively appealing property turns out to be very strong: we show that there is at most one rule satisfying both stability and drop out monotonicity. For the standard model of linear cost functions, the existence of this rule is established.     

Minimizing makespan for two parallel machines with job limit on each availability interval

We consider the problem of scheduling jobs on two parallel machines that are not continuously available for processing. The machine is not available after processing a fixed number of jobs in order to make precision adjustment of machines such as in wafer manufacturing, to reload the feeder in printed circuit board production, or to undertake any other maintenance works such as cleaning and safety inspections. The objective of the problem is to minimize the makespan. Two different scheduling horizons are investigated for this problem. For the short-term scheduling horizon, we consider only the time period before the unavailability interval, while for the long-term horizon, machines are allowed to restart processing after the unavailability interval. For both cases, which are strongly NP-hard, exact optimization algorithms based on the branch and bound method are proposed. Although the algorithms have exponential time complexities, computational results show that they can solve optimally the various-sized problems in reasonable computation time.