Joint optimization of job scheduling and maintenance planning for a two-machine flow shop considering job-dependent operating condition

Two-machine flow shops are widely adopted in manufacturing systems. To minimize the makespan of a sequence of jobs, joint optimization of job scheduling and preventive maintenance (PM) planning has been extensively studied for such systems. In practice, the operating condition (OC) of the two machines usually varies from one job to another because of different processing covariates, which directly affects the machines’ failure rates, PM plans, and expected job completion times. This fact is common in many real systems, but it is often overlooked in the related literature. In this study, we propose a joint decision-making strategy for a two-machine flow shop with resumable jobs. The objective is to minimize the expected makespan by taking into account job-dependent OC. We consider two situations. In the first situation, where the failure rate of a machine under a fixed OC is constant, a hybrid processing time model is proposed to obtain the optimal job sequence based on the Johnson's law. For the second situation, where the failure rate of a machine is time-varying, the job sequence and PM plan are jointly optimized. An enumeration method is adopted to find the optimal job sequence and PM plan for a small-scale problem, and a genetic algorithm-based method is proposed to solve a large-scale problem. Numerical examples are provided to demonstrate the necessity of considering the effect of job-dependent OC and the effectiveness of the proposed method in handing such joint decision-making problems in manufacturing systems.     

A computer simulation model for job shop scheduling problems minimizing makespan

One of the basic and significant problems, that a shop or a factory manager is encountered, is a suitable scheduling and sequencing of jobs on machines. One type of scheduling problem is job shop scheduling. There are different machines in a shop of which a job may require some or all these machines in some specific sequence. For solving this problem, the objective may be to minimize the makespan. After optimizing the makespan, the jobs sequencing must be carried out for each machine. The above problem can be solved by a number of different methods such as branch and bound, cutting plane, heuristic methods, etc. In recent years, researches have used genetic algorithms, simulated annealing, and machine learning methods for solving such problems. In this paper, a simulation model is presented to work out job shop scheduling problems with the objective of minimizing makespan. The model has been coded by Visual SLAM which is a special simulation language. The structure of this language is based on the network modeling. After modeling the scheduling problem, the model is verified and validated. Then the computational results are presented and compared with other results reported in the literature. Finally, the model output is analyzed.     

Service Time Optimization of Mixed-Line Flow Shop Systems

We consider deterministic mixed-line flow shop systems that are composed of controllable and uncontrollable machines. Arrival times and completion deadlines of jobs are assumed to be known, and they are processed in the order they arrive at the machines. We model these flow shops as serial networks of queues operating under a non-preemptive first-come-first-served policy, and employ max-plus algebra to characterize the system dynamics. Defining completion-time costs for jobs and service costs at controllable machines, a non-convex optimization problem is formulated where the control variables are the constrained service times at the controllable machines. In order to simplify this optimization problem, under some cost assumptions, we show that no waiting is observed on the optimal sample path at the downstream of the first controllable machine. We also present a method to decompose the optimization problem into convex subproblems. A solution algorithm utilizing these findings is proposed, and a numerical study is presented to evaluate the performance improvement due to this algorithm.      

Reliability evaluation of a multistate flexible flow shop with stochastic capacity for multiple types of jobs

A flexible flow shop (FFS) is a general manufacturing system that has been studied by numerous researchers. Owing to maintenance, partial failure, the possibility of failure, unexpected situations, etc., the number of functioning machines in a stage should be represented by multiple levels. It is appropriate to regard the capacity in each stage (i.e., the number of machines in a stage) as stochastic. Unlike the previous research, which dealt with the FFS problems under the assumption of the fixed capacity, this paper extends the deterministic capacity to the stochastic case in every stage. The FFS with stochastic capacity is modeled as a multistate flexible flow shop network (MFFSN), where each edge denotes a stage with stochastic capacity and each node denotes a buffer. The addressed problem is to evaluate network reliability, the probability that the MFFSN can complete a customer's order composed of multiple types of jobs within a time threshold. An efficient algorithm integrating a systematic branch-and-bound approach is proposed to obtain the lower boundary vectors, in terms of a pair of capacity vectors generated from two estimated demand vectors. Two practical cases, a tile production system and an apparel manufacturing system, are presented to demonstrate the proposed algorithm and to discuss the changes in network reliability within different time thresholds, respectively.     

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     

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.

     

Solution algorithms for synchronous flow shop problems with two dominating machines

In this paper, we present solution algorithms for synchronous flow shop problems with two dominating machines. In such an environment, jobs have to be moved from one machine to the next by an unpaced synchronous transportation system, which implies that the processing is organized in synchronized cycles. This means that in each cycle the current jobs start at the same time on the corresponding machines and after processing have to wait until the last job is finished. Afterwards, all jobs are moved to the next machine simultaneously. Motivated by a practical application, we investigate the special case of two dominating machines where the processing times of all jobs on these two machines are at least as large as the processing times of all jobs on the other machines and hence always determine the cycle times. After formulating the considered problem as a special vehicle routing problem, we propose mixed integer linear programming formulations and a tabu search algorithm. Finally, we present computational results for randomly generated data and show the efficiency of the approaches.     

A genetic algorithm-based scheduler for multiproduct parallel machine sheet metal job shop

This paper presents a genetic algorithm-based job-shop scheduler for a flexible multi-product, parallel machine sheet metal job shop. Most of the existing research has focused only on permutation job shops in which the manufacturing sequence and routings are strictly in a predefined order. This effectively meant that only the jobs shops with little or no flexibility could be modeled using these models. The real life job shops may have flexibility of routing and sequencing. Our paper proposes one such model where variable sequences and multiple routings are possible. Another limitation of the existing literature was found to be negligence of the setup times. In many job shops like sheet metal shops, setup time may be a very sizable portion of the total make-span of the jobs, hence setup times will be considered in this work. One more flexibility type arises as a direct consequence of the routing flexibility. When there are multiple machines (parallel machines) to perform the same operation, the job could be routed to one or more of these machines to reduce the make-span. This is possible in situations where each job consists of a pre-defined quantity of a specified product. In other words, same job is quantity-wise split into two or more parts whenever it reduces the makespan. This effectively assumes that the setup cost is negligible. This model has been implemented on a real-life industry problem using VB.Net programming language. The results from the scheduler are found to be better than those obtained by simple sequencing rules.     

Scheduling two-stage hybrid flow shops with parallel batch, release time, and machine eligibility constraints

This paper investigates a difficult scheduling problem on a specialized two-stage hybrid flow shop with multiple processors that appears in semiconductor manufacturing industry, where the first and second stages process serial jobs and parallel batches, respectively. The objective is to seek job-machine, job-batch, and batch-machine assignments such that makespan is minimized, while considering parallel batch, release time, and machine eligibility constraints. We first propose a mixed integer programming (MIP) formulation for this problem, then gives a heuristic approach for solving larger problems. In order to handle real world large-scale scheduling problems, we propose an efficient dispatching rule called BFIFO that assigns jobs or batches to machines based on first-in-first-out principle, and then give several reoptimization techniques using MIP and local search heuristics involving interchange, translocation and transposition among assigned jobs. Computational experiments indicate our proposed re-optimization techniques are efficient. In particular, our approaches can produce good solutions for scheduling up to 160 jobs on 40 machines at both stages within 10?min.     

恒速处理机的多机Flow shop最小和调度问题的启发式算法分析

本文研究有n个作业需在5个处理机中心进行加工，处理机中心i由l1个恒速机组成的非抢占式多机flow shop调度最小和问题．每个作业有s个工序，每个工序需在对应的处理机中心的任一台机器上加工处理，作业到达前不能加工，所有作业通过处理机中心的路径相同．目标是确定一个作业在每个处理机中心机器上的可行调度序列，使所有作业在最后处理机中心的加权完成时间总和最小化．在作业处理时间需求、作业权重分别为独立同分布的有界随机变量时，通过特殊flow shop调度松弛方法，我们证明该问题在作业数趋于无穷时，一个基于有效作业最短加权平均处理时间需求的启发式算法是渐近最优的．     

Receding Horizon Control of Mixed Line Flow Shop Systems

We consider reliable mixed line flow shop systems that are composed of controllable and uncontrollable machines. These systems are assumed to receive arrivals at random instants and process jobs deterministically in the order of arrival so as to depart them before their deadlines that are revealed at the time of arrival. We model these flow shops as serial networks of queues operating under a non-preemptive first-come-first-served policy. Defining completion-time costs for jobs and process costs at controllable machines, a stochastic convex optimization problem is formulated where the control variables are the constrained service times of jobs at the controllable machines. As an on-line solution method to determine these service times, we propose a receding horizon controller, which solves a deterministic problem at each decision instant. We quantify the available future information by the look-ahead window size. Numerical examples demonstrate the value of information and that the no-waiting property of the full-information case is not observed in the partial-information case.     

Production sequencing problem with reentrant work flows and sequence dependent setup times

This paper addresses a shop scheduling problem for the side frame press shop in a truck manufacturing company. In the problem, a set of n jobs to be scheduled on two machines. All the jobs require processing by the first machine more than once in their operation sequences with reentrant work flows. An unusual aspect of the problem is that the setup times required for a job in the first machine depend not on the immediately preceding job but on the job which is two steps prior to it. Redefining the job elements, the problem is formulated into a general two machine flow shop problem which has a set of job-element precedence constraints. The problem is solved with a modified dynamic programming with the objective of the minimum makespan. An optimal schedule is found utilizing the sequence dominance condition and a decision-delay scheme. A numerical example is presented for the illustration purpose.     

Scheduling of manufacturing systems using the Lagrangian relaxationtechnique

The practical solutions for three manufacturing scheduling problems are examined. As each problem is formulated, constraints are added or modified to reflect increasing real world complexity. The first problem considers scheduling single-operation jobs on identical machines. The second problem is concerned with scheduling multiple-operation jobs with simple fork/join precedence constraints on identical machines. The third problem is the job shop problem in which multiple-operation jobs with general precedence constraints are scheduled on multiple machine types Langrangian relaxation is used to decompose each of the scheduling problems into job- or operation-level subproblems. The subproblems are easier to solve than the original problem and have intuitive appeal. This technique results in algorithms which generate near-optimal schedules efficiently, while giving a lower bound on the optimal cost. In resolving the scheduling problem from one time instant to the next, the Lagrange multipliers from the last schedule can be used to initialize the multipliers, further reducing the computation time     

An interactive micro-computer software for general three machines flow shop sequencing problems

The order in which jobs pass through machines or work centres is a sequencing problem. The sequencing problems occur in flow shop as well as job shop production systems. In flow shop production systems, each job follows the same processing route whereas in the job shop production system, jobs flow across machines or work stations on many different routes. For optimizing the sequencing of such jobs, production planners may adopt different criteria such as makespan time, average completion time, due date performance, machine utilization and so forth. In the absence of given criteria, it is usual to accept the makespan time as the criteria and to attempt to minimize this. In a 2-machines flow shop, the jobs can be sequenced optimally for minimum total makespan time by using Johnson's algorithm [1]. Johnson's algorithm can also be used to find the optimal sequence for special three-machines flow shop problems satisfying certain conditions [1]. But for general three-machines sequencing problems, optimal sequence based on makespan time can be obtained by using a branch and bound solution procedure [1].

In this paper, the branch-and-bound procedure have been used to develop an interactive program in BASIC for finding the optimal job sequence for general three-machines flow shop problems. This program which is written for an IBM-PC or IBM-PC compatibles, also provides the time chart and the time chart drawing. Furthermore, it gives the results of the branching steps (i.e the partial sequences) in a tabular form.     

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.     

The total completion time open shop scheduling problem with a given sequence of jobs on one machine

This paper addresses the open shop scheduling problem to minimize the total completion time, provided that one of the machines has to process the jobs in a given sequence. The problem is NP-hard in the strong sense even for the two-machine case. A lower bound is derived based on the optimal solution of a relaxed problem in which the operations on every machine may overlap except for the machine with a given sequence of jobs. This relaxed problem is NP-hard in the ordinary sense, however it can be quickly solved via a decomposition into subset-sum problems. Both heuristic and branch-and-bound algorithm are proposed. Experimental results show that the heuristic is efficient for solving large-scaled problems, and the branch-and-bound algorithm performs well on small-scaled problems.Scope and purposeShop scheduling problems, widely used in the modeling of industrial production processes, are receiving an increasing amount of attention from researchers. To model practical production processes more closely, additional processing restrictions can be introduced, e.g., the resource constraints, the no-wait in process requirement, the precedence constraints, etc. This paper considers the total completion time open shop scheduling problem with a given sequence of jobs on one machine. This model belongs to a new class of shop scheduling problems under machine-dependent precedence constraints. This problem is NP-hard in the strong sense. A heuristic is proposed to efficiently solve large-scaled problems and a branch-and-bound algorithm is presented to optimally solve small-scaled problems. Computational experience is also reported.     

An operator load-balancing problem in a semi-automatic parallel machine shop

This paper deals with a load-balancing problem among several operators in a semi-automatic parallel machine shop in which two types of machine are operated. The objective is to assign jobs to the proper machines and allocate machines to operators in order to minimize the unbalance of the workloads among operators under the constraints of available machine- and operator-time. There are two types of parallel machines and jobs are classified into the two types. However, operator can handle machines of both types.Although, this situation can be formulated with non-linear integer programming, it is difficult to solve this program. Therefore, a hierarchical heuristic solution procedure is suggested and the performance of the algorithm is evaluated with various data.     

A new Lagrangian Relaxation Algorithm for scheduling dissimilar parallel machines with release dates

In this article we investigate the parallel machine scheduling problem with job release dates, focusing on the case that machines are dissimilar with each other. The goal of scheduling is to find an assignment and sequence for a set of jobs so that the total weighted completion time is minimised. This type of production environment is frequently encountered in process industry, such as chemical and steel industries, where the scheduling of jobs with different purposes is an important goal. This article formulates the problem as an integer linear programming model. Because of the dissimilarity of machines, the ordinary job-based decomposition method is no longer applicable, a novel machine-based Lagrangian relaxation algorithm is therefore proposed. Penalty terms associated with violations of coupling constraints are introduced to the objective function by Lagrangian multipliers, which are updated using subgradient optimisation method. For each machine-level subproblem after decomposition, a forward dynamic programming algorithm is designed together with the weighted shortest processing time rule to provide an optimal solution. A heuristics is developed to obtain a feasible schedule from the solution of subproblems to provide an upper bound. Numerical results show that the new approach is computationally effective to handle the addressed problem and provide high quality schedules.     

A genetic algorithm based heuristic for scheduling of virtual manufacturing cells (VMCs)

We present a genetic algorithm (GA) based heuristic approach for job scheduling in virtual manufacturing cells (VMCs). In a VMC, machines are dedicated to a part as in a regular cell, but machines are not physically relocated in a contiguous area. Cell configurations are therefore temporary, and assignments are made to optimize the scheduling objective under changing demand conditions. We consider the case where there are multiple jobs with different processing routes. There are multiple machine types with several identical machines in each type and are located in different locations in the shop floor. Scheduling objective is weighted makespan and total traveling distance minimization. The scheduling decisions are the (i) assignment of jobs to the machines, and (ii) the job start time at each machine. To evaluate the effectiveness of the GA heuristic we compare it with a mixed integer programming (MIP) solution. This is done on a wide range of benchmark problem. Computational results show that GA is promising in finding good solutions in very shorter times and can be substituted in the place of MIP model.     

A heuristic procedure for makespan minimization in job shops with multiple identical processors

Scheduling has been and continues to be a major issue in production planning. Job shop scheduling is one area where a considerable amount of research has been and continues to be pursued. Usual emphasis is on one machine per work center job shop scheduling. There appears to be very limited literature available on scheduling a job shop problem which requires scheduling of n jobs in m machine centers where each machine center may have k number of identical processors (though the number of identical processors may vary from one machine center to next). We discuss here, the problem of minimize of the makespan for such a job shop arrangement The problem can be represented by the symbol m x n x k.