{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,3]],"date-time":"2022-04-03T02:56:24Z","timestamp":1648954584822},"reference-count":36,"publisher":"Cambridge University Press (CUP)","issue":"1","license":[{"start":{"date-parts":[[2009,2,27]],"date-time":"2009-02-27T00:00:00Z","timestamp":1235692800000},"content-version":"unspecified","delay-in-days":5870,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["AIEDAM"],"published-print":{"date-parts":[[1993,2]]},"abstract":"<jats:p>In this paper, we show how a temporal constraint propagation technique can be embedded in the machine sequencing approach for solving the job shop scheduling problem. The temporal constraint propagation algorithm propagates the precedence constraints and machine interference constraints to reduce the search space generated by the machine sequencing approach. Further, by making use of the temporal nature of the job shop scheduling, efficient algorithms to propagate precedence constraints and machine interference constraints are developed. Experimental results reveal that embedding constraint propagation in the machine sequencing approach significantly reduces the computation time more than by just using the machine sequencing approach alone. Further, the proposed temporal constraint propagation algorithms provide an order of magnitude improvement on the computation time over the conventional constraint propagation algorithm.<\/jats:p>","DOI":"10.1017\/s0890060400000056","type":"journal-article","created":{"date-parts":[[2010,3,31]],"date-time":"2010-03-31T09:47:51Z","timestamp":1270028871000},"page":"37-52","source":"Crossref","is-referenced-by-count":0,"title":["Embedding temporal constraint propagation in machine sequencing for job shop scheduling"],"prefix":"10.1017","volume":"7","author":[{"given":"Wesley W.","family":"Chu","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Patrick H.","family":"Ngai","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2009,2,27]]},"reference":[{"key":"S0890060400000056_ref034","doi-asserted-by":"publisher","DOI":"10.1287\/opre.25.1.70"},{"key":"S0890060400000056_ref033","first-page":"45","article-title":"Constructing and maintaining detailed production plans; investigations into the development of knowledge-based factory scheduling systems","volume":"7","author":"Smith","year":"1986","journal-title":"AI Magazine"},{"key":"S0890060400000056_ref031","unstructured":"Sadeh N. and Fox M. S. 1990. Variable and value ordering heuristics for activity-based job-shop scheduling. Proceedings of the Fourth International Conference on Expert Systems in Production and Operations Management."},{"key":"S0890060400000056_ref030","volume-title":"Machine Scheduling Problems: Classification, Complexity and Computation","author":"Rinnooy Kan","year":"1976"},{"key":"S0890060400000056_ref029","doi-asserted-by":"publisher","DOI":"10.1057\/jors.1980.191"},{"key":"S0890060400000056_ref028","doi-asserted-by":"publisher","DOI":"10.1007\/BF02186362"},{"key":"S0890060400000056_ref027","volume-title":"Industrial Scheduling","author":"Muth","year":"1963"},{"key":"S0890060400000056_ref020","doi-asserted-by":"publisher","DOI":"10.1002\/nav.3800010110"},{"key":"S0890060400000056_ref023","doi-asserted-by":"publisher","DOI":"10.1016\/0004-3702(77)90007-8"},{"key":"S0890060400000056_ref002","first-page":"40","article-title":"Single machine job sequencing with precedence constraints","volume":"6","author":"Adolphson","year":"1977","journal-title":"Journal of Computing"},{"key":"S0890060400000056_ref015","first-page":"156","volume-title":"Sequencing and Scheduling: an introduction to the mathematics of job-shop","author":"French","year":"1982"},{"key":"S0890060400000056_ref025","doi-asserted-by":"publisher","DOI":"10.1287\/opre.23.3.475"},{"key":"S0890060400000056_ref012","doi-asserted-by":"publisher","DOI":"10.1111\/j.1468-0394.1984.tb00424.x"},{"key":"S0890060400000056_ref036","volume-title":"Operational Research","author":"Yueh","year":"1976"},{"key":"S0890060400000056_ref019","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-5060(08)70356-X"},{"key":"S0890060400000056_ref001","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.34.3.391"},{"key":"S0890060400000056_ref004","doi-asserted-by":"publisher","DOI":"10.1002\/nav.3800270313"},{"key":"S0890060400000056_ref007","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.35.2.164"},{"key":"S0890060400000056_ref032","volume-title":"Proceedings of UltraTech Conference","author":"Smith","year":"1986"},{"key":"S0890060400000056_ref003","volume-title":"Introduction to Sequencing and Scheduling","author":"Baker","year":"1974"},{"key":"S0890060400000056_ref017","volume-title":"Computers and Intractability. A Guide to the Theory of NP-Completeness","author":"Garey","year":"1979"},{"key":"S0890060400000056_ref024","doi-asserted-by":"publisher","DOI":"10.1016\/0004-3702(85)90041-4"},{"key":"S0890060400000056_ref022","unstructured":"Lowerce B. 1976. The HARPY Speech Recognition System, Ph.D. thesis, CS Dept., Carnegie-Mellon University."},{"key":"S0890060400000056_ref021","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.19.5.544"},{"key":"S0890060400000056_ref005","doi-asserted-by":"publisher","DOI":"10.1287\/opre.17.6.941"},{"key":"S0890060400000056_ref006","doi-asserted-by":"publisher","DOI":"10.1145\/361219.361224"},{"key":"S0890060400000056_ref008","volume-title":"Theory of Scheduling","author":"Conway","year":"1967"},{"key":"S0890060400000056_ref009","volume-title":"Proceedings of IJCAI-89 Workshop on Constraint Processing","author":"Chu","year":"1989"},{"key":"S0890060400000056_ref010","doi-asserted-by":"publisher","DOI":"10.1145\/356810.356816"},{"key":"S0890060400000056_ref011","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.17.12.B782"},{"key":"S0890060400000056_ref035","volume-title":"Flexible Manufacturing Systems in Practice","author":"Talavage","year":"1988"},{"key":"S0890060400000056_ref013","volume-title":"Constraint-directed search: a case study of job shop scheduling","author":"Fox","year":"1987"},{"key":"S0890060400000056_ref014","unstructured":"Fox M. S. and Sycava K. 1990. Overview of CORTES: a constraint based approach to production planning, scheduling and control. Proceedings of the Fourth International Conference on Expert Systems in Production and Operations Management."},{"key":"S0890060400000056_ref016","doi-asserted-by":"publisher","DOI":"10.1145\/359642.359654"},{"key":"S0890060400000056_ref018","first-page":"305","article-title":"Algorithms for solving production scheduling problems","volume":"12","author":"Giffler","year":"1960","journal-title":"Operations Research"},{"key":"S0890060400000056_ref026","doi-asserted-by":"publisher","DOI":"10.1016\/0004-3702(86)90083-4"}],"container-title":["Artificial Intelligence for Engineering Design, Analysis and Manufacturing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0890060400000056","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,16]],"date-time":"2019-05-16T15:16:47Z","timestamp":1558019807000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0890060400000056\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1993,2]]},"references-count":36,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1993,2]]}},"alternative-id":["S0890060400000056"],"URL":"https:\/\/doi.org\/10.1017\/s0890060400000056","relation":{},"ISSN":["0890-0604","1469-1760"],"issn-type":[{"value":"0890-0604","type":"print"},{"value":"1469-1760","type":"electronic"}],"subject":[],"published":{"date-parts":[[1993,2]]}}}