Earliness penalties on a single machine subject to precedence constraints: SLK due date assignment

The paper considers the single machine due date assignment and scheduling problems with n jobs in which the due dates are to be obtained from the processing times by adding a positive slack q. A schedule is feasible if there are no tardy jobs and the job sequence respects given precedence constraints. The value of q is chosen so as to minimize a function ϕ(F,q) which is non-decreasing in each of its arguments, where F is a certain non-decreasing earliness penalty function. Once q is chosen or fixed, the corresponding scheduling problem is to find a feasible schedule with the minimum value of function F. In the case of arbitrary precedence constraints the problems under consideration are shown to be NP-hard in the strong sense even for F being total earliness. If the precedence constraints are defined by a series-parallel graph, both scheduling and due date assignment problems are proved solvable in time, provided that F is either the sum of linear functions or the sum of exponential functions. The running time of the algorithms can be reduced to if the jobs are independent. Scope and purpose We consider the single machine due date assignment and scheduling problems and design fast algorithms for their solution under a wide range of assumptions. The problems under consideration arise in production planning when the management is faced with a problem of setting the realistic due dates for a number of orders. The due dates of the orders are determined by increasing the time needed for their fulfillment by a common positive slack. If the slack is set to be large enough, the due dates can be easily maintained, thereby producing a good image of the firm. This, however, may result in the substantial holding cost of the finished products before they are brought to the customer. The objective is to explore the trade-off between the size of the slack and the arising holding costs for the early orders.

Earliness penalties on a single machine subject to precedence constraints: SLK due date assignment

Abstract not available

Diallel analysis in cowpea aiming at selection for extra-earliness.

In Brazil, the production of cowpea is concentrated in the Northeast and North; however, in recent years, its cultivation has expanded to the Cerrado biome of the Brazilian Midwest region, where it is incorporated into production arrangements in the form of off-season

Metaheuristic approaches to the hybrid flow shop scheduling problem with a cost-related criterion

In the paper, the flow-shop scheduling problem with parallel machines at each stage (machine center) is studied. For each job its release and due date as well as a processing time for its each operation are given. The scheduling criterion consists of three parts: the total weighted earliness, the total weighted tardiness and the total weighted waiting time. The criterion takes into account the costs of storing semi-manufactured products in the course of production and ready-made products as well as penalties for not meeting the deadlines stated in the conditions of the contract with customer. To solve the problem, three constructive algorithms and three metaheuristics (based one Tabu Search and Simulated Annealing techniques) are developed and experimentally analyzed. All the proposed algorithms operate on the notion of so-called operation processing order, i.e. the order of operations on each machine. We show that the problem of schedule construction on the base of a given operation processing order can be reduced to the linear programming task. We also propose some approximation algorithm for schedule construction and show the conditions of its optimality.

混合流水车间提前/拖期调度问题的DE优化解

针对JIT生产模式下的混合流水车间调度问题特点,提出了采用DE算法与指派规则联合调度策略求解流水车间提前/拖期调度问题。构建了混合流水车间的提前/拖期调度模型。详细论述了DE算法的实施流程和关键问题。在算法实施过程中,首先,采用DE算法进行全局寻优,完成生产任务指派,确定某个工件在某个工序在哪个工位加工;然后采用局部指派规则来确定工件在该工序的开工时间。在满足目标完成时间(交货期)的前提下,使提前惩罚费用与拖期惩罚费用之和最小。数值计算结果证明了该算法的有效性。

Approximation Algorithms for a Symmetric Quadratic Knapsack Problem and its Scheduling Applications

We consider a knapsack problem to minimize a symmetric quadratic function. We demonstrate that this symmetric quadratic knapsack problem is relevant to two problems of single machine scheduling: the problem of minimizing the weighted sum of the completion times with a single machine non-availability interval under the non-resumable scenario; and the problem of minimizing the total weighted earliness and tardiness with respect to a common small due date. We develop a polynomial-time approximation algorithm that delivers a constant worst-case performance ratio for a special form of the symmetric quadratic knapsack problem. We adapt that algorithm to our scheduling problems and achieve a better performance. For the problems under consideration no fixed-ratio approximation algorithms have been previously known.

Schedules with due-date assignment and position-dependent processing times

Single machine scheduling problems are considered, in which the processing of jobs depend on positions of the jobs in a schedule and the due-dates are assigned either according to the CON rule (a due-date common to all jobs is chosen) or according to the SLK rule (the due-dates are computed by increasing the actual processing times of each job by a slack, common to all jobs). Polynomial-time dynamic programming algorithms are proposed for the problems with the objective functions that include the cost of assigning the due-dates, the total cost of disgarded jobs (which are not scheduled) and, possibly, the total earliness of the scheduled jobs.

Single machine scheduling and due date assignment with positionally dependent processing times

We consider single machine scheduling and due date assignment problems in which the processing time of a job depends on its position in a processing sequence. The objective functions include the cost of changing the due dates, the total cost of discarded jobs that cannot be completed by their due dates and, possibly, the total earliness of the scheduled jobs. We present polynomial-time dynamic programming algorithms in the case of two popular due date assignment methods: CON and SLK. The considered problems are related to mathematical models of cooperation between the manufacturer and the customer in supply chain scheduling.

Interstitial pregnancies' diagnosis and management: an eleven cases series.

PRINCIPLES: Interstitial pregnancy represents 2% of ectopic pregnancies, but it is a highly morbid condition with a 2.5% of maternal mortality. Its diagnostic and therapeutic management remains controversial. The aim of this review is to describe the management of interstitial pregnancy in our institution between 2001 and 2011 and to define some general rules for the clinical practice. METHODS: Single institution retrospective study. RESULTS: Eleven women were treated for interstitial pregnancy. The median age was 33 years and the median gestity was 4. Seven patients had a history of gynaecological surgery and four interstitial pregnancies followed in vitro fertilisation. The diagnosis was made at a median gestational age of seven weeks with a median beta-HCG level of 5,838 U/l. Six of the eleven patients received an initial treatment with intracornual methotrexate, three with intramuscular methotrexate and two with surgery. The median time to beta-HCG resolution was 58 days. Three of the eleven patients needed a second line treatment: two after intramuscular methotrexate and one after intracornual methotrexate. Six patients had further pregnancies and delivered by caesarean section. CONCLUSIONS: A high prevalence of previous ectopic pregnancies, gynaecological surgery and of pregnancies resulting from in vitro fertilisation was observed. The earliness of the diagnosis was the factor that allowed a conservative treatment in most cases. Beta-HCG level follow up was fundamental in allowing a second line therapy but beta-HCG can persist over a long period of time and this must be taken into account due to its possible psychological impact. Intracornual methotrexate seems to be more efficacious than intramuscular methotrexate in our series.

Optimal Methodology for Synchronized Scheduling of Parallel Station Assembly with Air Transportation

We present an optimal methodology for synchronized scheduling of production assembly with air transportation to achieve accurate delivery with minimized cost in consumer electronics supply chain (CESC). This problem was motivated by a major PC manufacturer in consumer electronics industry, where it is required to schedule the delivery requirements to meet the customer needs in different parts of South East Asia. The overall problem is decomposed into two sub-problems which consist of an air transportation allocation problem and an assembly scheduling problem. The air transportation allocation problem is formulated as a Linear Programming Problem with earliness tardiness penalties for job orders. For the assembly scheduling problem, it is basically required to sequence the job orders on the assembly stations to minimize their waiting times before they are shipped by flights to their destinations. Hence the second sub-problem is modelled as a scheduling problem with earliness penalties. The earliness penalties are assumed to be independent of the job orders.

Desempenho agronômico de dez linhagens de soja-hortaliça

Objetivou-se avaliar o desempenho de dez linhagens de soja-hortaliça, em campo. O delineamento experimental adotado foi blocos ao acaso, com dez tratamentos (linhagens) e cinco repetições. Cada parcela experimental foi constituída por quatro linhas de plantio, com cinco metros de comprimento. Utilizou-se irrigação por aspersão. As linhagens avaliadas foram: JLM003; JLM004; JLM010; JLM018; JLM019; JLM024; JLM030; BR36; BR155 e BRS216. Avaliaram-se a precocidade média, altura de inserção da primeira vagem, número de vagens chochas, número de vagens com um grão, número de vagens com dois grãos, número de vagens com três grãos, massa fresca de vagens com um, dois e três grãos, massa fresca de 100 sementes, provenientes de vagens com um, dois e três grãos, massa de vagens não comerciais e produção de vagens comerciais por planta. Com base nos resultados obtidos, a linhagem JLM010 foi a mais indicada para a produção de soja-hortaliça por apresentar produção de grãos imaturos de 12,53 t ha-1 e maior massa fresca de 100 sementes.

Avaliação de parentais e híbridos experimentais de melão rendilhado

Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP)