Efficient approximation algorithms for the routing open shop problem

We consider the routing open shop problem being a generalization of two classical discrete optimization problems: the open shop scheduling problem and the metric traveling salesman problem. The jobs are located at nodes of some transportation network, and the machines travel on the network to execute the jobs in the open shop environment. The machines are initially located at the same node (depot) and must return to the depot after completing all the jobs. It is required to find a non-preemptive schedule with the minimum makespan. The problem is NP-hard even on the two-node network with two machines. We present new polynomial-time approximation algorithms with worst-case performance guarantees.     

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.     

多机器总完成时间和makespan近似最优的开放式车间调度方法

研究了多机器开放式车间调度问题,采用离散事件系统调度使makespan最小化和总完成时间最小.给出了在确定处理机器的条件下,不同批次的作业总完成时间最优的排序定理,以及选择机器处理作业的指标优化定理,利用给出的若干定理建立了总完成时间最优的调度方法.作者利用加权总完成时间最优算法来近似求解makespan最小化和总完成时间最优的调度问题.作者也利用论文的理论结果给出了一个三机器开放式车间情况的实际算例.     

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.     

Ant colony optimization for multi-objective flow shop scheduling problem

Flow shop scheduling problem consists of scheduling given jobs with same order at all machines. The job can be processed on at most one machine; meanwhile one machine can process at most one job. The most common objective for this problem is makespan. However, multi-objective approach for scheduling to reduce the total scheduling cost is important. Hence, in this study, we consider the flow shop scheduling problem with multi-objectives of makespan, total flow time and total machine idle time. Ant colony optimization (ACO) algorithm is proposed to solve this problem which is known as NP-hard type. The proposed algorithm is compared with solution performance obtained by the existing multi-objective heuristics. As a result, computational results show that proposed algorithm is more effective and better than other methods compared.     

Series production in a basic re-entrant shop to minimize makespan or total flow time

This paper addresses a real life shop scheduling problem in a manufacturing company. In this problem, a set of n identical jobs are to be processed on two machines. Every job visits one of the machines more than once. This is therefore a re-entrant shop. Due to the fact that the jobs are identical, the decision version of this problem is even not in the class NP. We give an optimal schedule to minimize the makespan. Since the total flow time depends on the relations between the processing times, we decompose this problem into sub-problems according to the relations between the processing times. We prove various properties of optimal solutions and, based on these properties, we provide an optimal solution for all the sub-problems except one of them. For the sole remaining sub-problem, we prove a dominance property which allows to consider a part of schedules to find an optimal one.     

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.     

Preemptive online scheduling with rejection of unit jobs on two uniformly related machines

We consider preemptive online and semi-online scheduling of unit jobs on two uniformly related machines. Jobs are presented one by one to an algorithm, and each job has a rejection penalty associated with it. A new job can either be rejected, in which case the algorithm pays its rejection penalty, or it can be scheduled preemptively on the machines, in which case it may increase the maximum completion time of any machine in the schedule, also known as the makespan of the constructed schedule. The objective is to minimize the sum of the makespan of the schedule of all accepted jobs and the total penalty of all rejected jobs. We study two versions of the problem. The first one is the online problem where the jobs arrive unsorted, and the second variant is the semi-online case, where the jobs arrive sorted by a non-increasing order of penalties. We also show that the variant where the jobs arrive sorted by a non-decreasing order of penalties is equivalent to the unsorted one. We design optimal online algorithms for both cases. These algorithms have smaller competitive ratios than the optimal competitive ratio for the more general problem with arbitrary processing times (except for the case of identical machines), but larger competitive ratios than the optimal competitive ratio for preemptive scheduling of unit jobs without rejection.     

Bounded parallel-batching scheduling with two competing agents

We consider a scheduling problem in which two agents, each with a set of non-preemptive jobs, compete to perform their jobs on a common bounded parallel-batching machine. Each of the agents wants to minimize an objective function that depends on the completion times of its own jobs. The goal is to schedule the jobs such that the overall schedule performs well with respect to the objective functions of both agents. We focus on minimizing the makespan or the total completion time of one agent, subject to an upper bound on the makespan of the other agent. We distinguish two categories of batch processing according to the compatibility of the agents. In the case where the agents are incompatible, their jobs cannot be processed in the same batch, whereas all the jobs can be processed in the same batch when the agents are compatible. We show that the makespan problem can be solved in polynomial time for the incompatible case and is NP-hard in the ordinary sense for the compatible case. Furthermore, we show that the latter admits a fully polynomial-time approximation scheme. We prove that the total completion time problem is NP-hard and is polynomially solvable for the incompatible case with a fixed number of job types.     

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

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

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

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

A Stronger Complexity Result for the Single Machine Multi-Operation Jobs Scheduling Problem to Minimize the Number of Tardy Jobs

We consider the single machine multi-operation jobs scheduling problem to minimize the number of tardy jobs. Each job consists of several operations that belong to different families. In a schedule, each family of job operations may be processed in batches with each batch incurring a setup time. A job completes when all of its operations have been processed. The objective is to minimize the number of tardy jobs. In the literature, this problem has been proved to be strongly NP-hard for arbitrary due-dates. We show in this paper that the problem remains strongly NP-hard even when the due-dates are common and all jobs have the same processing time.     

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.     

A simulated annealing algorithm approach to hybrid flow shop scheduling with sequence-dependent setup times

One of the scheduling problems with various applications in industries is hybrid flow shop. In hybrid flow shop, a series of n jobs are processed at a series of g workshops with several parallel machines in each workshop. To simplify the model construction in most research on hybrid flow shop scheduling problems, the setup times of operations have been ignored, combined with their corresponding processing times, or considered non sequence-dependent. However, in most real industries such as chemical, textile, metallurgical, printed circuit board, and automobile manufacturing, hybrid flow shop problems have sequence-dependent setup times (SDST). In this research, the problem of SDST hybrid flow shop scheduling with parallel identical machines to minimize the makespan is studied. A novel simulated annealing (NSA) algorithm is developed to produce a reasonable manufacturing schedule within an acceptable computational time. In this study, the proposed NSA uses a well combination of two moving operators for generating new solutions. The obtained results are compared with those computed by Random Key Genetic Algorithm (RKGA) and Immune Algorithm (IA) which are proposed previously. The results show that NSA outperforms both RKGA and IA.     

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.     

Minimizing the makespan on a batch machine with non-identical job sizes: an exact procedure

A batch processing machine can simultaneously process several jobs forming a batch. This paper considers the problem of scheduling jobs with non-identical capacity requirements, on a single-batch processing machine of a given capacity, to minimize the makespan. The processing time of a batch is equal to the largest processing time of any job in the batch. We present some dominance properties for a general enumeration scheme and for the makespan criterion, and provide a branch and bound method. For large-scale problems, we use this enumeration scheme as a heuristic method.Scope and purposeUsually in classical scheduling problems, a machine can perform only one job at a time. Although, one can find machines that can process several jobs simultaneously as a batch. All jobs of a same batch have common starting and ending times. Batch processing machines are encountered in many different environments, such as burn-in operations in semiconductor industries or heat treatment operations in metalworking industries. In the first case, the capacity of the machine is defined by the number of jobs it can hold. In the second case, each job has a certain capacity requirement and the total size of a batch cannot exceed the capacity of the machine. Hence, the number of jobs contained in each batch may be different. In this paper, we consider this second case (which is more difficult) and we provide an exact method for the makespan criterion (minimizing the last ending time).     

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.     

Branch-and-bound and PSO algorithms for no-wait job shop scheduling

This paper deals with the no-wait job shop scheduling problem resolution. The problem is to find a schedule to minimize the makespan (\(C_{max}\)), that is, the total completeness time of all jobs. The no-wait constraint occurs when two consecutive operations in a job must be processed without any waiting time either on or between machines. For this, we have proposed two different resolution methods, the first is an exact method based on the branch-and-bound algorithm, in which we have defined a new technique of branching. The second is a particular swarm optimization (PSO) algorithm, extended from the discrete version of PSO. In the proposed algorithm, we have defined the particle and the velocity structures, and an efficient approach is developed to move a particle to the new position. Moreover, we have adapted the timetabling procedure to find a good solution while respecting the no-wait constraint. Using the PSO method, we have reached good results compared to those in the literature.     

A heuristic method for two-stage hybrid flow shop with dedicated machines

This paper considers a two-stage hybrid flow shop scheduling problem with dedicated machines, in which the first stage contains a single common critical machine, and the second stage contains several dedicated machines. Each job must be first processed on the critical machine in stage one and depending on the job type, the job will be further processed on the dedicated machine of its type in stage two. The objective is to minimize the makespan. To solve the problem, a heuristic method based on branch and bound (B&B) algorithm is proposed. Several lower bounds are derived and four constructive heuristics are used to obtain initial upper bounds. Then, three dominance properties are employed to enhance the performance of the proposed heuristic method. Extensive computational experiments on two different problem categories each with various problem configurations are conducted. The results show that the proposed heuristic method can produce very close-to-optimal schedules for problems up to 100 jobs and five dedicated machines within 60 s. The comparisons with solutions of two other meta-heuristic methods also prove the better performance of the proposed heuristic method.     

Preemptive scheduling on uniformly related machines: minimizing the sum of the largest pair of job completion times

We revisit the classic problem of preemptive scheduling on m uniformly related machines. In this problem, jobs can be arbitrarily split into parts, under the constraint that every job is processed completely, and that the parts of a job are not assigned to run in parallel on different machines. We study a new objective which is motivated by fairness, where the goal is to minimize the sum of the two maximal job completion times. We design a polynomial time algorithm for computing an optimal solution. The algorithm can act on any set of machine speeds and any set of input jobs. The algorithm has several cases, many of which are very different from algorithms for makespan minimization (algorithms that minimize the maximum completion time of any job), and from algorithms that minimize the total completion time of all jobs.