Group shops scheduling with makespan criterion subject to random release dates and processing times

This paper deals with a stochastic group shop scheduling problem. The group shop scheduling problem is a general formulation that includes the other shop scheduling problems such as the flow shop, the job shop and the open shop scheduling problems. Both the release date of each job and the processing time of each job on each machine are random variables with known distributions. The objective is to find a job schedule which minimizes the expected makespan. First, the problem is formulated in a form of stochastic programming and then a lower bound on the expected makespan is proposed which may be used as a measure for evaluating the performance of a solution without simulating. To solve the stochastic problem efficiently, a simulation optimization approach is developed that is a hybrid of an ant colony optimization algorithm and a heuristic algorithm to generate good solutions and a discrete event simulation model to evaluate the expected makespan. The proposed approach is tested on instances where the random variables are normally, exponentially or uniformly distributed and gives promising results.     

An experimental analysis of local minima to improve neighbourhood search

The paper reports the results from a number of experiments on local search algorithms applied to job shop scheduling problems. The main aim was to get insights into the structure of the underlying configuration space. We consider the disjunctive graph representation where the objective function of job shop scheduling is equal to the length of longest paths. In particular, we analyse the number of longest paths, and our computational experiments on benchmark problems provide evidence that in most cases optimal and near optimal solutions do have a small number of longest paths. For example, our best solutions have one to five longest paths only while the maximum number is about sixty longest paths. Based on this observation, we investigate a non-uniform neighbourhood for simulated annealing procedures that gives preference to transitions where a decrease of the number of longest paths is most likely. The results indicate that the non-uniform strategy performs better than uniform methods, i.e. the non-uniform approach has a potential to find better solutions within the same number of transition steps. For example, we obtain the new upper bound 886 on the 20×20 benchmark problem YN1.

Scope and purpose

The paper reports a number of experiments with local search algorithms applied to job shop scheduling (JSS). The JSS problem is defined as follows: Given a number of l jobs, the jobs have to be processed on m machines. Each job consists of a sequence of m tasks, i.e., each task of a job is assigned to a particular machine. The tasks have to be processed during an uninterrupted time period of a fixed length on a given machine. A schedule is an allocation of the tasks to time intervals on the machines and the aim is to find a schedule that minimises the overall completion time which is called the makespan. The scheduling problem is one of the hardest combinatorial optimization problems (cf. M.R. Garey, D.S. Johnson, SIAM J. Comput. 4(4) (1975) 397. Many methods have been proposed to find good approximations of optimum solutions to job shop scheduling problems; for an overview (see E.H.L. Aarts, Local Search in Combinatorial Optimization, Wiley, New York, 1998). In our paper, the main aim is to get insights into the structure of the underlying configuration space. We consider the disjunctive graph representation where the objective function of job shop scheduling is equal to the length of longest paths. In particular, we analyse the number of longest paths, and our computational experiments on benchmark problems provide evidence that in most cases optimal and near optimal solutions do have a small number of longest paths. For example, our best solutions have one to five longest paths only while the maximum number is about sixty longest paths. Based on this observation, we investigate a non-uniform neighbourhood for simulated annealing procedures that gives preference to transitions where a decrease of the number of longest paths is most likely. The results indicate that the non-uniform strategy performs better than uniform methods, i.e., the non-uniform approach has a potential to find better solutions within the same number of transition steps. For example, we obtain the new upper bound 886 on the 20×20 benchmark problem YN1.     

Scheduling jobs under decreasing linear deterioration

This paper considers the scheduling problems under decreasing linear deterioration. Deterioration of a job means that its processing time is a function of its execution start time. Optimal algorithms are presented respectively for single machine scheduling of minimizing the makespan, maximum lateness, maximum cost and number of late jobs. For two-machine flow shop scheduling problem to minimize the makespan, it is proved that the optimal schedule can be obtained by Johnson's rule. If the processing times of operations are equal for each job, flow shop scheduling problems can be transformed into single machine scheduling problems.     

Flow shop scheduling with multiple operations and time lags

A scheduling system is proposed and developed for a special type of flow shop. In this flow shop there is one machine at each stage. A job may require multiple operations at each stage. The first operation of a job on stage j cannot start until the last operation of the job on stage j - 1 has finished. Pre-emption of the operations of a job is not allowed. The flow shop that the authors consider has another feature, namely time lags between the multiple operations of a job. To move from one operation of a job to another requires a finite amount of time. This time lag is independent of the sequence and need not be the same for all operations or jobs. During a time lag of a job, operations of other jobs may be processed. This problem originates from a flexible manufacturing system scheduling problem where, between operations of a job on the same workstation, refixturing of the parts has to take place in a load/unload station, accompanied by (manual) transportation activities. In this paper a scheduling system is proposed in which the inherent structure of this flow shop is used in the formulation of lowerbounds on the makespan. A number of lowerbounds are developed and discussed. The use of these bounds makes it possible to generate a schedule that minimizes makespan or to construct approximate solutions. Finally, some heuristic procedures for this type of flow shop are proposed and compared with some well-known heuristic scheduling rules for job shop/flow shop scheduling.An earlier version of this paper was presented at the First International Conference on Industrial Engineering and Production Management 1993, 2–4 June 1993, Mons, Belgium.     

具有线性恶化加工时间的调度问题

讨论了工件具有线性恶化加工时间的调度问题.在这类问题中,工件的恶化函数为线性函数.对单机调度问题中目标函数为极小化最大完工时间加权完工时间和,最大延误以及最大费用等问题分别给出了最优算法.对两台机器极小化最大完工时间的Flowshop问题,证明了利用Johnson规则可以得到最优调度.对于一般情况,如果同一工件的工序的加工时间均相等,则Flowshop问题可以转化为单机问题.     

相关工件车间调度问题的拓扑算法

针对加工装配型离散制造企业实际生产的特点,提出了一类用于表示工序之间偏序关系的相关工件车间调度问题。为了利用已有的求解表示工序之间的线序关系的传统车间调度算法求解相关工件车间调度问题,设计了一种拓扑算法,该算法能够将工序之间的偏序关系转化为线序关系,将相关工件车间调度问题转化为传统的车间调度问题,通过实证研究,结果表明了拓扑算法是可行和高效的。     

On the Complexity of Non-preemptive Shop Scheduling with Two Jobs

In this note, we investigate the time complexity of non-preemptive shop scheduling problems with two jobs. First we study mixed shop scheduling where one job has a fixed order of operations and the operations of the other job may be executed in arbitrary order. This problem is shown to be binary NP-complete with respect to all traditional optimality criteria even if distinct operations of the same job require different machines. Moreover, we devise a pseudo-polynomial time algorithm which solves the problem with respect to all non-decreasing objective functions. Finally, when the job with fixed order of operations may visit a machine more than once, the problem becomes unary NP-complete. Then we discuss shop scheduling with two jobs having chain-like routings. It is shown that the problem is unary NP-complete with respect to all traditional optimality criteria even if one of the jobs has fixed order of operations and the jobs cannot visit a machine twice. Received July 28, 2001; revised May 15, 2002 Published online: July 26, 2002     

Discrepancy search for the flexible job shop scheduling problem

The flexible job shop scheduling problem (FJSP) is a generalization of the classical job shop problem in which each operation must be processed on a given machine chosen among a finite subset of candidate machines. The aim is to find an allocation for each operation and to define the sequence of operations on each machine, so that the resulting schedule has a minimal completion time. We propose a variant of the climbing discrepancy search approach for solving this problem. We also present various neighborhood structures related to assignment and sequencing problems. We report the results of extensive computational experiments carried out on well-known benchmarks for flexible job shop scheduling. The results demonstrate that the proposed approach outperforms the best-known algorithms for the FJSP on some types of benchmarks and remains comparable with them on other ones.     

模糊Job Shop调度交货满意度模型研究

针对生产环境中调度参数的不确定性,研究含模糊加工时间和模糊交货期的Job Shop调度问题,用6点模糊数表示加工时间梯形模糊数表示交货期。基于隶属度定义工件交货满意度,以最大化平均工件交货满意度作为优化目标建立模糊调度数学模型。基于模糊截集概念设计稳定性指标评价优化方案的稳定性,最后通过仿真结果证明所设计模型能够获得稳定性较好的满意调度方案。     

Recurrent neural network approach for cyclic job shop scheduling problem

While cyclic scheduling is involved in numerous real-world applications, solving the derived problem is still of exponential complexity. This paper focuses specifically on modelling the manufacturing application as a cyclic job shop problem and we have developed an efficient neural network approach to minimise the cycle time of a schedule. Our approach introduces an interesting model for a manufacturing production, and it is also very efficient, adaptive and flexible enough to work with other techniques. Experimental results validated the approach and confirmed our hypotheses about the system model and the efficiency of neural networks for such a class of problems.     

Irreducible bin packing and normality in routing open shop

The open shop is a classical scheduling problem known since 1976, which can be described as follows. A number of jobs have to be processed by a given set of machines, each machine should perform an operation on every job, and the processing times of all the operations are given. One has to construct a schedule to perform all the operations to minimize finish time also known as the makespan. The open shop problem is known to be NP-hard for three and more machines, while is polynomially solvable in the case of two machines. We consider the routing open shop problem, being a generalization of both the open shop problem and the metric traveling salesman problem. In this setting, jobs are located at nodes of a transportation network and have to be processed by mobile machines, initially located at a predefined depot. Machines have to process all the jobs and return to the depot to minimize makespan. A feasible schedule is referred to as normal if its makespan coincides with the standard lower bound. We introduce the Irreducible Bin Packing decision problem, use it to describe new sufficient conditions of normality for the two machine problem, and discuss the possibility to extend these results on the problem with three and more machines. To that end, we present two new computer-aided optima localization results.

     

A heuristic for job shop scheduling to minimize total weighted tardiness

This paper considers the job shop scheduling problem to minimize the total weighted tardiness with job-specific due dates and delay penalties, and a heuristic algorithm based on the tree search procedure is developed for solving the problem. A certain job shop scheduling to minimize the maximum tardiness subject to fixed sub-schedules is solved at each node of the search tree, and the successor nodes are generated, where the sub-schedules of the operations are fixed. Thus, a schedule is obtained at each node, and the sub-optimum solution is determined among the obtained schedules. Computational results on some 10 jobs and 10 machines problems and 15 jobs and 15 machines problems show that the proposed algorithm can find the sub-optimum solutions with a little computation time.     

Job-shop scheduling in a body shop

We study a generalized job-shop problem called the body shop scheduling problem (BSSP). This problem arises from the industrial application of welding in a car body production line, where possible collisions between industrial robots have to be taken into account. BSSP corresponds to a job-shop problem where the operations of a job have to follow alternating routes on the machines, certain operations of different jobs are not allowed to be processed at the same time and after processing an operation of a certain job a machine might be unavailable for a given time for operations of other jobs. As main results we will show that for three jobs and four machines the special case where only one machine is used by more than one job is already $\mathcal NP $ -hard. This also implies that the single machine scheduling problem that asks for a makespan minimal schedule of three chains of operations with delays between the operations of a chain is $\mathcal NP $ -hard. On the positive side, we present a polynomial algorithm for the two job case and a pseudo-polynomial algorithm together with an FPTAS  for an arbitrary but constant number of jobs. Hence for a constant number of jobs we fully settle the complexity status of the problem.     

Dynamic non-preemptive single machine scheduling

Considering a dynamic single machine problem in which operations cannot be split, we first develop a decision theory based heuristic called DT-TD (Decision Theory-Tactically Delayed) of computational complexity O(n²). Using a simple look-ahead procedure, it produces, actically delayed (TD) schedules. We then develop a branch-and-bound (BB) algorithm (which uses DT-TD to obtain the initial upper bound) to obtain the optimum schedule. The optimum schedules are examined to identify conditions where TD schedules are necessary. Results based on 540 test problems suggest that TD schedules are important, for job shop scheduling under the range of conditions examined, when due dates are arbitrary and utilization is low. Additional test results indicate that the difference between the optimum schedule and the optimum non-delay schedule could be substantial. Finally, the performance of the DT-TD heuristic is analyzed by comparing its solution to the optimum solution obtained using the BB algorithm. The results indicate that the DT-TD heuristic is effective.     

A genetic algorithm for the proportionate multiprocessor open shop

The multiprocessor open shop (MPOS) scheduling problem is NP-complete, a category of hard combinatorial optimization problems that have not received much attention in the literature. In this work, a special MPOS—a proportionate one—is introduced for the first time. Two original mixed integer programming formulations for the proportionate MPOS are developed and their complexity is discussed. Due to the complexity of the MPOS, this paper develops a compu-search methodology (a genetic algorithm (GA)) to schedule the shop with the objective of minimizing the makespan. In this novel GA, a clever chromosome representation of a schedule is developed that succinctly encodes a schedule of jobs across multiple stages. The innovative design of this chromosome enables any permutation of its genes to yield a feasible solution. This simple representation of an otherwise very complex schedule enables the genetic operators of crossover and mutation to easily manipulate a schedule as the algorithm iteratively searches for better schedules. A testbed of difficult instances of the problem are created to evaluate the performance of the GA. The solution for each instance is compared with a derived lower bound. Computational results reveal that the algorithm performs extremely well, demonstrating its potential to efficiently schedule MPOS problems. More importantly, successful experiments on large-scale problem instances suggest the readiness of the GA for industrial use.     

A survey of scheduling with deterministic machine availability constraints

Various deterministic scheduling problems with availability constraints motivated by preventive maintenance attract more and more researchers. Many results involving this constraint have been published in recent years. But there is no recent paper to summarize them. To be convenient for interested researchers, we make this survey. In this paper, complexity results, exact algorithms and approximation algorithms in single machine, parallel machine, flow shop, open shop, job shop scheduling environment with different criteria are surveyed briefly.     

Fuzzy branch-and-bound algorithm for flow shop scheduling

Scheduling is the allocation of resources over time to perform a collection of task. It is an important subject of production and operations management area. For most of scheduling problems made so far, the processing times of each job on each machine and due dates have been assigned as a real number. However in the real world, information is often ambiguous or imprecise. In this paper fuzzy concept are applied to the flow shop scheduling problems. The branch-and-bound algorithm of Ignall and Schrage was modified and rewritten for three-machine flow shop problems with fuzzy processing time. Fuzzy arithmetic on fuzzy numbers is used to determine the minimum completion time (C _max). Proposed algorithm gets a scheduling result with a membership function for the final completion time. With this membership function determined, a wider point of view is provided for the manager about the optimal schedule.     

Neighbourhood generation mechanism applied in simulated annealing to job shop scheduling problems

This paper presents a neighbourhood generation mechanism for the job shop scheduling problems (JSSPs). In order to obtain a feasible neighbour with the generation mechanism, it is only necessary to generate a permutation of an adjacent pair of operations in a scheduling of the JSSP. If there is no slack time between the adjacent pair of operations that is permuted, then it is proven, through theory and experimentation, that the new neighbour (schedule) generated is feasible. It is demonstrated that the neighbourhood generation mechanism is very efficient and effective in a simulated annealing.     

Multi-objective flexible job shop schedule: Design and evaluation by simulation modeling

Flexible job shop schedule is very important in both fields of combinatorial optimization and production management. In this paper, a simulation model is presented to solve the multi-objective flexible job shop scheduling problem. The proposed model has been coded by Matlab which is a special mathematical computation language. After modeling the pending problem, the model is validated by five representative instances based on practical data. The results obtained from the computational study have shown that the proposed approach is a feasible and effective approach for the multi-objective flexible job shop scheduling problem.     

Open Shop Scheduling with Synchronization

In this paper, we study open shop scheduling problems with synchronization. This model has the same features as the classical open shop model, where each of the n jobs has to be processed by each of the m machines in an arbitrary order. Unlike the classical model, jobs are processed in synchronous cycles, which means that the m operations of the same cycle start at the same time. Within one cycle, machines which process operations with smaller processing times have to wait until the longest operation of the cycle is finished before the next cycle can start. Thus, the length of a cycle is equal to the maximum processing time of its operations. In this paper, we continue the line of research started by Weiß et al. (Discrete Appl Math 211:183–203, 2016). We establish new structural results for the two-machine problem with the makespan objective and use them to formulate an easier solution algorithm. Other versions of the problem, with the total completion time objective and those which involve due dates or deadlines, turn out to be NP-hard in the strong sense, even for \(m=2\) machines. We also show that relaxed models, in which cycles are allowed to contain less than m jobs, have the same complexity status.