订单带多类工件时的最大迟后问题

本文考虑多工类工件的单机排序问题,每一客户提供一由若干工件组成的订单,总共n个工件又分成k个类,当机器从加工某类中的工件转向加工不同于它的第i类工件时需一调整时间S_i,每一订单有一给定的应交工时间,所考虑目标函数是使订单的最大迟后最小,相应这一排序问题的三种模式,文中分别给出了一多项式算法,分枝定界算法和动态规划解法。     

On a New Class of Parallel Sequencing Situations and Related Games

This paper considers a special class of sequencing situations with two parallel machines in which each agent has precisely two jobs to be processed, one on each machine. The costs of an agent depend linearly on the final completion time of his jobs. We describe a procedure that provides an optimal processing order of the jobs for some particular classes. Furthermore, we study cooperative games arising from these sequencing situations. Our main result will be on the balancedness of these games.     

On the convexity of step out–step in sequencing games

The main result of this paper is the convexity of step out–step in (SoSi) sequencing games, a class of relaxed sequencing games first analyzed by Musegaas et al. (Eur J Oper Res 246:894–906, 2015). The proof makes use of a polynomial time algorithm determining the value and an optimal processing order for an arbitrary coalition in a SoSi sequencing game. In particular, we use that in determining an optimal processing order of a coalition, the algorithm can start from the optimal processing order found for any subcoalition of smaller size and thus all information on such an optimal processing order can be used.     

公共交货期窗口的提前／延期惩罚

本讨论n个独立工件在一台机器上加工,而且加工时间服从正态分布的公共交货期窗口的提前/延期惩罚问题,在确定公共交货期窗口情况下,推导出工件的最优排序具有V型特征。     

An approximation algorithm for the m-machine permutation flow shop scheduling problem with controllable processing times

The paper deals with the m-machine permutation flow shop scheduling problem in which job processing times, along with a processing order, are decision variables. It is assumed that the cost of processing a job on each machine is a linear function of its processing time and the overall schedule cost to be minimized is the total processing cost plus maximum completion time cost. A algorithm for the problem with m = 2 is provided; the best approximation algorithm until now has a worst-case performance ratio equal to . An extension to the m-machine (m ≥2) permutation flow shop problem yields an approximation algorithm with a worst-case bound equal to

Full-size image

, where is the worst-case performance ratio of a procedure used, in the proposed algorithm, for solving the (pure) sequencing problem. Moreover, examples which achieve this bound for = 1 are also presented.     

求带释放时间的半导体煅烧排序的最短交付时间的一个高效PTAS

本文研究一个目标是最小化最大交付时间的能分批处理的非中断单机排序问题．这个问题来源于半导体制造过程中对芯片煅烧工序的排序．煅烧炉可以看成一个能同时最多加工B（〈n）个工件的处理机．此外，每个工件有一个可以允许其加工的释放时间和一个完成加工后的额外交付时间．该问题就是将工件分批后再依批次的排序加工，使得所有工件都交付后所需的时间最短．我们设计了一个用时O（f（l／ε）n^5/2）的多项式时间近似方案，其中关于1／ε的指数函数厂（1／ε）对固定的ε是个常数.     

Optimal Assignment of Total-work-content Due-dates and Sequencing in a Single-machine Shop

This paper considers the problem of optimal assignment of total-work-content due-dates to n jobs and of sequencing them on a single machine to minimize an objective function depending on the assigned due-date multiple value and maximum tardiness penalty. It is shown that both the earliest due-date and shortest processing time orders yield an optimal sequence. A simple analytical solution method is presented to find the optimal due-dates. After the theoretical treatment an illustrative example is presented for discussion.     

Job sequencing and due date assignment in a single machine shop with uncertain processing times

This paper considers due date assignment and sequencing for multiple jobs in a single machine shop. The processing time of each job is assumed to be uncertain and is characterized by a mean and a variance with no knowledge of the entire distribution. A heuristic procedure is developed to find job sequence and due date assignment to minimize a linear combination of three penalties: penalty on job earliness, penalty on job tardiness, and penalty associated with long due date assignment. Numerical experiments indicate that the performance of the procedure is stable and robust to job processing time distributions. In addition, the performance improves when the means and variances of job processing times are uncorrelated or negatively correlated or when the penalty of a long due date assignment is significant.     

Single-machine serial-batching scheduling with a machine availability constraint,position-dependent processing time,and time-dependent set-up time

This article considers the single-machine serial-batching scheduling problem with a machine availability constraint, position-dependent processing time, and time-dependent set-up time. The objective of this problem is to make the decision of batching jobs and sequencing batches to minimize the makespan. To solve the problem, three cases of machine non-availability periods are considered, and the structural properties of the optimal solution are derived for each case. Based on these structural properties, an optimization algorithm is developed and an example is proposed to illustrate this algorithm.     

Sequencing games with repeated players

Two classes of one machine sequencing situations are considered in which each job corresponds to exactly one player but a player may have more than one job to be processed, so called RP(repeated player) sequencing situations. In max-RP sequencing situations it is assumed that each player’s cost function is linear with respect to the maximum completion time of his jobs, whereas in min-RP sequencing situations the cost functions are linear with respect to the minimum completion times. For both classes, following explicit procedures to go from the initial processing order to an optimal order for the coalition of all players, equal gain splitting rules are defined. It is shown that these rules lead to core elements of the associated RP sequencing games. Moreover, it is seen that min-RP sequencing games are convex. We thank two referees for their valuable suggestions for improvement. Financial support for P. Calleja has been given by the Ministerio de Educación y Ciencia and FEDER under grant SEJ2005-02443/ECON, and by the Generalitat de Catalunya through a BE grant from AGAUR and grant 2005SGR00984.     

An <Emphasis Type="Italic">O</Emphasis>(<Emphasis Type="Italic">N</Emphasis> log (1/<Emphasis Type="Italic">ɛ</Emphasis>)) Algorithm for the Two-resource Allocation Problem with a Non-differentiable Convex Objective Function

This paper considers a job consisting of N totally ordered tasks. There is a budget for each of the two non-substitutable resources needed for the tasks. The processing time of each task is inversely proportional to the amount of resource allocated. We determine how to distribute the resources to the tasks so that the completion time of the job is minimized. A search procedure is presented that solves the problem with a worst case performance O(N log (1/?)), where ? is a given accuracy.     

Single-machine scheduling problems with time and position dependent processing times

We consider single-machine scheduling problems with time and position dependent job processing times. In many industrial settings, the processing time of a job changes due to either job deterioration over time or machine/worker’s learning through experiences. In the models we study, each job has its normal processing time. However, a job’s actual processing time depends on when its processing starts and how many jobs have completed before its start. We prove that the classical SPT (Shortest Processing Time) rule remains optimal when we minimize the makespan or the total completion time. For problems of minimizing the total weighted completion time, the maximum lateness, and the discounted total weighted completion time, we present heuristic sequencing rules and analyze the worst-case bounds for performance ratios. We also show that these heuristic rules can be optimal under some agreeable conditions between the normal processing times and job due dates or weights.     

Dynamic scheduling in multiclass queueing networks: Stability under discrete-review policies

This paper describes a family of discrete-review policies for scheduling open multiclass queueing networks. Each of the policies in the family is derived from what we call a dynamic reward function: such a function associates with each queue length vector q and each job class k a positive value r _k (q), which is treated as a reward rate for time devoted to processing class k jobs. Assuming that each station has a traffic intensity parameter less than one, all policies in the family considered are shown to be stable. In such a policy, system status is reviewed at discrete points in time, and at each such point the controller formulates a processing plan for the next review period, based on the queue length vector observed. Stability is proved by combining elementary large deviations theory with an analysis of an associated fluid control problem. These results are extended to systems with class dependent setup times as well as systems with alternate routing and admission control capabilities. This revised version was published online in June 2006 with corrections to the Cover Date.     

Single facility scheduling with multiple job classes

This paper considers a static single facility scheduling problem where jobs are divided into several mutually exclusive classes. The jobs in a given class need not be processed together. In addition to a known processing time for each job, there is a switching time involved which depends on the class of the job immediately preceding a job. A heuristic algorithm is proposed to find a minimum mean flow time schedule. The effectiveness of the proposed heuristic algorithm is empirically evaluated and found to indicate that the solutions obtained from this heuristic algorithm are often close to optimal.     

Single-job lot streaming in m − 1 two-stage hybrid flowshops

This paper studies the single-job lot streaming problem in a two-stage hybrid flowshop that has m identical machines at the first stage and one machine at the second stage, to minimise the makespan. A setup time is considered before processing each sublot on a machine. For the problem with the number of sublots given, we prove that it is optimal to use a rotation method for allocating and sequencing the sublots on the machines. With such allocation and sequencing, the sublot sizes are then optimised using linear programming. We then consider the problem with equal sublot sizes and develop an efficient solution to determining the optimal number of sublots. Finally optimal and heuristic solution methods for the general problem are proposed and the worst-case performance of the equal-sublot solution is analysed. Computational results are also reported demonstrating the close-to-optimal performances of the heuristic methods in different problem settings.     

Scheduling controllable processing time jobs in a deteriorating environment

In many real-life applications, job processing times are a function of the waiting time prior to their execution. In the most general setting, each job comprises of a basic processing time, which is independent of its start time, and a start time-dependent deterioration function. Some common examples of deteriorating systems include fire fighting, pollution containment, and medical treatments. To date, research has focused on scheduling models where the basic processing time of jobs is constant. However, job processing times are often controllable through the allocation of a limited non-renewable resource. We study a single-machine setting that combines these two models under the assumptions of general linear deterioration and convex resource functions. We develop a polynomial time solution for minimizing the makespan. For the total flowtime criterion, we compute the optimal resource allocation policy for a given job instance and show that the sequencing problem is at least as hard as the case with non-controllable jobs. We follow by discussing the properties of several special cases.     

Single-machine due window assignment and scheduling with a common flow allowance and controllable job processing time

In this paper, we consider single-machine due window assignment and scheduling with a common flow allowance and controllable job processing times, subject to unlimited or limited resource availability. Due window assignment with a common flow allowance means that each job has a job-dependent due window, the starting time and completion time of which are equal to its actual processing time plus the job-independent parameters q₁ and q₂, respectively, which are common to all the jobs. The processing time of each job is either a linear or a convex function of the amount of a common continuously divisible resource allocated to the job. We study five versions of the problem that differ in terms of the objective function and processing time function being used. We provide structural properties of the optimal schedules and polynomial-time solution algorithms for the considered problems.     

Multi-objective parallel machine scheduling problems by considering controllable processing times

This study examines parallel machine scheduling problems with controllable processing times. The processing time of each job can be between lower and upper bounds, and a cost is associated with the processing of a job on a machine. The processing time of a job can be decreased, which may lower the cycle time, although doing so would incur additional costs. This study develops two multi-objective mathematical models, which consist of two and three inconsistent objective functions, respectively. The first model minimizes the total manufacturing cost (TMC) and the total weighted tardiness (TWT) simultaneously, while the second uses makespan (C_max) as an additional objective function. In contrast to conventional mathematical models, efficient solutions are attained using the lexicographic weighted Tchebycheff method (LWT). Experimental results indicate that the LWT yields better-spread solutions and obtains more non-dominated solutions than its alternative, that is the weighted-sum method, which is a widely used yet promising approach to achieve multi-objective optimization. Results of this study also demonstrate that in purchasing machines, the variation in the fixed costs associated with the processing of jobs on machines is critical to reducing TWT. Moreover, using C_max as an additional objective function typically improves TWT and worsens TMC.     

Scheduling jobs on a single machine with release dates, delivery times and controllable processing times: worst-case analysis

The paper deals with the problem of scheduling jobs on a single machine, in which each job has a release date, a delivery time and a controllable processing time, having its own associated linearly varying cost. An approximation algorithm for minimizing the overall schedule cost is provided which has the performance guarantee of , where is the worst-case performance bound of a procedure used in the proposed algorithm for solving the pure sequencing problem. The best approximation procedure known has .