亲爱的研友该休息了!由于当前在线用户较少,发布求助请尽量完整地填写文献信息,科研通机器人24小时在线,伴您度过漫漫科研夜!身体可是革命的本钱,早点休息,好梦!

Coordinating scheduling and rejection decisions in a two-machine flow shop scheduling problem

流水车间调度 计算机科学 调度(生产过程) 作业车间调度 动态优先级调度 运筹学 公平份额计划 数学优化 数学 地铁列车时刻表 操作系统
作者
Dvir Shabtay,Enrique Gerstl
出处
期刊:European Journal of Operational Research [Elsevier BV]
卷期号:316 (3): 887-898
标识
DOI:10.1016/j.ejor.2024.03.021
摘要

We study a two-machine flow shop scheduling problem where any operation can be rejected at a certain cost. A solution for such a problem requires two sets of decisions. The first involves the partition of the set of operations into two subsets: the set of operations that are accepted for scheduling in the shop, and the set of rejected operations. The second decision involves scheduling the set of accepted operations in the shop. The objective is to find a solution that minimizes the sum of the makespan and the total rejection cost. We prove that the problem is NP-hard even if all processing operations have identical processing times and identical rejection costs on either one of the two machines. We show, however, that the problem is fixed parameterized tractable with respect to a parameter that combine the number of different processing times on both machines with the number of different rejection costs on one out of the two machines. We also provide a pseudo-polynomial time algorithm for the problem, which we then convert into a fully polynomial time approximation scheme. This is achieved by dividing the problem into a set of subproblems and deriving a fully polynomial time approximation scheme for each one of them, separately. Finally, we present an integer linear programming formulation of the problem and two simple 2-approximation algorithms.
最长约 10秒,即可获得该文献文件

科研通智能强力驱动
Strongly Powered by AbleSci AI
科研通是完全免费的文献互助平台,具备全网最快的应助速度,最高的求助完成率。 对每一个文献求助,科研通都将尽心尽力,给求助人一个满意的交代。
实时播报
20秒前
善良的寒珊完成签到,获得积分10
20秒前
隐形曼青的应助被科研通管家采纳,获得10
27秒前
温柔的太君完成签到,获得积分10
39秒前
42秒前
小羊羊完成签到,获得积分10
48秒前
光亮靳完成签到,获得积分10
53秒前
坦率寻菡完成签到,获得积分10
1分钟前
1分钟前
Voiceless完成签到,获得积分10
1分钟前
1分钟前
水北完成签到,获得积分10
1分钟前
1分钟前
兴奋筮完成签到,获得积分10
1分钟前
1分钟前
爆米花的应助被懦弱的大有采纳,获得10
1分钟前
1分钟前
2分钟前
懦弱的大有完成签到,获得积分20
2分钟前
长情的小蕾完成签到,获得积分10
2分钟前
2分钟前
2分钟前
Jasper的应助被五岁的哈士奇采纳,获得10
2分钟前
哪块小饼干完成签到,获得积分10
2分钟前
dddj完成签到,获得积分10
2分钟前
null的应助被科研通管家采纳,获得20
2分钟前
GingerF的应助被科研通管家采纳,获得100
2分钟前
2分钟前
心灵美涵柳完成签到,获得积分10
2分钟前
2分钟前
顺心的傲松完成签到,获得积分10
2分钟前
和谐的不乐完成签到,获得积分10
3分钟前
3分钟前
Kishi完成签到,获得积分10
3分钟前
调皮雅柔完成签到,获得积分10
3分钟前
3分钟前
3分钟前
3分钟前
3分钟前
wsdow完成签到,获得积分10
3分钟前
高分求助中
(应助此贴封号)【重要!!请各用户(尤其是新用户)详细阅读】【科研通的精品贴汇总】 10000
拉伸高分子熔体中缠结行为的模拟和小角中子散射研究 1700
The World Atlas of Wine 9th edition 1000
奈特基础组织学:配套组织病理学(第4版)(Netter's Essential Histology With Correlated Histopathology) 800
John McDowells Bildungstheorie 800
Social Psychology in the Real World 600
八旗制度の研究 600
热门求助领域 (近24小时)
化学 材料科学 医学 生物 纳米技术 计算机科学 工程类 有机化学 化学工程 生物化学 物理 复合材料 内科学 催化作用 光电子学 人工智能 细胞生物学 无机化学 物理化学 数学
热门帖子
关注 科研通微信公众号,转发送积分 8179920
求助须知:如何正确求助?哪些是违规求助? 9570103
关于积分的说明 21808354
捐赠科研通 7775756
什么是DOI,文献DOI怎么找? 3433193
关于科研通互助平台的介绍 2557347
邀请新用户注册赠送积分活动 2478918